Dual_EC_DRBG

Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) is a standard developed by the National Security Agency and published cryptographically secure random number generator ( PRNG ). The method is one of four in the NIST Special Publication 800-90 standard PRNGs. Shortly after the publication by NIST suspicions were voiced that the algorithm contains a kleptographische backdoor.

Security

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

Following the publication of standards researchers found two security problems:

• The bit sequence is generated from the sequence of points can be distinguished for certain parameters of a uniformly distributed random sequence of bits. Thus the PRNG for use as stream cipher, and for other applications is not suitable.
• The security of the PRNG is based on the assumption that the DDH problem is difficult. But it is possible for the recommended by NIST curve, the parameters of the curve were chosen on the basis of other values ​​that facilitate solving this problem significantly (see the next section).

Controversy

In August 2007, Dan discovered Shumow and Niels Ferguson, that the algorithm has a weakness that could be exploited as a backdoor. Since PRNGs are a widely -used cryptographic primitive, this weakness could be exploited to break any cryptographic method, which relies on.

To as defined in the standard curve, a point P is defined that generates the cyclic group. In addition, a point Q is defined. Since the group is cyclic, a number d, where Q = dP, the discrete logarithm of Q to the base P exists in the here additively written group. Shumow and Ferguson were able to show that the knowledge of d would allow an attacker to break the process. It is not clear how these constants P and Q were chosen. If Q was truly chosen at random, it is virtually impossible to calculate d. However, there is the possibility that P were chosen and D and Q = dP is calculated. In that case, the one who chose the two points, breaking each instance of the PRNG on this curve. In Appendix A of the standard, however, a method is defined as a separate curve with self-chosen constants can be generated.

According to a report in the New York Times in September 2013 by the revelations of the whistleblower Edward Snowden confirm secret memos of the U.S. Foreign Intelligence NSA that this vulnerability had been developed by the NSA. Mid- September 2013, the company released RSA Security, including providers of cryptography program library RSA BSafe and the authentication system SecurID, a recommendation to developers who work with their libraries, not to use the Dual_EC_DRBG contained therein as the standard further and instead use a different random number generator. This affects all applications that rely on RSA BSafe. The NIST Standards Institute has announced plans to undergo the standard to a new review.