Dual EC DRBG



Vulnerability of the RNG ecosystem

Many organizations are involved in designing, evaluating, standardizing, selecting, implementing, and deploying RNGs. This ecosystem, the entire design-through-deployment process that eventually gives random numbers to users, is a broader attack target than any particular RNG. Papers analyzing the security of particular RNGs do not answer the question of whether this ecosystem is secure.

This web page considers an attack strategy against this ecosystem, including several synergistic stages, some of which do not appear to have been publicly considered before:

  • Design: Construct a PRNG that secretly contains a back door.
  • Evaluation: Publish statements that the PRNG is secure; if possible, publish statements that it is more secure than the alternatives. This is important because public evaluation increases the probability of standardization, selection, implementation, and deployment.
  • Standardization: Edit standards to include the PRNG. This is important because standardization increases the probability of selection, implementation, and deployment.
  • Standardization maintenance: Monitor changes to the PRNG standard, and counteract changes that make the PRNG more difficult to exploit.
  • Auxiliary standardization: If necessary modify other standards, such as networking standards, to make the PRNG easier to exploit.
  • Selection, implementation, and deployment: Modify cryptographic libraries to implement this PRNG, at least as an option but preferably as default, preferably with as many of the modifications as possible.
  • Attack optimization: Reduce the cost of computation required to exploit the back door, through algorithmic improvements and through influencing the way the PRNG is used in practice.

It is possible that Dual EC was part of a deliberate attack of this type. Specifically, each of the following events can be explained by such an attack:

  • Design: Shumow and Ferguson raised an alarm in 2007 regarding the ability of the Dual EC creators to insert a back door into Dual EC. News reports in 2013 appeared to confirm that Dual EC had been created by NSA with a back door.
  • Evaluation: Slides presented at a 2004 NIST workshop claim that number-theoretic RNGs provide "increased assurance". NIST SP800-90 contains several positive statements regarding the security of Dual EC, such as "The Dual_EC_DRBG is the only DRBG mechanism in this Recommendation whose security is related to a hard problem in number theory."
  • Standardization: Dual EC has been standardized by ANSI, ISO, and NIST. The standards were not withdrawn in response to public objections to the security of Dual EC from the cryptographic community in 2006 and 2007.
  • Standardization maintenance: There was a change from the June 2006 NIST Dual EC standard to the March 2007 NIST Dual EC standard. This site reports new security analysis from Bernstein, Checkoway, Green, and Lange with the following conclusions: the claimed security benefit of this change would also have been achieved by a simpler, faster change; from an attacker's perspective, the June 2006 standard contained an obstacle to Dual EC exploitation in some circumstances; the March 2007 standard removed this obstacle; the simpler change would not have removed this obstacle.
  • Auxiliary standardization: New analysis from Checkoway, Fredrikson, Niederhagen, Everspaugh, Green, Lange, Ristenpart, Bernstein, Maskiewicz, and Shacham shows that the exploitability of Dual EC in TLS depends on many TLS details. A proposed "Extended Random" TLS extension coauthored by NSA removes another obstacle to exploiting Dual EC in TLS, to the extent that the extension is used. This site reports new security analysis from Bernstein and Lange that does not support the claimed security benefit of this TLS extension.
  • Selection, implementation, and deployment: News reports in December 2013 indicated that NSA had paid RSA to implement Dual EC in their security library and to make it the default.
  • Attack optimization: New analysis from Checkoway, Fredrikson, Niederhagen, Everspaugh, Green, Lange, Ristenpart, Bernstein, Maskiewicz, and Shacham shows that the computations required to exploit Dual EC are considerably less expensive than indicated by previous analyses. These researchers demonstrate feasibility of exploiting Dual EC in several TLS libraries.

This case study is intended to help support followup analyses of ways to protect the ecosystem against attacks of this type. For these analyses, what matters is not determining whether any particular attacks have been carried out, but rather understanding the attacks that can be carried out. This site does not attempt to resolve questions such as whether Dual EC was in fact created with a back door, whether the March 2007 modification was in fact intended to remove an obstacle to exploiting this back door, or whether Extended Random was in fact intended to remove another obstacle. What matters is that the Dual EC designers did have the option of secretly including a back door, that the March 2007 modification removes an obstacle, and that Extended Random removes another obstacle.

Of course, security issues also arise for other cryptographic ecosystems, and for the broader security ecosystem.

Authors of this "Vulnerability of the RNG ecosystem" page (alphabetical order)




Last modified: 2014.07.07