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
