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

[Anon Mus <a_green_lantern@xxxxxxxxx>]

Ben Wilhelm wrote:
>
> 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
>
>

Ben,

Yes you are right factorising this is hard, but thats not what I've
been 
suggesting. What if every time you generated a pair of keys you stored 
the result somewhere!

Say you owned a huge network of say mil/gov computers which communicate

securely using sefl generated rotating keys. As any client finishes
with 
a key pair they send them off to a central storage location.  If they 
are not there already they are added to the store.

To find the private key(s) you only need to search through the list of 
public keys. If you only find 1% of the server communities private keys

then you've got many extra nodes to add to your dummy network.

Hopefully you understand this and I'll get some sleep tonite ( :D ).

-K-




      ____________________________________________________________________________________
Never miss a thing.  Make Yahoo your home page. 
http://www.yahoo.com/r/hs