Dual_EC_DRBG: a standard with a possible back door

Dual_EC_DRBG is a random-number generator that appeared in a US government standard in 2006. Within a year people suspected it hid a back door only its designers could use, and NIST withdrew it after documents leaked in 2013 appeared to confirm the suspicion. It's the best-documented case of a cryptographic standard with a possible built-in flaw, and a clear lesson in two things: randomness underlies every key, and the numbers in a standard need explaining. We'll show how the back door works with a toy you can run, then what happened to the standard.

What a random-number generator has to do

Every key, nonce and salt in cryptography has to be unpredictable (random numbers in the browser). Real computers are deterministic, so a deterministic random bit generator (DRBG) takes a small amount of true randomness as a seed and expands it into as many bits as needed. If an attacker can predict its output, they can predict the keys made from it, however good the cipher is. That makes a DRBG a single point of failure for everything built on it.

The standard

NIST released a draft of Special Publication 800-90, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, in December 2005 and published it in June 2006. It specified four generators. Three were built from hash functions or block ciphers. The fourth, Dual_EC_DRBG, was built from elliptic curve arithmetic (elliptic curves), and it was an oddity from the start: slower than the others, with no stated reason to prefer it.

It works like this. The generator uses two fixed points on a curve, P and Q, written into the standard as constants with no explanation of where they came from. Its internal state is a number s. To produce output, it computes the point s·Q and outputs most of the bits of that point's x coordinate (it drops 16 of the 256 bits). To update its state, it computes s·P and takes the x coordinate of that as the new s. Multiplying a point by a number can't be undone (the discrete logarithm problem), so an observer who sees outputs shouldn't be able to find s and so shouldn't be able to predict the next output.

The back door

That holds only if nobody knows a relation between P and Q. Suppose whoever chose the constants started with Q, picked a secret number d, and set P = d·Q. Nothing in the published numbers would show it. Any two points on the curve are related by some d, and nobody can find it without solving the hard problem. But whoever holds d can do the following. Take one output of the generator. Rebuild the point R = s·Q from its x coordinate (for the 16 dropped bits, try all 65,536 possibilities and keep the candidates consistent with what follows). Multiply by d: d·R = d·s·Q = s·(d·Q) = s·P. That point's x coordinate is exactly the generator's next state, and from then on every future output can be computed. One output of the generator, about 30 bytes, is enough to know them all.

A toy you can run

The mechanism fits on a small curve. Take y² = x³ + 2x + 2 modulo 17 from the elliptic-curves page, whose 19 points are all multiples of Q = (5, 1). Choose the secret d = 7 and publish P = 7Q = (0, 6). Start the generator at s = 8. It outputs x(8Q) = 13, moves to s = x(8P) = 5, outputs x(5Q) = 9, moves to 10, outputs 7, then 10, 16, and so on. An outsider sees 13, 9, 7, 10, 16 and can't tell what's coming. The holder of d = 7 sees only the first output, 13. The points with x = 13 are (13, 7) and (13, 10), and 7·(13, 7) has x coordinate 5 (the same for the other, which is its negative). So the next state is 5, and the next output is x(5Q) = 9, exactly what the generator produces. The code does it in a few lines, and this site's tests run it from every starting state:

