Dual_EC_DRBG

from Wikipedia, the free encyclopedia

Dual_EC_DRBG ( English Dual E lliptic C urve D eterministic R andom B it G enerator ) is a cryptographically secure random number generator (PRNG) developed and published by the National Security Agency . Despite public criticism, the procedure was one of four (now three) PRNGs standardized in the NIST Special Publication 800-90. Shortly after its publication by NIST in 2007, there were suspicions that the algorithm contained a kleptographic backdoor , which proved to be true in September 2013.

safety

The reason for the absorption of dual_ec_drbg in the standard, its safety that a difficult number theory problem that Decisional Diffie-Hellman assumption (DDH) in the used elliptic curve reduce leaves. The additional confidence gained in the security of the method can in some cases justify the loss of speed by three orders of magnitude compared to the other three standardized methods. Assuming DDH is a difficult problem, the intermediate values ​​produced by the method, a sequence of points on the elliptic curve, are indistinguishable from a sequence of random points.

After the standard was published, researchers found two security issues:

  • The bit sequence that is generated from the point sequence can be differentiated for some parameters from a uniformly distributed random bit sequence. The PRNG is therefore unsuitable for use as a stream cipher and for other applications.
  • The security of the PRNG is based on the assumption that the DDH problem is difficult. For the curve recommended by NIST, however, there is the possibility that the parameters of the curve were selected on the basis of additional values ​​that make solving this problem much easier (see the next section).

controversy

In August 2007, Dan Shumow and Niels Ferguson warned that the algorithm had a weakness that could be exploited as a backdoor. PRNGs are a widely used cryptographic primitive , and this weakness can be exploited to break any cryptographic method that is based on Dual EC.

Tanja Lange and Daniel Bernstein found the first description of the back door in 2013 - expressly directed against the TLS protocol - in a preliminary patent application from Certicom dated January 21, 2005.

A point P is specified on the curve defined in the standard , which creates the cyclic group . In addition, a point Q is defined. Since the group is cyclic, there is a number d , with Q = dP , the discrete logarithm from Q to base P in the group written here additively. Shumow and Ferguson were able to show that knowing d would allow an attacker to break the procedure. It is not clear how these constants P and Q were chosen. If Q was chosen to be truly random, it is practically impossible to compute d . However, there is a possibility that P and d were chosen and Q = dP was calculated. In this case, whoever chose the two points could break any instance of the PRNG on this curve. In Appendix A of the standard, however, a method is defined how a separate curve can be generated with self-selected constants.

According to a report in the New York Times in September 2013, the revelations of whistle-blower Edward Snowden secret memos confirm the US - foreign intelligence NSA that this vulnerability through the NSA had been developed. In mid-September 2013, the company RSA Security , among other things the provider of the cryptography program library RSA BSafe and the authentication system SecurID , published a recommendation to developers who work with their program libraries not to continue using the Dual_EC_DRBG contained therein as a standard and instead to use a different random number generator. This affects all applications that use RSA BSafe . The standardization institute NIST has announced that it will subject the standard to a new review. The implementation list of the US standardization authority NIST gives an overview of the random number generators used by implementations.

After a consultation phase, NIST decided to remove Dual_EC_DRBG from the standard. On April 21, 2014, NIST published a draft for a revised version of the SP 800-90A standard that no longer contains Dual_EC_DRBG.

Individual evidence

  1. ↑ National Institute of Standards and Technology (Ed.): NIST SP 800-90: Recommendations for Random Number Generation Using Deterministic Random Bit Generators (Revised) . 2007 ( nist.gov [PDF]).
  2. ↑ a b Bruce Schneier : Did NSA Put a Secret Backdoor in New Encryption Standard? Wired , November 15, 2007, accessed October 9, 2011 .
  3. ↑ a b Kristian Gjøsteen: Comments on Dual-EC-DRBG / NIST SP 800-90 . 2006 ( ntnu.no [PDF]). Comments on Dual-EC-DRBG / NIST SP 800-90 ( Memento of the original from May 25, 2011 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice.  @1@ 2Template: Webachiv / IABot / www.math.ntnu.no
  4. ^ Daniel RL Brown: Conjectured Security of the ANSI-NIST Elliptic Curve RNG . 2006 ( iacr.org ).
  5. ^ A b Daniel RL Brown and Kristian Gjøsteen: A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator . In: CRYPTO 2007 . tape 4622 . Springer, 2007, p. 466-481 , doi : 10.1007 / 978-3-540-74143-5_26 ( iacr.org ).
  6. ↑ Berry Schoenmakers and Andrey Sidorenko: Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator . 2006 ( iacr.org ).
  7. ↑ Dan Shumow and Niels Ferguson : On the Possibility of a Back Door in the NIST SP800-90 Dual EC PRNG . In: CRYPTO Rump Session 2007 . 2007 ( yp.to [PDF]).
  8. ↑ http://www.golem.de/news/dual-ec-das-patent-auf-die-nsa-hintertuer-1406-107219.html
  9. ^ Matthew D. Green: The Many Flaws of Dual_EC_DRBG
  10. ↑ Aris Adamantiadis: Dual_Ec_Drbg backdoor: a proof of concept , April 28, 2014.
  11. ↑ http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=3
  12. ↑ Wired : RSA Tells Its Developer Customers: Stop Using NSA-Linked Algorithm , September 19, 2013.
  13. ^ Zeit Online : NSA hacks cryptography: Security company RSA warns of itself , September 20, 2013.
  14. ↑ NIST : List of Implementation of Random Number Generation Methods , April 28, 2014.
  15. ↑ Archive link ( Memento of the original from July 23, 2014 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  @1@ 2Template: Webachiv / IABot / csrc.nist.gov