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:
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 2b possible elements of Fp corresponding to r. On average, only every second field element extends to a point (x3+ax+b needs to be a square), so there are about 2b−1 candidate points R which include sQ. Note that all computations will only involve the x-coordinates, so we do not distinguish between R and −R. 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 2b−1 times. If the output used for comparing is from a separate Dual EC call, another round of s=x(sP) is needed before computing r. Also note that not all bits of the second block are required. If at least b bits of the second block are available chances are very low that more than one candidate inner state matches the next output. Attack costs for NIST P-256For 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 216 attempts to recover x(sQ) and for each valid x-coordinate 2 scalar multiplications. If one stops when the inner state matching the next block of output is obtained one needs on average 215 point reconstructions and 214 times 2 scalar multiplications. 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 should be used. 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 shall be used in applications requiring certification under FIPS 140-2. 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)
Last modified: 2014.03.30 |