RNG quality verification

Sidney Markowitz sidney at sidney.com
Tue Jan 3 15:37:30 EST 2006

Philipp Gühring wrote:
> I took OpenSSL, generated 10000 RSA keys, and took them apart.
> First I analyzed the raw keys:

Try this:

Generate 256000 bytes from MD5(i), i=1...16000 and run the same tests. That is
clearly not acceptable as a PRNG because it is completely predictable if you
know that the sequence is MD5(1) ... MD5(16000), but it should pass any tests
other than one that checks specifically if it is correlated to MD5(1) ...

Perhaps you would say that example is unfair because MD5 makes a perfectly good
PRNG as long as the software package seeds it properly. In that case, how are
you going to ensure that the package you are testing is seeding the PRNG properly?

In fact, the famous Netscape vulnerability was based on a PRNG that was simply
MD5 of a counter, with the vulnerability being predictability of the seed. See
http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html for a clear
description of that.

Your tests would not detect that kind of vulnerability.

You asked,
> Has anyone tested yet, how much samples are needed to detect those PRNGs?

The point is that your tests will not detect the difference between a PRNG
using a properly seeded MD5(counter) and one with a predictable seed. More
generally, a sequence can be predictable while still being statistically random.

Carrying it even further, back in 1996 the only problem with using MD5 of a
counter as a PRNG was making sure that the seed was unpredictable. That may not
be true anymore because of recent results of MD5 collisions, or more
accurately, it may not remain true if stronger attacks continue to be found.
Statistical tests have not all of a sudden changed their results: MD5 will not
appear any less random in those tests just because vulnerabilities are found.

So how do you certify PRNGs used by your customers? You have them use well
known software packages that have been analyzed and vetted by the cryptographic
community, such as OpenSSL. It would be a shock if any of them did not pass the
simple statistical tests that you can perform. Passing those tests does not
ensure that there are none of the more subtle vulnerabilities that are only
discovered by many smart people taking a very hard look over a significant time

 -- Sidney Markowitz

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list