in Dual EC, NSA, RNGs 1,139 Words

A few more notes on NSA random number generators

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 3a7ac-thomas_adversaryDual 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.

18 thoughts on “A few more notes on NSA random number generators”

  1. There has been some discussion in the IETF's CFRG regarding Dual_EC_DRBG (http://www.ietf.org/mail-archive/web/cfrg/current/threads.html#03651).

    What is your opinion on Dan Brown's assertion that Dual_EC_DRBG has been mischaracterized: “Dual_EC_DRBG, as specified in NIST SP 800-90A and ANSI X9.82-3, allows an alternative choice of constants P and Q. As far as I know, the alternatives do not admit a known feasible backdoor. In my view, it is incorrect to imply that Dual_EC_DRBG always has a backdoor, though I admit a wording to qualify the affected cases may be awkward” ?

  2. And where do the NIST P-224/256/384 curves come from? It seems strange that everyone is enabling those curves on their TLS implementations, given what we know about Dual_EC.

  3. From a corporate point of view, the existance of a backdoor (on the asssumption that it's controlled by the NSA), isn't such a big deal. Corporate IT Security want to keep out competitors, foreign entities, and the like. If the NSA is rummaging through the secret information, it's probably about 87th on the list of concerns.

    I doubt that you'll see a panic in the hallways of Corporate America. Unless they're cheating on their taxes; so maybe most of them.

  4. It is a problem for the corporations who are trying to sell hardware or software that comes with NSA backdoors, and now the whole world assumes they do anyway.

  8. > What is your opinion on Dan Brown's assertion that Dual_EC_DRBG has been mischaracterized

    To start with, point 7) is wrong. Dual_EC_DRBG has been shown to be insecure because of the too large amount of bits leaked from the X coordinate.

    But generally it seems ridiculous to argue that the prechosen P and Q are not a backdoor, because implementers could choose their own P and Q. Especially since the standard stated you had to use the prechosen P and Q.

    If the standard had specifically said that the prechosen P and Q were backdored by NSA, then it would have been acceptable. But they just happened to forget to mention that little fact.

    To me, Dan Brown seems to be either a troll, or work for NSA.

  9. Ah, the email you link to is by Daniel Brown, who were on the ANSI X9F1 group. I bet he vouched for the standard, and is just trying to cover his own ass by arguing that letting the standard being approved was OK, with the argument that nobody would be stupid enough to use the obviously suspect P and Q.

    So his obviously bad faith arguments are just ass-covering, and not trolling or as a puppet for NSA .

  10. Corporate IT Security want to keep out competitors, foreign entities, and the like.

    The other shiny side of that Corporate IT Security COIN is the need to discover more advanced contemporaries with greater security arrangements/virtual protection.

    Although that/they may most probably be identified by simple stenographically coded text message exchange between/across peering networks/hacked sites/monitored and/or mentored communications channels, for not all competitors realise value in being solely adversarial with some choosing instead to make themselves known at required levels to others of a similar ilk, to beta test compatibility issues in order to progress and confirm virtually secure protection parameters in the applied protocols.

  11. And the same Dan Brown who published the patent describing in great detail and accuracy the NSA backdoor in Januar 2005, and the same Dan Brown who published the security reduction with Gjøsteen (with appropriate caveats).

    That Dan Brown now seems to think he has to cover his ass is interesting.

  12. And now that I remember it. I was skimming the various response papers to the 2005 NIST draft publication, and I was struck by a big difference. The paper from Kristian Gjøsteen concluded (in what seemed reasonable to me)

    > While the practical impact of these results are modest, it is hard to see how these flaws would be acceptable in a pseudo-random bit generator based on symmetric cryptographic primitives. They should not be accepted in a generator based on number-theoretic assumptions.

    And the paper from Berry Schoenmakers and Andrey Sidorenko concluded (which also seemed reasonable to me)

    > Our experimental results and also empirical argument show that the DEC PRG is insecure.

    The paper from Brown seems to ignore the actual Dual_EC_DRBG, and talks about a fixed version of Dual_EC_DRBG with the too small bit trunkation and chosen P and Q backdoor fixed. With his ideal fixed Dual_EC_DRBG, he concludes with a glowing review (which seems far too positive to me):

    > The ECRNG has both proven number-theoretic-based security and higher efficiency than many other RNGs with similar security properties. Random numbers play such an essential in cryptography, that implementers should always choose them to be as secure as possible. Therefore, the ECRNG should be a serious consideration, and its high efficiency makes it suitable even for constrained environments.

    Which is fine I suppose, but the title of the paper specifically says “Conjectured Security of the ANSI-NIST Elliptic Curve RNG”, so it seems very strange indeed that he does not more directly make conclusions about the actual Dual_EC_DRBG, which he knows to be flawed (remember Brown's patent, and Gjøsteen's paper which showed Dual_EC_DRBG to be a poor CSPRNG).

    It also seems very strange to me that Brown does not mention the backdoor he filed a patent for more directly. The need for Q to be random is mentioned, but only passingly. And the chosen Q attack is not tied together with the too small bit truncation issue, even though Brown mentioned this in his patent.

    Matthew Green wrote “The existence of this patent does not mean that Brown and Vanstone were responsible for Dual_EC”. But the more I read Brown's comments, the more I get the feeling that he is glossing over the backdoor. Note that Brown works for Certicom, which is the main owner of ECC patents. Brown _must_ have basically known that the NSA backdoor was in the standard, at the time in January 2005, why else the low bit truncation and prechosen P and Q. And he would have had every opportunity to suggest an easy fix. But Brown let it become approved anyway – that does not speak well for Certicom's dedication to users versus NSA. Was Brown as silent about the back door when talking to the ANSI committee as he was in the 2006 paper?

    Just to speculate wildly, Bruce Schneier did say that he did not trust ECC cryptography in view of Bullrun: http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance . Is there more to be found?

  13. You missed perhaps one of the most interesting parts of the patent:

    > [0041] Another alternative method for preventing a key escrow attack on the output of an ECRNG, shown in Figures 3 and 4 is to add a truncation function to ECRNG to truncate the ECRNG output to approximately half the length of a compressed elliptic curve point. Preferably, this operation is done in addition to the preferred method of Figure 1 and 2, however, it will be appreciated that it may be performed as a primary measure for preventing a key escrow attack. The benefit of truncation is that the list of R values associated with a single ECRNG output r is typically infeasible to search. For example, for a 160-bit elliptic curve group, the number of potential points R in the list is about 2^80, and searching the list would be about as hard as solving the discrete logarithm problem. The cost of this method is that the ECRNG is made half as efficient, because the output length is effectively halved.

    So Brown knew that the low amount of truncation made that part of the RNG reversible (and would in 2006 make his security derivation dependent on a higher amount of trucation than Dual_EC_DRBG specify). And that high truncation would stop the backdoor (“may be performed as a primary measure for preventing a key escrow attack”).

    So why did the ANSI standard group not make sure Dual_EC_DRBG truncated more bits, when one of their members were so well informed that it was necessary? Did Brown share his knowledge with the other members? Did Brown share his knowledge with the three members from RSA Security, who sometime in 2005 (patent is from January 2005) had accepted $10 million from NSA to make Dual_EC_DRBG the default in BSAFE?

    And how can Dan Brown still go around saying that Dual_EC_DRBG is amazing and unsubverted because of his security proof, when his security proof depends on truncating more output bits than is done in Dual_EC_DRBG?

  14. Woops, I meant to write that RSA Security made Dual_EC_DRBG the default sometime in 2004, not sometime in 2005, in the previous comment.

  15. Hmm, correction. The standard does actually allow you to output less bits (max_outlen), but says you “should” use the maximal max_outlen. The end of Appendix C argues why truncating more bits would be bad, but seems a bit hand-wavy (and I don't know enough to really understand it) – I would like to hear Matthew Greens analysis of that. Surely at least it is an error to say s<2^277, since s is at most the number of output bits?

  16. No I think you see definite unease and slow panic in corporate America because the CIA and NSA both are staffed with individuals that have ties to potential competitors and pass information to them. It's one thing when an high level official in the NSA passes your companies confidential info to his old classmate who is working at a hedge fund. It's another when his old classmate works for your competitor.

    Come on Aldrich Ames was living beyond his means for a decade before oops they found his money was coming from the Soviets and not some friendly government or corporation. Let that sink in, they knew he was dirty for ten years or more and let is slide, why is that? A lot of people at his level are dirty.

  17. Ok, I am pretty sure the argumentation for a high max_outlen in appendix C is obviously flawed. Truncating is the last step, and if outputting 128 of the least significant bits make the output nonrandom in some way, then obviously outputting more than 128 of the same bits will also be nonrandom. All the supposedly nonrandom lower bits will still be in the output, at perfectly regular and predictable intervals, so by any reasonable comprehensive definition of bitstring randomness if a low outlen is nonrandom, so is a high outlen.

    The argument in appendix C is therefore flawed in an obvious way. Since the high outlen is what makes the backdoor possible, I assume that this argument was added by NSA.

Comments are closed.