ECDSA curve seeds traced to Unix timestamps and lrand48, not a hashed passphrase

The origin of the “seed” parameters used by the NIST standard elliptic curves has been identified, where previously only the values were published with no account of how they were produced. The seeds were provided to NIST by the NSA with no explanation or justification, making their provenance a long-standing open question in cryptography that Koblitz and Menezes surveyed and that drew an amateur bounty. The circulating story that the seeds came from hashing a humorous passphrase produced nothing when searched; Claude produced the generation method for the P-192, P-224, P-256, P-384 and P-521 seeds in under half an hour.

The seeds are not hash outputs but the output of the 1990s C library pseudorandom number generator lrand48, initialized from a Unix timestamp. lrand48 returns only the top 31 bits of its 48-bit state, so its output carries a recognizable signature that a hash output would not leave. Written as five 32-bit words, four of the ten seeds have a zero top bit in all 20 words, a pattern that would occur by chance with probability 1/5810; trying all 2¹⁷ values of the hidden bits in the first word and checking the next four words worked for all four seeds.

The prime-curve seeds come from the same lrand48 but keep fewer bits of each output, so the generator state had to be recovered from truncated output. Recovering the state of a truncated linear congruential generator is a textbook lattice problem solved with the Lenstra–Lenstra–Lovász basis reduction algorithm, and it was not known which bits of the state the seeds exposed. Running the solver over every window showed five NIST prime-curve seeds and five ANSI X9.62 seeds sharing the pattern lrand48() >> 23, and each recovered 48-bit state regenerates all 160 bits of its seed.

The base points of some curves were also traced to the random number generator in the FreeLIP long-integer arithmetic package. The seed does not determine the base point G, and how those base points were generated had likewise not been explained. The base points of the six curves generated in May 1997, P-192 and the ANSI X9.62 example curves prime192v2, prime192v3 and prime239v1 through v3, match that generator with seeds 20000, 20420, 20507, 20509, 20512 and 20517.

This work addresses cryptography and security engineering readers concerned with where standard curve parameters came from, covering the five prime-curve seeds P-192, P-224, P-256, P-384 and P-521, the four binary-curve seeds B-233, B-283, B-409 and B-571, and the base points of the six curves generated in May 1997. The authors state that readers should take it as a fun closing chapter and the end of years of speculation, with no action to be taken or things to do differently.

The fifth binary seed, B-163, fits nothing Claude has tried and remains unexplained, and how the base points for P-224, P-256, P-384 and P-521 were generated is also unknown, as is the case for the NIST binary curves. In addition, the published P-256 seed is candidate 1842, but candidate 876 of the same run also gives a prime-order curve of the right size, the P-224 run passed over three such curves, and the two runs behind the ANSI X9.62 example curves passed over seven more; the selection criteria are unknown and it is unclear whether this was an unintentional artifact. The authors consider the number of skipped candidates small enough that selecting weakened curves is not plausible, but nothing in the numbers shows how many runs there were.