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

[Ben Wilhelm]

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.
> 
> http://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search
> 
> http://mersenne.org/primenet/
> 
> " 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")*
> 
> http://mersenne.org/ips/index.html#contest
> 
> 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.)

-Ben