DUAL_EC_DRBG is a cryptographically secure pseudorandom generator whose single bignum state advances through elliptic-curve multiplication. Its security fails if the generator points P and Q have a hidden mathematical relation. section 3.2 section 3.2.3
Each generation computes the next state as g_P(n) = X(nP), then outputs g_Q(n) = t(X(nQ)): it discards the y-coordinate and truncates the x-coordinate to 30 bytes. section 3.2.3
The backdoor attack proceeds as follows:
- Observe an output derived from s₀Q, then restore candidate x-coordinates by trying the missing 16 high-order bits. section 3.2.4
- Recover a valid y-coordinate from the elliptic-curve equation and reconstruct the candidate point s₀Q. section 3.2.4
- If P = dQ and d is known, multiply the recovered point by d to obtain s₀P, the next state. section 3.2.4
- Generate a predicted next output and compare it with the observed value; a match identifies the candidate and enables cloning. section 3.2.4
Go cloning demonstration
A Go implementation uses elliptic.P256(), big.Int, and 30-byte outputs. The exploit generates related constants, brute-forces candidates, and verifies that cloned and original generators produce identical subsequent outputs. section 3.2.3 section 3.2.4
Listing 3.15 impl_dual_ec_drbg.go
const ( Px = "6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296" Py = "4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5" Qx = "c97445f45cdef9f0d3e05e1e585fc297235b82b5be8ff3efca67c59852018192" Qy = "b28ef557ba31dfcbdd21ac46e2a91e3c304f44cb87058ada2cb815151e610046" )
The constant definitions make the two elliptic-curve generator points concrete and show the fixed parameters that determine generator behavior. section 3.2.3
