Random numbers are critical for cryptography: for encryption keys, random authentication challenges, initialization vectors, nonces, key-agreement schemes, generating prime numbers and so on. Break the random-number generator, and most of the time you break the entire security system. Which is why you should worry about a new random-number standard that includes an algorithm that is slow, badly designed and just might contain a backdoor for the National Security Agency.

The NSA has always been intimately involved in U.S. cryptography standards — it is, after all, expert in making and breaking secret codes. So the agency’s participation in the NIST (the U.S. Commerce Department’s National Institute of Standards and Technology) standard is not sinister in itself. It’s only when you look under the hood at the NSA’s contribution that questions arise.

Problems with Dual_EC_DRBG were first described in early 2006. The math is complicated, but the general point is that the random numbers it produces have a small bias. The problem isn’t large enough to make the algorithm unusable — and Appendix E of the NIST standard describes an optional work-around to avoid the issue — but it’s cause for concern. Cryptographers are a conservative bunch: We don’t like to use algorithms that have even a whiff of a problem. But today there’s an even bigger stink brewing around Dual_EC_DRBG. In an informal presentation (.pdf) at the CRYPTO 2007 conference in August, Dan Shumow and Niels Ferguson showed that the algorithm contains a weakness that can only be described a backdoor.

We don’t know where the constants came from in the first place. We only know that whoever came up with them could have the key to this backdoor. And we know there’s no way for NIST — or anyone else — to prove otherwise.

This is scary stuff indeed.

Wired