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:
>> 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-
>
> You're continuing to drastically underestimate the numbers involved. 
> Let's say that a computer is a cube, one half foot on each side. Now 
> let's take the Earth, and *cover the Earth with solid computers* to a

> depth of one mile. This gives us approximately 232 billion billion 
> computers. If you assume that each computer can generate a thousand 
> private/public pairs per second (I believe this is an exaggeration
for 
> commodity hardware, though you could likely build a custom system to 
> do so) then that means we get 2.32 * 10^23 keys every second.
>
> I'm going to go handwavy here and assume that one key is
approximately 
> equal to one prime. This isn't true, but we'll end up within an order

> of magnitude of the right answer, and honestly more precision than 
> that isn't needed.
>
> With 7.5127 * 10^74 primes, attempting to cover 1% of the keyspace at

> 2.32 * 10^23 keys per second would take approximately one million 
> million million million million million million *years*. Excuse me
for 
> not being particularly worried about this. And remember, this assumes

> the entire surface of the planet is covered, a mile thick, with 
> computers. Last I checked this was not the case.
>
> (Again, this also ignores the issue of where you store all this
data.)
>
> Seriously, sit down and think about the numbers some. The numbers are

> *gigantic* - so gigantic that "brute force" becomes implausible, even

> if you assume the adversary owns all the government and corporations 
> of our world and has access to alien supercomputers.
>
> -Ben
>
>
Ben,

I think you are using the purely theoretical  numbers and applying them

to the problem as if they were reality.

As I remember the problem with the selection of primes for PKE is,

1. the seeding of the pseudo-random number generator

e.g. with a 16bit seed then only 65,000 or so entry points into the 
number generation which leads that number of keys.

Even for an 8byte random seed the number of keys generated would be 
about 10^19 keys and obviously, following your example, this represents

less than a milligram of your hydrogen memory, about a breath of air in

the lungs of the average human being.

2. the pseudo-random numbers generators, themselves have not been
proven 
to be numerically complete. Indeed their very form suggests not.


Bearing these things in mind, it may be possible to "pick off" machines

where their key is only generated from a small sub-set of the total 
possible keys.

I am sorry I included the example of the prime numbers tail off as it 
only served to confuse the issue and probably got you involved in your 
calculation in the first place.

Hopefully, this brings a "breath of fresh air" to this subject and ends

the scoffing of some detractors.

Of course, the scenario for this attack, as originally outlined ( Re: 
OSI 1-3 attack on Tor? in it.wikipedia), is still intact, fully correct

and easily provable.

Thank you for your interest.


-K-  
 




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