Encryption Backdoors

Brief Rundown of Technology:

Encryption is the process of encoding and decoding messages so that only authorized people can view the content of the message. Cryptography in and of itself is not new to the digital age; cryptography has been recorded as far back as the Roman Empire (see Caesar Cipher).

Caesar Cipher
The Caesar cipher replaces each letter with a fixed number of places further alphabet. In this example is a shift of three causes the B to translate to the E in the cipher.

However, cryptography before the digital age was primitive, because encryption schemes had to be easy enough for a human to decode. Computers have allowed the use of much more complex encryption schemes because we can rely on the computers to do the extremely tough number-crunching required to decode encrypted messages.

A "backdoor" in computing is a method of bypassing the normal method of authentication. Backdoors are usually inserted into a program or algorithm before it is distributed widely. They are often hidden in part of the design of the program or algorithm. In cryptography specifically, a backdoor would allow an intruder to access the encrypted information without having the correct credentials. The backdoor would either a) allow the intruder to guess the access key based on the context of the message or b) allow the intruder to present a skeleton key that will always grant him access.

Precedence/Historic Cases:

The NSA, as the US government’s cryptologic intelligence agency, is often suspected of implementing encryption backdoors. The most substantive accusation against the NSA was made in November 2007, after the release of the 2007 NIST official standard for random-number generators.

Almost every cryptography algorithm relies on the use of random numbers to encode messages. Modern cryptography uses these random numbers for everything ranging from variable initialization to encryption keys. As such, computer-based random number generators are extremely important to computer cryptography. If an agent is able to compromise the random-number generator, that agent has most likely compromised any encryption scheme using that random-number generator.

Designing random-number generators is very difficult, and many encryption attacks have fundamentally been random-number generator attacks. In an effort to ensure that the random-number generators are secure, the National Institute of Standards and Technology (NIST) dictates which techniques are approved for use in the public and private sectors. Software and hardware developers world-wide rely on the NIST’s reports to form the basis of their encryption design choices.

NIST Special Publication 800-90, NIST’s 2007 official standard for random number generators, is believed to have included a secret backdoor on the behalf of the NSA. The 800-90 report describes four different techniques for "Deterministic Random Bit Generators" (DRBGs) based on pre-existing cryptographic primitives. Each of the four techniques is different; one relies on hash functions, one on keyed-Hash Message Authentication Code (HMAC), one on block ciphers and one on elliptic curves.

The controversy revolves around DUAL_EC_DRBG, the random-number generator based on elliptic curves. DUAL_EC_DRBG was first shown to have problems in 2006, where Daniel Brown and Kristian Gjosteen pointed out that DUAL_EC_DRBG generates random numbers with a small bias. At the 2007 CRYPTO conference, Dan Shumow and Niels Ferguson presented a weakness in the DUAL_EC_DRBG technique which they claimed was an intentional backdoor. Shumow and Ferguson demonstrated that constants used within the DUAL_EC_DRBG standard have a relationship with a secret set of numbers. Anyone who knows these numbers can predict DUAL_EC_DRBG's output, and consequently can break encryption schemes using DUAL_EC_DRBG.

What does the NSA have to do with DUAL_EC_DRBG? As the nation's cryptologic expert, the NSA has always contributed to the NIST standard. DUAL_EC_DRBG was much slower than the other three techniques described in the standard, and was demonstrated to have a huge weakness. People wondered why DUAL_EC_DRBG was included in the NIST standard until cryptology expert Bruce Schneier pointed out that the NSA made the initial proposal for DUAL_EC_DRBG and was the main lobbyist for its inclusion. Schneier makes no conclusions, but implies that it is possible that the NSA pushed so hard for DUAL_EC_DRBG because they wanted to easily crack encryption schemes. Schneier's editorial making this accusation ends with a sober note:

"I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard... 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. In the meantime, both NIST and the NSA have some explaining to do."

Further Reading:

http://www.schneier.com/essay-198.html
http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf
http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf