[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: Compromised entry guards rejecting safe circuits (was Re: OSI 1-3 attack on Tor? in it.wikipedia)

Anon Mus wrote:
A fully global networked array of prime number testers, prime numbers being the underlying basis for your public key encryption technology.

1 million decimal digit long primes achieved, the search for 10 million

digit primes underway.



" The virtual machine's sustained throughput <http://mersenne.org/ips/stats.html>* is currently *29479 billion floating point operations per second* (gigaflops), or 2448.9 CPU years (Pentium 90Mhz) computing time per day. For the testing of Mersenne numbers, this is equivalent to 1052 Cray T916 supercomputers"

Take a look at just which org is offering the $100,000 prize !!! (In
the para. headed by "*v22.12 Mersenne Research Software Released")*


This project went live in 1997 and the CM5 ( http://en.wikipedia.org/wiki/FROSTBURG ) was phased out in 1999 .. you decide.

Makes 512 bit prime location and storage look like a walk in the park.

You're suffering from several very serious misconceptions.

First off, the Mersenne primality testing network is designed to test prime numbers of a very specific type, namely 2^n-1. It turns out that you can test primality for those numbers in a much more efficient manner than for general primes. The Mersenne algorithm is useless for general primes, and virtually every prime used in modern cryptography is not going to be a Mersenne prime.

Second, merely testing to see if something is prime is not isn't particularly helpful in breaking modern cryptography. You already know that the public key isn't a prime (since it's the product of two private keys) and you also already know that the private keys are prime (since that's necessary for the algorithm to function.) What you'd need to do in order to derive the private keys from a public key is to *factor* an extremely large number with no convenient properties. This is an entirely different issue from mere primality testing.

Without major breakthroughs in number factoring, I seem to remember it's actually provable that modern public keys literally cannot be factored within the heat death of the universe. As in, "if you turned every atom of the universe into energy, and used it to power a universe-sized supercomputer which reaches the theoretical limits of efficiency, you would not be done factoring a single public key by the time you ran out of energy". Unless you want to claim that the US government is actually *more powerful* than this, any number of supercomputers and databases they might have is completely irrelevant.

Now, if you do want to keep on with the "the government is all-powerful and can corrupt Tor installations easily", there's a few easy tactics you can use.

First, you can claim that the US governmenet has come up with a factoring breakthrough that makes factoring - and thus far, far easier. There's certainly nothing we've discovered yet that proves this is impossible. Of course, there's no evidence for it being possible either.

Second, private keys are only as secure as they system they are stored on. Much more plausibly, you could claim that the US government has backdoors into most (if not all) modern OSes, including the ones used to generate Tor's directory server private keys. If the government got the private keys that way there would be, of course, no barrier to them intercepting Tor communications in exactly the way you claim.

But claiming that the government has huge datacenters that derive public keys from private keys is simply impossible. The math doesn't add up.

Now for a bit of hard math, just to demonstrate that you need to think about your numbers a bit further:

The density of prime numbers can be approximated as 1/log(N), as you've mentioned. This means, for 256-binary-digit primes, the density is approximately 1/log(2^256) or 0.012976. There are 2^255 (that's about 5.7896 * 10^76) 256-digit numbers, therefore we can assume that there are approximately 1/log(2^256) * 2^255 primes in that area.

This is approximately 7.5127 * 10^74 primes.

If we assume we can store each prime number on a single atom of hydrogen (this is obviously a hilarious overestimation of storage density, but bear with me) we can store 6.02214 * 10^23 prime numbers in one gram of hydrogen. Thus we will need 1.2475 * 10^51 grams in order to store our "prime database". The Sun masses approximately 1.98892 * 10^33 grams, so we'll need the hydrogen of approximately 627 thousand million million suns merely to store a list of all the 256-digit prime numbers.

If Tor uses 512-bit keys then we're approximately seventy orders of magnitude too small, however.

(That was actually kind of fun to work out.)