Does a new government encryption standard contain a back door for the NSA? That's what security researchers want to know after taking a close look at one of four random number generators approved by the National Institutes of Standards and Technology, Bruce Schneier writes in Wired.
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.
The problem, Scheier says, is not that NSA is involved - they are the crypto experts of course - but the algorithm itself smells fishy.
In an informal presentation 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. This is how it works: There are a bunch of constants -- fixed numbers -- in the standard used to define the algorithm's elliptic curve. These constants are listed in Appendix A of the NIST publication, but nowhere is it explained where they came from. 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.
Schneier says this is "scary stuff indeed" and that NIST and NSA "have some explaining to do." In the meantime, don't use Dual_EC_DRBG.