Dual EC DRBG
Modification in SP800-90 in March 2007
In March 2007 the SP800-90 Dual EC standard was changed. Lange noticed in January 2014 that there was a change to the standard in 2007. When she reported this to Green he said that he and Checkoway had previously noticed the step in the algorithm which constituted the change and realized that it is important for the back door to function, without realizing that it was a later add-on to the standard. Bernstein found the 2006 version of the standard. The security impact of this change reported on this page was further analyzed by Bernstein, Checkoway, Green, and Lange.
The June 2006 version of Dual EC had an error from the attacker's perspective: the back door was difficult to exploit if the user incorporated "additional input" for each output block, even if the additional input was guessable. The March 2007 change fixed this error, allowing exploitability whether or not the user incorporated "additional input". The same change appears in the current version of ISO 18031. The rest of this page explains the details.
The broken back door
As pointed out in our description of Dual EC, the SP 800-90 diagram given as an illustration of the working of Dual EC does not match the SP 800-90 specification of the steps in Dual EC. The steps include an extra scalar multiplication s=x(sP) at the end of each call.
This extra scalar multiplication did not appear in the June 2006 version of Dual EC. In that version, a series of one-block outputs with additional inputs on each call was generated as follows:
Assume that an attacker knows an integer d such that P = dQ. If the ⊕Hash(input) is omitted then the attacker inspects φ(x(s1 Q)), guesses the missing bits of s1 Q, computes d(s1 Q) = s1 P = t2 P, and verifies the next output. However, when ⊕Hash(input) is included, the attacker is stuck with d(s1 Q) = s1 P. Even when the attacker knows the additional input, the attacker has no obvious way to compute t2 P = (s1⊕Hash(input)) P or the subsequent state s2.
Note that there is an obvious way for the attacker to compute (s1+Hash(input)) P: namely, multiply the known Hash(input) by P and add the known s1 P. However, s1⊕Hash(input) is not the same as an integer addition s1+Hash(input): integer addition includes carries (depending on how many bits of Hash(input) are set at the same positions as bits of s1), and the attacker is forced to guess those carries. This becomes much faster if Hash(input) has Hamming weight far from average, but this does not happen very often: it requires the attacker to be lucky or to control the input.
To summarize, between June 2006 and March 2007 the Dual EC back door was broken for applications that used additional input for every output block.
In the March 2007 (and current) version of Dual EC, a series of one-block outputs with additional inputs on each call is generated as follows:
Now the attacker guesses the missing bits of s1 Q, computes s1 P using d, computes s2, computes t3 using the known additional input, computes s3, and verifies the next output. The back door relies critically on having the output computation sQ followed immediately by the state update sP, for the same value of s, so that the back-door information d can be used to obtain d(sQ) = sP.
To summarize, the March 2007 change reestablished the back door even for applications that used additional input, as long as the attacker could guess the additional input.
The official reason for the change
The official explanation for the March 2007 change, and therefore also for the difference between diagram and algorithmic description, is the following snippet which appears on page 124 of the March 2007 version of 800-90:
"Backtracking" sounds like a very serious problem with an RNG, allowing an attacker to work backwards from an output to all the previous outputs. Dual EC has never had this problem. Even an attacker who knows the Dual EC back door is only able to run Dual EC forwards, not backwards.
What NIST actually means by "backtracking" is working backwards from the current RNG state to some information about previous outputs. This is a much more obscure issue. It is not at all clear how an attacker would obtain access to an RNG state without also obtaining access to long-term cryptographic keys; such problems need to be fixed by better storage of secret data, not by tweaking RNGs.
The following comments assume that some applications are concerned with this obscure issue. The June 2006 version of Dual EC obviously allows working backwards from the current state s to one previous output r: an attacker who obtains access to the current state s can simply compute r from s the same way that the application did. Dual EC does not allow backtracking to earlier outputs, so these applications can protect themselves by simply generating and discarding an extra output block.
An obvious improvement to the design of Dual EC, incidentally eliminating this obscure issue, would be to simply reverse the order of computing r and s (matching how typical DRBGs work), so that the old state is replaced immediately after it is used to generate output rather than immediately before:
This provides full "backtracking resistance" and (in this situation of one output block for each call) is 1.5x more efficient than the March 2007 version of Dual EC. From an attacker's perspective the March 2007 version of Dual EC is much more satisfactory because it fixes the back door.
Intent or accident?
It is unclear whether the March 2007 change was introduced with the purpose of patching the back door. It certainly had the consequence of patching it.
It is also not clear whether NIST seriously considered the "backtracking resistance" of Dual EC and more efficient methods to provide "backtracking resistance" for Dual EC. Note that "backtracking resistance" is in direct conflict with the "health tests" required by FIPS: those tests require the previous RNG state (including sQ for Dual EC) to be stored in memory, eliminating any possible security provided by "backtracking resistance". A public statement by NIST about the history of this modification would be helpful.
Our current theory is as follows. NSA's first version of Dual EC did not support "additional input" and was always exploitable. NIST, when standardizing Dual EC, was not aware of the back door and incorporated "additional input" for consistency with other DRBGs. When NSA realized that "additional input" broke the back door, NSA convinced NIST to update the Dual EC standard.
Authors of this "Modification in SP800-90 in March 2007" page (alphabetical order)
Last modified: 2014.04.01