A new Dual EC DRBG flaw

The dual elliptic curve deterministic random bit generator (Dual EC DRBG) cryptographic algorithm has a dubious history—it is believed to have been backdoored by the US National Security Agency (NSA)—but is mandated by the FIPS 140-2 US government cryptographic standard. That means that any cryptographic library project that is interested in getting FIPS 140-2 certified needs to implement the discredited random number algorithm. But, since certified libraries cannot change a single line—even to fix major, fatal bugs—having a non-working version of Dual EC DRBG may actually be the best defense against the backdoor. Interestingly, that is exactly where the OpenSSL project finds itself.

OpenSSL project manager Steve Marquess posted the tale to the openssl-announce mailing list on December 19. It is, he said, "an unusual bug report for an unusual situation". It turns out that the Dual EC DRBG implementation in OpenSSL is fatally flawed, to the point where using it at all will either crash or stall the program. Given that the FIPS-certified code cannot be changed without invalidating the certification, and that the bug has existed since the introduction of Dual EC DRBG into OpenSSL, it is clear that no one has actually used that algorithm from OpenSSL. It did, however, pass the testing required for the certification somehow.

It is also interesting to note that the financial sponsor of the feature adding support for Dual EC DRBG, who is not named, did so after the algorithm was already known to be questionable. It was part of a request to implement all of SP 800-90A, which is a suite of four DRBGs that Marquess called "more or less mandatory" for FIPS certification. At the time, the project recognized the "dubious reputation" for Dual EC DRBG, but also considers OpenSSL to be a comprehensive library and toolkit: "As such it implements many algorithms of varying strength and utility, from worthless to robust." Dual EC DRBG was not even enabled by default, but it was put into the library.

The bug was discovered by Stephen Checkoway and Matt Green of the Johns Hopkins University Information Security Institute, Marquess said. Though there is a one-line patch to fix the problem included with the bug report, there are no plans to apply it. Instead, OpenSSL will be removing the Dual EC DRBG code from its next FIPS-targeted version. The US National Institute of Standards and Technology (NIST), which oversees FIPS and other government cryptography standards, has recently recommended not using Dual EC DRBG [PDF]. Since that recommendation, Dual EC DRBG has been disabled in OpenSSL anyway. Because there is essentially the same amount of testing required for fixing or removing the algorithm (for FIPS recertification), removal seems like the right course.

The problem stems from a requirement in FIPS that each block of output random numbers not match the previous block. It is, effectively, a crude test that the algorithm is actually producing random-looking data (and not repeating blocks of zeroes, for example). When there is no previous block to compare against, OpenSSL generates one that should be discarded after the comparison. But the Dual EC DRBG implementation botched the discard operation by not updating the state correctly.

Dual EC DRBG was under suspicion for other reasons even before it was adopted by NIST in 2006. In 2007, Bruce Schneier raised the alarm about an NSA backdoor in the algorithm. For one thing, Dual EC DRBG is different than the other three algorithms specified in SP 800-90A in that it is three orders of magnitude slower and that it was only added at the behest of the NSA. It was found that the elliptic curve constants chosen by NIST (with unspecified provenance) could be combined with another set of numbers—not generally known, except possibly by the NSA—to predict the output of the random number generator after observing 32 bytes of its output. Those secret numbers could have been generated at the same time the EC constants were, but it is unknown if they actually were.

The NIST standards were a bit unclear about whether the EC constants were required, but Marquess noted that the testing lab required using the constants (aka "points"):

So, what we have here is a likely backdoored algorithm that almost no one used (evidently unless they were paid $10 million) added to an open-source cryptography library funded by money from an unnamed third party. After "rigorous" testing, that code was certified as conforming to a US government cryptographic standard, but it never actually worked at all. According to Marquess: "Frankly the FIPS 140-2 validation testing isn't very useful for catching 'real world' problems."

It is almost comical (except to RSA's BSafe customers, anyway), but it does highlight some fundamental problems in the US (and probably other) government certification process. Not finding this bug is one thing, but not being able to fix it (or, more importantly, being unable to fix a problem in an actually useful cryptographic algorithm) without spending lots of time and money on recertification seems entirely broken. The ham-fisted way that the NSA went about putting the backdoor into the standard is also nearly amusing. If all its attempts were similarly obvious and noisy, we wouldn't have much to worry about—unfortunately that seems unlikely to be the case.

One other thing to possibly consider: did someone on the OpenSSL project "backdoor" the Dual EC DRBG implementation such that it could never work, but would pass the certification tests? Given what was known about the algorithm and how unlikely it was that it would ever be used by anyone with any cryptographic savvy, it may have seemed like a nice safeguard to effectively disable the backdoor. Perhaps that is far-fetched, but one can certainly imagine a developer being irritated by having to implement the NSA's broken random number generator—and doing something about it. Either way, we will probably never really know for sure.