Random Fail

I must be out of the security loop. I first learned about the latest random number bug via a cartoon. Schneier has a short summary of the problem.

This is very disturbing because it went unnoticed since September of 2006 in a number of Linux distributions. Both SSL certificates and SSH keys generated on these systems are affected.

This reminds me of a paper I wrote on a similarly weak RNG in Kerberos, with Steve Lodin and Gene Spafford 11 years ago. In the case of Kerberos Version 4, it used a RNG that depended only about 20 bits of entropy. The maintainers of Kerberos knew it was weak and implemented a much stronger one for Kerberos Version 5 and backported the new RNG to Version 4. However, the old RNG code was left in the source tree and due to a somewhat convoluted Makefile and source code, the new RNG was never called. The failure was masked by the existence of the old, weaker RNG code.

While working at Sun Microsystems, on the groundbreaking, but commercially unsuccessful SPF-100, I did more work on RNGs. These experiences confirmed to me the difficulty in writing a good, cryptographically strong, RNG.

The RNG that our group at Sun used was based on the RNG for PGP (the gold standard of crypto at the time). The seeding and generation of random numbers were fine, except the developer had gotten too clever. The algorithm used md5 to generate random bits based on a entropy pool. If you requested fewer bytes than were generated by the md5 block, those bits would be wasted. So instead, the algorithm saved the extra random bits for later. This was where the bug was, it wouldn't make any more random bits unless you asked for more than one md5 block worth of randomness. Session keys just happened to be short enough to never trigger new randomness. So while the Diffie-Hellman key exchange was secure, the underlying session keys were very weak.

Thankfully someone was debugging and noticed that the session keys stayed the same, even after they were renegotiated. Maybe it was Rich, I can't remember now.

The moral is: be very careful building your RNG and don't forget to test the randomness of the output. The Dieharder test suit is a good start. Make sure you test the right way too. Generate the random test data exactly like the RNG will get called in the code. Same number of bits, same pattern of calls. Then don't forget to retest before you ship. :)

Good luck, and stay random.

Write