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) ... MD5(16000). 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 period. -- Sidney Markowitz http://www.sidney.com --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
