NSA Backdoor picoCTF 2022 Solution

Description

1. Step 1Understand Dual_EC_DRBG and its backdoor
   The PRNG generates randomness by computing r_i = x(s_i * P) where s_i is the state. If you know d such that Q = d*P, then given one output you can recover s_i and predict all future outputs.
   Learn more

   Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) was a NIST-standardized PRNG that was later shown (and suspected to be deliberately designed) to contain a backdoor. The algorithm works as follows:

   • State update: s_{i+1} = x(s_i * P) (x-coordinate of elliptic curve point multiplication)
   • Output: r_i = x(s_i * Q)

   If the PRNG designer knows d such that Q = d*P, then given an output r_i = x(s_i * Q), they can compute s_i * P using r_i and the curve to recover the full state - because d * (s_i * P) = s_i * (d*P) = s_i * Q.

   The NSA/NIST controversy: cryptographers noted that the relationship between the standardized P and Q was never explained, strongly suggesting the designers knew d. This would give the NSA the ability to predict all future random numbers from any TLS connection using Dual_EC_DRBG.

2. Step 2Recover the PRNG state using the backdoor
   An x-coordinate alone underspecifies a curve point: the equation y^2 = x^3 + ax + b has at most two solutions for any x, so two candidate points share that x. Lift the observed r_i to both candidate points (positive and negative y) and try each. The scalar d itself comes from the challenge files - inspect gen.py for the explicit P and Q constants, then solve Q = d * P either with Sage's discrete-log primitive (P.discrete_log(Q) on a small-order curve) or with a precomputed table if the order is too large. If d is hidden behind opaque transformations, an angr / Z3 hybrid against the generation routine can sometimes recover it symbolically.
   python

   python3 -c "
   # Pseudocode - fill in actual curve parameters and d from challenge files
   from Crypto.PublicKey import ECC
   
   # Challenge-provided values
   d = 0xYOUR_BACKDOOR_SCALAR
   # P and Q are standard curve points or given in the challenge
   
   # Given observed output r = x(s * Q):
   # We need to find s * P from r.
   # 1. Lift r (x-coordinate) to a point on the curve (try both y values)
   # 2. Multiply by d: d * (s * Q) = s * (d * Q) = s * (d^2 * P) - not directly useful
   #    But: d * (s * P) = s * Q, and x(s*Q) = r (known)
   # 3. Enumerate curve points with x = r, multiply each by d, check if x matches next output
   
   # After recovering state, regenerate the RSA primes and compute private key
   "

   Copied!
   Learn more

   The backdoor exploitation works as follows:

   • From the observed output r_i = x(s_i * Q), you know the x-coordinate of the point s_i * Q
   • Compute the candidate point T with x-coordinate r_i (there are two: one for each y value)
   • Compute d * T: if T = s_i * Q, then d * T = d * s_i * Q = s_i * d * Q
   • Since Q = d*P, we have d*Q = d^2*P - this alone does not recover s_i*P
   • The actual backdoor: e * Q = P where e = d^-1, so e * (s_i * Q) = s_i * P, revealing the next state

   With the state recovered, regenerate the pseudorandom byte stream used for prime generation and reconstruct p and q.

3. Step 3Decrypt the flag with the recovered RSA private key
   Once p and q are recovered from the predicted PRNG output, compute d = e^-1 mod (p-1)(q-1) and decrypt.
   Learn more

   This challenge illustrates why nothing-up-my-sleeve numbers matter in cryptographic standards. Constants in algorithms like curve point coordinates, S-box values, and initialization vectors should have a publicly verifiable, arbitrary derivation (e.g., digits of pi or SHA-256 of a fixed string) to prevent trapdoors.

   The real-world impact of backdoored PRNGs: any TLS connection using Dual_EC_DRBG could have its session keys predicted by the backdoor holder. RSA key generation using backdoored randomness produces predictable primes, making all generated keys breakable.

   Modern secure PRNGs (like the ones in OpenSSL, /dev/urandom, and NIST SP800-90A's approved algorithms, excluding Dual_EC_DRBG which was de-listed) use non-backdoored constructions like HMAC-DRBG or CTR-DRBG.

Flag

Unsolved during the competition. Use the backdoor scalar d (where Q = d*P, recoverable via discrete log on the supplied P and Q) to lift the observed PRNG output to both candidate curve points, recover the state, regenerate the RSA primes, and decrypt.