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

[Ben Wilhelm]

Anon Mus wrote:
> 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.

Yes, this is correct - if you use a horrifically insecure random-number 
generator, you'll end up with a horrifically insecure public key. Any 
serious application of crypto will use a random-number generator with 
far more than 16 bits of entropy. I don't actually know what the current 
standard for pseudo-random crypto generators are, but I give as a simple 
example Boost's Mersenne Twister generator, which, as I understand it, 
can be given something on the order of 20,000 bits of entropy as a seed. 
(Obviously, this is far more than is strictly needed to generate all 
256-bit primes.)

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

This is untrue in several ways. There's nothing in the structure of a 
psuedorandom generator which makes it impossible to analyse, and many 
pseudorandom generators are understood extremely well. Again, this isn't 
something I'm particularly expert in, but it's a solved problem to 
roughly the same extent that the entire public-key cryptography issue is 
a solved problem (i.e. "solved, barring spectacular and unexpected 
advances".)

Note that you could simply use a source of truly secure entropy to 
bypass these issues entirely, and most non-embedded operating systems 
include such a thing built-in.

> 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.

We've described logically why your original attack would not work (at 
least, why it would not allow any kind of security breaches - obviously 
you can bring the Tor network down using such an attack, but that's not 
exactly avoidable.) It is neither intact nor correct, and, assuming no 
security bugs in the Tor implementation, I believe it is provably so.

-Ben