Dual EC DRBG

2015.07.31: New paper "Dual EC: A Standardized Back Door".

Randomness is essential for secure cryptography. Random numbers are used for secret long-term keys, secret short-term keys, public "nonces" that must never repeat, secret nonces, and more. An attacker who can control these random numbers, or who can merely predict the secret random numbers, has the power to decrypt encrypted messages and forge authenticated messages.

Cryptographic users obtain random numbers from software and hardware devices called "random-number generators" (RNGs). This site collects new results on one RNG, Dual EC, and also provides detailed background on this RNG.

Dual EC was standardized by the American standardization bodies ANSI and NIST and by the International Organization for Standardization, ISO. Cryptographers raised alarms about undesirable properties of Dual EC, including a potential back door; these alarms began while the NIST standard was still a draft. In September 2013, the New York Times mentioned Dual EC as an example of NSA's Bullrun program. In response, NIST issued an official bulletin that "strongly recommends" against Dual EC. On 21 April 2014, NIST issued a draft revision of SP 800-90A removing Dual EC. The comment period lasted till 23 May 2014. On June 24, 2015, NIST published a Revision 1 of SP 800-90A. NIST's press release mentions the removal of Dual EC and comments "This algorithm has spawned controversy because of concerns that it might contain a weakness that attackers could exploit to predict the outcome of random number generation."

In February 2014, NIST issued a request for comments on the "principles, processes and procedures" behind NIST's "cryptographic standards development efforts". In May 2014, NIST's advisory committee "formed a panel of experts to assess NIST’s existing cryptographic standards and guidelines and the process by which they have been developed".

Summaries of subpages with new content

For details on the research credit stated in these summaries see the individual pages.

• Vulnerability of the RNG ecosystem
  There is a large ecosystem that eventually gives random numbers to users. This ecosystem includes designing, evaluating, standardizing, selecting, implementing, and deploying RNGs. This page considers a high-level attack strategy against the ecosystem.
• Certicom's patent applications regarding Dual EC key escrow
  Certicom has patents in multiple countries on Dual EC exploitation and Dual EC escrow avoidance. The patent filing history also shows that Certicom knew the Dual EC back door by 2005; NSA was informed of the Dual EC back door by 2005, even if they did not know it earlier; and the patent application, including examples of Dual EC exploitation, was publicly available in July 2006, just a month after SP800-90 was standardized. Research credit: Lange and an anonymous contributor.
• Modification in SP800-90 in March 2007
  In March 2007 the SP800-90 Dual EC standard was changed. The June 2006 version of Dual EC had an error from the attacker's perspective: the back door was difficult to exploit if the user incorporated "additional input" for each output block, even if the additional input was guessable. The March 2007 change fixed this error, allowing exploitability whether or not the user incorporated "additional input". The same change appears in the current version of ISO 18031. Research credit (alphabetical order): Bernstein, Checkoway, Green, Lange.
• Extended Random
  The proposed "Extended Random" TLS extension improves the exploitability of the Dual EC back door. The published security motivation for Extended Random is incorrect. Research credit for exploitability (alphabetical order): Checkoway and Green. Research credit for security analysis of the motivation (alphabetical order): Bernstein and Lange.
• Exploitability in TLS
  The basic Dual EC attack turns out to be highly oversimplified: it ignores critical limitations and variations in the amount of the PRNG output actually exposed in TLS, additional inputs to the PRNG, PRNG reseeding, alignment of PRNG outputs, and outright bugs in Dual EC implementations. Dual EC has different levels of exploitability in RSA BSAFE, Microsoft SChannel, and OpenSSL. Research credit: Checkoway, Fredrikson, Niederhagen, Everspaugh, Green, Lange, Ristenpart, Bernstein, Maskiewicz, and Shacham.
• Performance of the attacks
  Detailed cost analysis for Dual EC exploitation in TLS using BSAFE-C, BSAFE-Java, SChannel, and OpenSSL-fixed. The basic computations are considerably less expensive than indicated in the previous literature. Research credit: Checkoway, Fredrikson, Niederhagen, Everspaugh, Green, Lange, Ristenpart, Bernstein, Maskiewicz, and Shacham.





Last modified: 2015.07.31