The Dual EC DRBG Backdoor Incident

Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG) was one of four DRBGs standardized by NIST in SP 800-90A (2006). It generates pseudorandom bits using two elliptic curve points P and Q: each step computes r_i = x(s_i * P) (x-coordinate of point multiplication), then s_{i+1} = x(r_i * P) updates the state, and output = x(r_i * Q) generates bits. The generator appeared legitimate in academic notation. It was included in NIST SP 800-90A and later endorsed by RSA Security as the default in their BSAFE cryptographic library, spreading it into enterprise and government software.

The backdoor in Dual EC DRBG exploits the relationship between P and Q. If an adversary knows a secret scalar e such that Q = e * P, then given any output block, they can compute: from output = x(r * Q), brute-force the y-coordinate of r*Q, then compute r*P = (1/e) * (r*Q) mod n. From r*P, they can predict all future outputs and recover the internal state. The knowledge of e is the backdoor — it is equivalent to the discrete logarithm of Q with respect to P. The NIST standard provided P and Q values with no explanation of how they were chosen, making it impossible to verify they were generated randomly without a trapdoor.