[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:
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