[Cryptography] RSA recommends against use of its own products.

Ray Dillinger bear at sonic.net
Fri Sep 20 15:14:22 EDT 2013


> *1 "Anyone who attempts to generate random numbers by
>      deterministic means is, of course, living in a
>      state of sin." -- John Von Neumann


That said, it seems that most of these attacks on Pseudorandom
generators some of which are deliberately flawed, can be ameliorated
somewhat by using a known-good (if slow) Pseudorandom generator.

If we were to take the compromised products, rip out the PRNG's,
and replace them with Blum-Blum-Shub generators, we would have
products that work more slowly -- spending something like an
order of magnitude more time on the generation of Pseudorandom
bits -- but the security of those bits would be subject to an
actual mathematical proof that prediction of the next really is
at least equal in difficulty to a known-size factoring problem.
Factoring problems apparently aren't as hard as we used to think
but they *are* still pretty darn hard.

Slow or not, I think we do need to have at least one option
available in most PRNG-using systems which comes with a
mathematical proof that prediction is GUARANTEED to be hard.
Otherwise it's too easy for people and businesses to be caught
absolutely flatfooted and have no recourse when a flawed PRNG
is discovered or a trust issue requires them to do something
heroic in order to convince customers that the customers' data
can actually be safe.

We've been basing our notion of security on the idea that others
don't know something we don't know -- which is sort of nebulous
on its face and of course can never be provable. We can't really
change that until/unless we can say something definite about
P=NP, but we're a lot more sure that nobody else has anything
definite to say about P=NP than we are about most crypto
primitives.

Do we know of anything faster than BBS that comes with a real
mathematical proof that prediction is at least as hard as
$SOME_KNOWN_HARD_PROBLEM ?

				Bear


More information about the cryptography mailing list