Was Secret Backdoor In New Encryption Standard Put There By The NSA?

In a recent article written by Bruce Schneier, noted cryptographer from e-media mag Wired.com, the author examines the research (PDF) of security experts Niels Ferguson and Dan Shumow, presenters at the CRYPTO 2007 conference this past August.  Ferguson and Shumow suggest that an algorithm for generating random numbers included in an official standard document (PDF) by the National Institute of Standards and Technology (NIST) contains a weakness that can only be described as a backdoor.

Earlier this year the U.S. government released a new official standard for random-number generators that is likely to be followed by software and hardware developers around the world called NIST Special Publication 800-90, a 130-page document (PDF) containing four different approved techniques called DRBGs, or "Deterministic Random Bit Generators." All four are based on existing cryptographic primitives.

Ferguson and Shumow raised concerns about the potential backdoor in the Dual_EC_DRBG algorithm which unlike the others, is based on elliptic curves, said to three orders of magnitude slower than the others. The only reason Dual_EC_DRBG is in the standard is because it's favored by the NSA who first proposed it years ago.

The National Security Agency (NSA) has always been intimately involved in U.S. cryptography standards, so their participation in the NIST standard is not sinister in itself. Only when you look under the hood at the NSA's contribution do questions arise.

Problems with Dual_EC_DRBG were first described in early 2006. While not enough of a problem to make the algorithm unusable and Appendix E of the NIST standard describes an optional work-around to avoid the issue, it is problematic enough to cause concern.

How it works

There are a bunch of constants, or fixed numbers, in the standard used to define the algorithm's elliptic curve. The constants are listed in Appendix A of the NIST publication, but no explanation of where they came from can be found.

The presentation by Ferguson and Shumow showed 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. In other words, you only need to monitor one Transport Layer Security (TLS) Internet encryption connection in order to crack the security of that protocol. If you only know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.

Ferguson and Shumow don't know what the secret numbers are, but because of the way the algorithm works, the person who produced the constants might know; he or she had the mathematical opportunity to produce the constants and the secret numbers in tandem.

What makes NSA involvement scary

Also noted by Schneier on Wired.com is that we have no way of knowing whether the NSA knows the secret numbers that break Dual_EC_DRBG, whether an NSA employee working on his or her own came up with the constants has the secret numbers, if someone from the NIST has them, or if nobody does.

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 there's no way for the NIST -- or anyone else -- to prove otherwise.

Even if no one knows the secret numbers, the Dual_EC-DRBG backdoor alone makes it very fragile. If someone solved just one instance of the algorithm's elliptic curve problem, they would effectively have the keys to the kingdom, being able to use it for whatever nefarious purpose. Publishing the result would render every implementation of the random-number generator completely insecure.

While the possible method to implement Dual_EC_DRBG in such a way as to protect it against the backdoor is documented in the NIST document in Appendix E, the procedure is optional, meaning that most implementations won't bother.

It is unclear as to why the NSA was so insistent about including Dual_EC_DRBG in the NIST standard as a trap door: It is public and rather obvious. From an engineering perspective it's too slow for anyone to willingly use it. From a backwards-compatibility perspective, swapping one random-number generator for another is easy.

I've questioned the NSA's involvement in Windows, primarily Windows Vista, in the past, as have a couple of others. If you're in need of a random-number generator, Schneier recommends avoiding the Dual_EC_DRBG standard under any circumstances, using one of the remaining other three standards in Special Publication 800-90 instead if you must use that standard. He also noted that in the meantime, both the NIST and the NSA have some explaining to do.

All the links used above can be found below:

• Did NSA Put a Secret Backdoor in New Encryption Standard? article from Wired.com
   
• Report (PDF) titled 'On the possibility of a back door in the NIST SP800-90 Dual Ec Prng from CRYPTP 2007 conference
   
• CRPYTO 2007 web site presented by the International Association for Cryptologic Research (IACR)
   
• National Institute of Standards and Technology (NIST) web site
   
• NIST Special Publication 800-90 (PDF) - Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised)
   
• Backdoor (computing) definition from Wikipedia
   
• National Security Agency/Central Security Service (NSA/CSS) start page
   
• Transport Layer Security definition from Wikipedia
   
• Microsoft, the DoD and Windows article in Infopackets gazette
   
• Does Windows Vista Send Information to the Government? article in Infopackets gazette
   
• NSA Likely Reading Windows Software In Your Computer article from AfterDowningStreet
   
• NSA may be Reading your Computer article from Scoop NZ

Visit Bill's Links and More for more great tips, just like this one!