## Dual EC DRBG |

## The basic back doorAt the rump session of Crypto 2007, Dan Shumow and Niels Ferguson announced that Dual EC allowed the following attack strategy: - Use a secret number (as explained below) to generate the Dual EC parameter P, or alternatively to generate the Dual EC parameter Q. This requires the attacker to have input into the specification of the Dual EC parameters.
- Given this secret number and 32 bytes of Dual EC output (for example, via public nonces), perform a feasible computation (explained below) to figure out subsequent Dual EC outputs (for example, secret keys).
Other people had observed the same attack strategy but had not drawn public attention to it. Kelsey states in slides from December 2013 that the "Issue was first raised in an X9 meeting". ## DetailsHere are the details of the basic attack, using the same notation as the Description of Dual EC. A designer choosing P and Q can choose them so that the discrete logarithm of P to the base Q is known to the designer, i.e., P=dQ where d is known. If P is fixed first this is done by computing Q=eP for some value e and then computing d as the inverse of e modulo the order of P. For each of the Dual EC curves, the order of P is a prime, so this inverse exists and is efficiently computable. Take the first block of Dual EC output, i.e., r=φ(x(sQ)).
There are b bits missing from x(sQ) and
so there are 2 For each candidate R, compute dR. If R=sQ then dR=dsQ=sP, which would be the next multiple of P computed in Dual EC. To check whether R was the correct guess, compute s=x(dR) and then r=φ(x(sQ)) and compare it to the next block of Dual EC output. If this matches there is a good chance that the candidate R was correct, and then following the normal Dual EC computation produces all further outputs. The computation of s=x(dsQ) matches the diagonal lines in the back-door schematic; this computation gives the next inner state. There is no need to start with the very first part of Dual EC output.
Generally two consecutive blocks of output are sufficient to recover the state
at the cost of computing s=x(dR) and r=φ(x(sQ)) about
2 ## Attack costs for NIST P-256
For Dual EC instantiated with NIST P-256 the standard truncation b is
specified as 16. This means that out of the 256 bits of x(sQ) the top
240 bits are output. Recovering sQ from φ(x(sQ)) takes at
most 2 ## Alternatives within the Dual EC frameworkThe NIST SP 800-90 standard describes the possibility of implementing Dual EC with alternative points [Appendix 2.1.1: "Generating Alternative P, Q"] and explains how to choose points verifiably at random. For implementations deploying such points it requires extra tests ["A.2.2 Additional Self-testing Required for Alternative P, Q"]. However, the standard discourages use of alternative points ["A.2 Using Alternative Points in the Dual_EC_DRBG"]: To avoid using potentially weak points, the points specified in Appendix A.1 Furthermore, the standard prohibits FIPS validation of implementations using alternative points ["A.1 Constants for the Dual_EC_DRBG"]: One of the following NIST approved curves with associated points Kelsey made the following statement in slides from December 2013 regarding the use of alternative points: "As far as we know, nobody actually did this." ## Authors of this "The basic back door" page (alphabetical order)- Daniel J. Bernstein, University of Illinois at Chicago and Technische Universiteit Eindhoven
- Tanja Lange, Technische Universiteit Eindhoven
- Ruben Niederhagen, Technische Universiteit Eindhoven
Last modified: 2014.03.30 |