Since the New York Times ran a story discussing ‘DUAL_EC_DRBG' – a random number generator –controversy surrounding this algorithm has grown. NIST has advised that it not be used, while RSA warned its customers not to use it in its cryptographic library – even though it was the default algorithm.
Of the many things Edward Snowden revealed as part of his ongoing NSA exposé, evidence suggesting that DUAL_EC_DRBG contains a back door has probably had the most immediate impact on the cryptographic community. The biggest casualty has been trust – and when trust in institutions is lacking, conspiracy theories rise to take its place. With that in mind, let's take a look at the subject with our tinfoil hats on.
Random number generators are important because they are used to create cryptographic keys. One of the problems with computers from a random number generator point of view is that they are designed to be predictable, logical machines that will always give you the same answer when you ask the same question – exactly the opposite property that you want in a random number generator.
To compensate, “pseudo random number generators” (PRNGs) were invented. PRNGs are given a “seed” value, and from then on will create a stream of numbers that appear random, but are all based on that seed number. Beyond making random-looking numbers, a good PRNG is resistant to guesses about previous and future output. The new tinfoil-hat-wearing me sees a reliable source of random numbers as crucial to the security of a system – and a brilliant place to put a back door.
In 2006, NIST published Special Publication 800-90, “Recommendation for Random Number Generation Using Deterministic Random Bit Generators”. NIST publications are taken seriously by the cryptographic community as they contain industry best practices, vetted and mature algorithms, and frequently come to be required by government certifications, like FIPS 140-2. As such, security researchers and makers of security products pay close attention to them. The twist here is that the NSA authored SP 800-90, and it describes four different types of DRBG. Two of them are based on hash functions, one is based on encryption and one is based on a “number theoretic problem”. The latter is DUAL_EC_DRBG.Why four algorithms?
The document states “in the event that new attacks are found on a particular class of DRBG mechanisms, a diversity of approved mechanisms will allow a timely transition to a different class of DRBG mechanism”. In other words, have several algorithms ready to choose from in case one is broken. This makes complete sense, and the old me would unquestioningly agree with this statement. However, it wasn't long before it was noticed that DUAL_EC_DRBG wasn't quite right. It was slow in comparison to the others, and it had some obvious security flaws. In 2007, Microsoft showed that there were “magic numbers” that would allow it to be broken open, a “skeleton key”, such as we discussed earlier.
Even with this evidence, NIST kept DUAL-EC-DRBG as part of SP 800-90. So was NIST duped by the NSA or was it in league with the NSA? Many prominent security researchers warned against its use, but since it was part of the standard it was implemented far and wide. Moreover, it wasn't long before it was noticed that RSA's “BSAFE” cryptographic library used the algorithm by default. At this point, with all of the evidence pointing one direction, it's time to draw uncomfortable conclusions regarding anyone involved in implementing DUAL_EC_DRBG.