Dual_EC_DRBG

Dual_EC_DRBG

Dual_EC_DRBG or Dual Elliptic Curve Deterministic Random Bit Generator[1] is a controversial pseudorandom number generator (PRNG) designed and published by the National Security Agency. It is based on the elliptic curve discrete logarithm problem (ECDLP) and is one of the four PRNGs standardized in the NIST Special Publication 800-90. Shortly after the NIST publication, it was suggested that the RNG could be a kleptographic NSA backdoor.[2]

Contents

Security

This stated purpose of including the Dual_EC_DRBG in NIST SP 800-90 is that its security is based on a hard problem from number theory, such as the elliptic curve Decision Diffie-Hellman problem. Given the importance of having secure random number generators in cryptography, in certain cases it may be desirable to sacrifice speed for security.

Subsequent to publication of the Dual_EC_DRBG algorithm, various researchers have reported certain security issues with the properties of the Dual_EC_DRBG:

  • The intermediate values it generates, a sequence of elliptic curve points, should, under certain reasonable assumptions, such as the Decision Diffie-Hellman problem, be indistinguishable from uniformly random elliptic curve points.[3][4][5]
  • The sequence of bits generated from the Dual_EC_DRBG, under certain parameter choices, can be distinguished from uniformly random bits, making its output unsuitable for use as a stream cipher, and, arguably, for more general use.[3][5][6]
  • Its security requires that a certain problem be hard, such as the computational Diffie-Hellman problem, but one of the recommended configurations of the Dual_EC_DRBG permits the possibility that a key, which facilitates solution of the problem, has been retained. See the Controversy section for more discussion.

Controversy

This PRNG has been controversial because it was published in the NIST standard despite being three orders of magnitude slower than the other three standardized algorithms, and containing several weaknesses which have been identified since its standardization.[2]

In August 2007, Dan Shumow and Niels Ferguson discovered that the algorithm has a vulnerability which could be used as a backdoor. Given the wide applications of PRNGs in cryptography, this vulnerability could be used to defeat practically any cryptosystem relying on it. The algorithm uses several constants which determine the output; it is possible that these constants are deliberately crafted in a way that allows the designer to predict its output.[2][7]

This backdoor would work analogously to public-key encryption: the designer of the algorithm generates a keypair consisting of the public and private key; the public key is published as the algorithm's constants, while the private key is kept secret. Whenever the algorithm is being used, the holder of the private key can decrypt its output, revealing the state of the PRNG, and thereby allowing him to predict any future output. Yet for third parties, there is no way to prove the existence (or non-existence) of the private key. However, Appendix A.2 of the NIST document, which describes the weakness, does contain a method of generating a new keypair which will repair the backdoor if it exists.

See also

References


External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Dual_EC_DRBG — (Dual Elliptic Curve Deterministic Random Bit Generator) ist ein von der National Security Agency entwickelter und veröffentlichter kryptographisch sicherer Zufallszahlengenerator (PRNG). Das Verfahren ist eines von vier in der NIST Special… …   Deutsch Wikipedia

  • Dual EC DRBG — is a controversial pseudorandom number generator (PRNG) designed and published by the National Security Agency. It is based on the elliptic curve discrete logarithm problem (ECDLP) and is one of the four PRNGs standardized in the NIST Special… …   Wikipedia

  • Dual EC DRBG — алгоритм генерации псевдослучайных чисел, разработанный Агентством национальной безопасности США. Алгоритм основан на использовании эллиптических кривых. Это один из четырёх ГПСЧ, стандартизованных в NIST Special Publication 800 90.[1] Вскоре… …   Википедия

  • Microsoft CryptoAPI — The Cryptographic Application Programming Interface (also known variously as CryptoAPI, Microsoft Cryptography API, MS CAPI or simply CAPI) is an application programming interface included with Microsoft Windows operating systems that provides… …   Wikipedia

  • Random number generator attack — The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic… …   Wikipedia

  • Bruce Schneier — (2007) Bruce Schneier (* 15. Januar 1963 in New York) ist ein US amerikanischer Experte für Kryptographie und Computersicherheit, Autor verschiedener Bücher über Computersicherheit und Mitgründer der Computersicherheitsfirma Counterpane Internet… …   Deutsch Wikipedia

  • Niels Ferguson — (* 10. Dezember 1965 in Eindhoven) ist ein niederländischer Kryptograph. Er arbeitet zur Zeit für Microsoft. Ferguson hat am Hash Algorithmus Skein, am Stromchiffrierer Helix und am WLAN Sicherheitsstandard WPA2 mitgewirkt. Weiterhin hat er 1999… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”