Last Friday, Joseph Menn from Reuters
published an article claiming that RSA, the pioneering security firm and division of EMC, accepted $10 million dollars to include the Dual EC random number generator as the
default in their flagship BSAFE library. I’ve
written a bit about Dual EC on this blog, so readers will know that I don’t think highly of it. For one thing, it’s a rotten choice for a commercial product, due to its lousy software performance. Much worse: it may introduce a
practical backdoor into any system that uses it.
Given the numerous problems with Dual EC it’s baffling that RSA would select this particular generator as the default for their software. It’s particularly strange given that BSAFE is designed for use in Java-based and embedded systems where performance truly is at a premium. And none of this can be explained by the needs of a single RSA customer, since those needs could be satisfied merely by making BSAFE an option, rather than the default.
Of course there have been many people who had viewed RSA’s decision as potentially malicious. Unsupported rumors have been floating around since long before Reuters got involved. What’s new this time is that RSA insiders appear to be going on the record.
I suppose time will tell how the industry reacts to this news. In the interim I have a few small facts to add to the discussion, so I thought I’d sketch them out in this post.
#1: Dual_EC_DRBG’s ‘backdoor’ was known as of January 2005
It’s widely believed that the ‘vulnerability’ in Dual_EC was first identified by Microsoft employees
Dan Shumow and Niels Ferguson in the summer of 2007.
Tanja Lange (and
nymble) recently tipped me off to the fact that this isn’t precisely true.
In point of fact, the possibility of a backdoor was known to at least some members of the ANSI X9.82 standardization committee as far back in January 2005. This surprising news comes via a patent application filed by Certicom employees Dan Brown and Scott Vanstone. The application claims a priority date of January 2005. Here’s the scary bit:
If P and Q are established in a security domain controlled by an administrator, and the entity who generates Q for the domain does so with knowledge of e (or indirectly via knowledge of d). The administrator will have an escrow key for every ECRNG that follows that standard.
Escrow keys are known to have advantages in some contexts. They can provide a backup functionality. If a cryptographic key is lost, then data encrypted under that key is also lost. However, encryption keys are generally the output of random number generators. Therefore, if the ECRNG is used to generate the encryption key K, then it may be possible that the escrow key e can be used to recover the encryption key K. Escrow keys can provide other functionality, such as for use in a wiretap. In this case, trusted law enforcement agents may need to decrypt encrypted traffic of criminals, and to do this they may want to be able to use an escrow key to recover an encryption key.
…
For example, in the SSL and TLS protocols, which are used for securing web (HTTP) traffic, a client and server perform a handshake in which their first actions are to exchange random values sent in the clear.
The patent also describes a number of ways to close the backdoor in Dual_EC_DRBG. Indeed, it may be due to Brown and Vanstone that the NIST standard includes an alternative method to close the backdoor (by generating a random Q point).
The existence of this patent does not mean that Brown and Vanstone were responsible for Dual EC. In fact, the generator appears to be an NSA invention, and may date back to the early 2000s. What this patent demonstrates is that some members of the ANSI committee, of which RSA was also a member, had reason to at least suspect that Dual EC could be used to create a wiretapping backdoor. (Update: John Kelsey confirms this.) It would be curious to know how widely this information was shared, and whether anyone on the committee ever inquired as to the provenance of the default parameters.
#2. Dual_EC_DRBG is not really a NIST standard
This is hardly a secret, but it’s something that hasn’t been widely acknowledged in the press. Dual_EC_DRBG is generally viewed as a NIST standard, since it was published in NIST Special Publication 800-90. But that’s not the only place it appears, nor was it developed at NIST.
A complete history of Dual_EC_DRBG would begin with NSA’s drive to include it in the ANSI X9.82 DRBG standard, with a standardization process kicked off in the early 2000s. The draft ANSI standard includes Dual_EC_DRBG with all of the known parameters, along with several additional elliptic curve parameters that were not included in the NIST standards.
|
| Members of the ANSI X9F1 Tool Standards and Guidelines Group which wrote ANSI X9.82. |
However you’ll also find Dual_EC_DRBG in the international standard ISO 18031. In other words, Dual EC was widely propagated in numerous standards long before NIST finalized it, and it’s hardly limited to US borders. The ANSI and ISO drafts are in some sense worse, since they don’t include a technique for generating your own Q parameter.
#3. Dual_EC_DRBG is not the only asymmetric random number generator in the ANSI and ISO standards
Cryptographers generally think of Dual EC as the only ‘public key’ random number generator to be widely standardized. We also point to NSA’s generation of the public parameters as evidence that Dual_EC may be compromised.
But in fact, the ANSI X9.82 and ISO standards each include a second generator based on public key cryptographic techniques. And like Dual EC, this one ships with a complete set of default parameters! The additional generator is based on an algorithm due to Micali and Schnorr, and relies for its security on assumptions related to the hardness of factoring large composite numbers. It requires an RSA-type modulus, several of which are conveniently provided in the specification.
|
| Two default MS-DRBG moduli from the ISO 18031 specification. |
There’s no reason to suspect that MS-DRBG is used by any real products, let alone that there’s a backdoor in the standard. In fact, there’s a curious fact about it: it’s not obvious from the public literature how one would attack the generator even if one knew the factorization of the n values above — though it seems intuitively likely that an attack does exist. Solving the problem, and finding a practical attack for known factorization, would be a fun project for an enthusiastic mathematician.
Since MS-DRBG comes from the same people who brought you Dual EC, if you are using it you might want to think twice.
deutrino
All Jonkman Microblog content and data are available under the