A couple of weeks ago I wrote about Vormetric’s security, and made the case that we didn’t have any back doors that the NSA can exploit. In that post, I called out the “DUAL_EC_DRBG” random number generator that was alluded to in the New York Times article. Since then, the controversy surrounding this algorithm has only grown. NIST has advised that it not be used. On Friday RSA, the Security Division of EMC, issued a guidance statement that warned its customers not to use DUAL_EC_DRBG in its cryptographic library – even though it was the default algorithm. In this post I’ll provide some background and will try to bring you up to date on the controversy (and conspiracy theory) so far. Let me state up front that Vormetric has never used DUAL_EC_DRBG in any of its products.
Of all of the things that Snowden revealed, evidence that DUAL_EC_DRBG had a back door inserted into it has probably had the most immediate impact in the cryptographic community. The biggest casualty has been trust – trust that NIST was a neutral, open, and transparent organization. When trust in institutions is lacking, conspiracy theories rise to take its place. This transformation has happened to me personally – I normally laugh off conspiracy theorists, but now I’m becoming one. I don’t like this new viewpoint. I have always believed firmly in Hanlon’s razor: Never attribute to malice that which is adequately explained by stupidity. But now the ‘malice’ side is too prominent to ignore. With that in mind, let’s take a tour of the subject - tinfoil hat in hand.
Let’s start at the beginning. Random numbers are important because they are used to make cryptographic keys. If the random number generator can be cracked, the cryptographic keys are there for the taking. However, random numbers are something that computers do not do well at all. A computer is designed in every other way to be a predictable, logical machine that will always give you the same answer when you ask it the same question. This is exactly the opposite property that you want in a random number generator.
To compensate for this, “Pseudo Random Number Generators” (PRNGs) were invented. (PRNGs are also called “Deterministic Random Bit Generators (DRBGs), mostly by NIST.) The idea is that you give the PRNG a “seed” value, and from then on the PRNG will create a stream of numbers that look really random, but are all based from that seed number. Beyond making random-looking numbers, a good PRNG is resistant to guesses about previous and future output. The pre-tinfoil-hat me was only vaguely aware of the importance of PRNGs. The new tinfoil-hat-wearing me sees a reliable source of random numbers as absolutely 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”. Special Publications (SPs) from NIST are taken very seriously by the cryptographic community. They generally contain industry best practices, vetted and mature algorithms and processes, and are written by awfully smart people. Plus, the guidance from NIST frequently winds up being required by various government certifications, like FIPS 140-2 and Common Criteria. All this means that security researchers and the makers of security products pay close attention to them. The twist here is that the NSA authored SP 800-90. The pre-tinfoil-hat me saw NIST processes as a force for good. But with my shiny new hat it looks like a government process that can be subverted.
SP 800-90 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 the wisdom of the statement. But putting on this great hat I have to wonder – if only DUAL_EC_DRBG was introduced, would it have caused more of an uproar? Did the NSA slip a bad apple in with the good, in order to get the crate of apples out the door?
It wasn’t long before people noticed that DUAL_EC_DRBG wasn’t quite right. It was slow in comparison to the others, and it had some rather obvious security flaws. In 2007 Dan Shumow and Niels Ferguson of Microsoft published a talk titled “On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng”. They showed that there exist “magic numbers” that would allow DUAL_EC_DRBG to be broken wide open. A skeleton key, if you will. If someone had the skeleton key, they could predict what the random number generator would output – and hence what the cryptographic keys would be. The conclusion of the presentation actually states “WHAT WE ARE NOT SAYING: NIST intentionally put a back door in this PRNG”. The pre-tinfoil-hat me would have seen this as prudent and scholarly. Now it’s laughably naïve.
Even with this evidence, NIST kept DUAL-EC-DRBG as part of SP 800-90. (Was NIST duped by the NSA? Or was NIST 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. You can actually see just how far and wide it spread by looking at the DRBG Validation List published by the Cryptographic Algorithm Validation Program. This list comes about through the FIPS 140-2 certification process. FIPS 140-2 is a government certification showing that a product properly implements cryptography. Part of that involves testing the algorithms themselves. When you pass the tests, you get on lists like that one. There are 403 products validated on that list, and DUAL_EC_DRBG is mentioned 66 times. Without my new hat, I would think that most folks are implementing the entire standard and aren’t thinking things through. My tinfoil hat is seriously impressed that the NSA was able to publish a standard with a backdoor, that backdoor was detected by the security community, and the standard was STILL implemented by so many vendors in so many products.
This brings us to the present day. Security researchers have been piling on. Matthew Green of John Hopkins University wrote a brilliant, detailed post describing The Many Flaws of Dual_EC_DRBG. It wasn’t long before it was noticed that RSA’s “BSAFE” cryptographic library used DUAL_EC_DRBG by default. Why would RSA do this? Mr. Green puzzles over the matter:
So why would RSA pick Dual_EC as the default? You got me. Not only is Dual_EC hilariously slow -- which has real performance implications -- it was shown to be a just plain bad random number generator all the way back in 2006. By 2007, when Shumow and Ferguson raised the possibility of a backdoor in the specification, no sensible cryptographer would go near the thing. And the killer is that RSA employs a number of highly distinguished cryptographers! It's unlikely that they'd all miss the news about Dual_EC.
At this point, I don’t even need my tinfoil hat. It’s hard to deny that Occam’s razor falls down on the side of government coercion being the simplest, most likely explanation. This essentially gives the NSA a back door into any product that uses RSA’s BSAFE code.
It doesn’t end there. Looking back at the DRBG Validation List, you can see that Microsoft implements DUAL_EC_DRBG in its products – validation numbers 259, 27, and 24. While it’s not a default, why is it there at all? Their own security researchers raised alarms about it! It’s not like they even implemented all four algorithms in SP 800-90: they only implemented two of them, and one was DUAL_EC_DRBG. Before all this, I might attempt to be charitable about the matter… but with all of the evidence pointing the other direction, it’s time to draw uncomfortable conclusions regarding anyone involved in implementing DUAL_EC_DRBG.