// A toy Dual_EC generator on the small curve y^2 = x^3 + 2x + 2 modulo 17, whose 19 points form one cycle around the generator Q = (5, 1).
// P is a secret multiple of Q: P = d Q. The generator keeps a number s. Each step outputs x(s Q) and moves to s = x(s P).
// Whoever knows d can take ONE output, rebuild the point s Q from it, multiply by d to get s P, and so know every later output. Toy sizes, never real.
var p = 17n, a = 2n;
function inv(x) { var r0 = p, r1 = ((x % p) + p) % p, t0 = 0n, t1 = 1n; while (r1) { var q = r0 / r1; [r0, r1] = [r1, r0 - q * r1]; [t0, t1] = [t1, t0 - q * t1]; } return (t0 % p + p) % p; }
function add(P, Q) {
  if (!P) return Q; if (!Q) return P;
  if (P.x === Q.x && (P.y + Q.y) % p === 0n) return null;
  var m = P.x === Q.x ? (3n * P.x * P.x + a) * inv(2n * P.y) : (Q.y - P.y) * inv(Q.x - P.x); m = ((m % p) + p) % p;
  var x = ((m * m - P.x - Q.x) % p + p) % p; return { x: x, y: ((m * (P.x - x) - P.y) % p + p) % p };
}
function mul(k, P) { var r = null; while (k > 0n) { if (k & 1n) r = add(r, P); P = add(P, P); k >>= 1n; } return r; }
var Q = { x: 5n, y: 1n }, d = 7n, P = mul(d, Q);                    // the designer picks d, publishes P and Q, and keeps d
function step(s) { return { out: mul(s, Q).x, next: mul(s, P).x }; }   // output x(sQ); new state x(sP)
function predictNext(out) {                                         // the attacker, who knows d, sees one output
  var guesses = [];
  for (var y = 0n; y < p; y++) if ((y * y - (out * out * out + a * out + 2n)) % p === 0n) guesses.push({ x: out, y: y });   // the point(s) with this x
  return guesses.map(function (R) { var S = mul(d, R); return S ? S.x : null; });    // d (sQ) = s (dQ) = sP, so its x is the next state
}

The toy is far too small to look like a random generator (it falls into a short cycle at once), and we show it only to display the mechanism. On a real 256-bit curve nothing about the mechanism changes. Only the holder of d can do it, and everyone else sees random bits.

Timeline of the suspicion

• June 2006: NIST publishes SP 800-90 with Dual_EC_DRBG (the draft came out in December 2005).
• August 2007: Dan Shumow and Niels Ferguson of Microsoft give an informal presentation showing that anyone who knew a number e with e·Q = P could predict the generator. Nobody had explained where the constants came from. Cryptographers advised against using it, and some products shipped it anyway.
• September 5, 2013: Documents leaked by Edward Snowden, reported by The New York Times, describe an NSA program, Bullrun, to defeat encryption, and appear to indicate that the NSA had worked to influence a standard. NIST said it "would not deliberately weaken a cryptographic standard" and strongly recommended against using Dual_EC_DRBG.
• December 20, 2013: Reuters reports that the security company RSA accepted a secret $10 million payment from the NSA to make Dual_EC_DRBG the default generator in its BSAFE software. RSA said it categorically denied entering into a secret contract.
• April 21, 2014: NIST removes the algorithm from its draft guidance, and the formal removal comes with a revision of SP 800-90A in June 2015.
• December 2015: Juniper Networks announces that some versions of its ScreenOS firmware use Dual_EC_DRBG with the suspect points, and that an unknown party had changed the point Q and some test vectors, a back door that was itself back-doored.

Here's what's established and what isn't. It's established that the constants were unexplained, that a relation between them would give a back door, that the standard included it, and that products used it. Whether the NSA chose them with a secret d is the inference the leaks supported, and the people responsible have never confirmed it in public.

The lessons

• Explain your constants. A cryptographic standard should use "nothing up my sleeve" numbers whose origin leaves no room for a hidden choice. The round constants of SHA-256 are the first digits of the cube roots of the first primes, and anyone can recompute them (the SHA-256 explorer does, in a few lines). Dual_EC's constants were just numbers.
• Be suspicious of unneeded complexity. It was slower than the alternatives and gave nothing in return. When a standard offers a worse option for no stated reason, ask why.
• Open review works, slowly. People found the flaw in public within a year, and the right people said so. The failure was in the response, since it was shipped and used until 2013 anyway. The lesson of Kerckhoffs's principle includes listening to the review.
• A weak generator undoes a strong cipher. AES was never the problem. The key it was given was.

The episode fed into the later debates (the Crypto Wars), and into the transparent processes that followed, for the SHA-3 hash and for post-quantum cryptography.

How cipher.ink uses this

None of cipher.ink's randomness comes from anything like Dual_EC. Salts, IVs, secret-link keys and tokens come from the browser's crypto.getRandomValues, which uses the operating system's generator (the Web Crypto API), and the passphrase dice use rejection sampling over it (modulo bias). On the elliptic-curve side, the only curve this site touches is the small toy one used to teach, and its X25519 code is tested against the RFC 7748 vectors. Wherever it needs a generator, it uses the one the operating system provides, the same one every other program on the machine depends on.