Ramblings & ephemera

The NSA’s cryptographic backdoor

From Bruce Schneier’s “The Strange Story of Dual_EC_DRBG” (Crypto-Gram: 15 November 2007):

This year, the U.S. government released a new official standard for random number generators, which will likely be followed by software and hardware developers around the world. Called NIST Special Publication 800-90, the 130-page document contains four different approved techniques, called DRBGs, or “Deterministic Random Bit Generators.” All four are based on existing cryptographic primitives. One is based on hash functions, one on HMAC, one on block ciphers, and one on elliptic curves. It’s smart cryptographic design to use only a few well-trusted cryptographic primitives, so building a random number generator out of existing parts is a good thing.

But one of those generators — the one based on elliptic curves — is not like the others. Called Dual_EC_DRBG, not only is it a mouthful to say, it’s also three orders of magnitude slower than its peers. It’s in the standard only because it’s been championed by the NSA, which first proposed it years ago in a related standardization project at the American National Standards Institute.

Problems with Dual_EC_DBRG 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 workaround 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 at the CRYPTO 2007 conference this past August, Dan Shumow and Niels Ferguson showed that the algorithm contains a weakness that can only be described as a backdoor.

What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.

My recommendation, if you’re in need of a random number generator, is not to use Dual_EC_DRBG under any circumstances. If you have to use something in SP 800-90, use CTR_DRBG or Hash_DRBG. Or Fortuna or Yarrow, for that matter.

Comments are closed.