The mystery of the NIST curve seeds is solved: they were 1997 timestamps

Every time a browser sets up an HTTPS connection with an ECDSA signature, it most likely uses the P-256 curve. It’s one of the elliptic curves NIST published in 2000 in the FIPS 186-2 standard, along with P-192, P-224, P-384 and P-521. And for 25 years it has carried an awkward question: its parameters came from some “seeds” handed over by the NSA, with no explanation of where they came from. This week the mystery was solved, and the answer is far more boring than many expected, which is exactly what everyone wanted to hear.

The problem with the seeds

The NIST curves were generated “at random” following the ANSI X9.62 standard: you take an arbitrary 20-byte seed, hash it with SHA-1, and use the result to compute one of the curve’s coefficients. The idea is that nobody can pick the curve on purpose, because SHA-1 makes it impossible to look for a seed that yields a specific result. For example, the P-256 seed is C49D360886E704936A6678E1139D26B7819F7E90.

The flaw in that reasoning is that if you can try many seeds, you can choose among many curves. And since the NSA never explained how it picked those seeds, there was always the suspicion that it might have tried millions until it found a weak curve only it knew how to attack. Neal Koblitz and Alfred Menezes summed up the whole controversy in A Riddle Wrapped in an Enigma, and the suspicion grew after the Snowden revelations and the case of Dual_EC_DRBG, a NIST random number generator that did have a backdoor.

The most widespread version came from Jerry Solinas, of the NSA, in 2015: the seeds were the hash of a joke phrase, something like “Give Bob and Jerry a raise”, but he didn’t remember the details, and the code had been written by a colleague who didn’t remember either. Solinas passed away in 2023 and the question seemed doomed to go unanswered. In 2023, Filippo Valsorda offered a bounty to whoever found the original phrases.

Not phrases, but timestamps

Several people at Anthropic had searched for the famous phrase without success. In October, someone on the team asked an internal research model to try to figure out how the seeds were generated, without giving it the phrase hint. According to Anthropic’s write-up, in under half an hour Claude found the origin of the P-192, P-224, P-256, P-384 and P-521 seeds. And none of them came from a hash.

They were the output of the C library’s pseudorandom number generator, the drand48/lrand48 family, seeded with the system clock through srand48(). The program drew bytes from the generator, tried each group of 20 bytes as a seed and discarded the curves that didn’t meet the requirements. P-256, for example, is candidate number 1842 of the run that started on 16 August 1997 at 01:52:34 UTC.

The best part is that anyone can check it. I reproduced the P-256 seed with this code, based on the one Anthropic published:

from datetime import datetime, timezone

t = int(datetime(1997, 8, 16, 1, 52, 34, tzinfo=timezone.utc).timestamp())
x = (t << 16) | 0x330E  # the state srand48(t) sets
seed = ""
for i in range(20 * 1842):
    x = (0x5DEECE66D * x + 0xB) % 2**48  # one step of the generator
    if i >= 20 * 1841:
        seed += "%02X" % (x >> 40)  # the top byte of the state

print(seed)  # C49D360886E704936A6678E1139D26B7819F7E90

A 32-bit timestamp and a counter regenerate the exact 160 bits of the seed. For that to happen by chance, and on ten different curves at that, is impossible.

How it was found

I find the technical part beautiful. Instead of searching for phrases, Claude thought about how the software that generated the curves in the nineties must have worked, and guessed it would use the C library’s generator. Those old generators are so simple that their output can be recognised:

1. Look for the fingerprint. It wrote a program that slid along each seed bit by bit, checking whether consecutive chunks could be successive outputs of some generator from the era, across 34 different combinations.
2. A pattern of zeros. In four of the seeds, the top bit of every 32-bit word was zero. The chance of that happening randomly is 1 in 5,810, and it’s exactly the signature of lrand48, which returns 31 bits of a 48-bit state.
3. Recover the state. In the curves over prime fields, each byte of the seed was only the top 8 bits of the state. Recovering the state of a truncated linear congruential generator is a textbook lattice problem, solved with the LLL algorithm.
4. Go backwards. This generator runs backwards as easily as forwards, so it stepped back until it found a state with the shape srand48() leaves. In every case, what showed up was a Unix timestamp between May 1997 and April 1998.

As a bonus, it also found where some of the curves’ base points came from, the fixed point every public key is derived from. Those of P-192 and five ANSI X9.62 example curves come from the generator in FreeLIP, Arjen Lenstra’s arithmetic library, seeded with small numbers like 20000. According to Anthropic, it’s the first time the origin of a NIST curve base point has been explained.

What it means for security

There’s nothing to do: this isn’t an attack or a weakness, quite the opposite. Filippo explains it with numbers in his post on the bounty being claimed. In 2017, Daniel Bernstein and Tanja Lange described how, with about 70 bits of freedom in picking the seed, someone could have targeted a hypothetical family of weak curves. Now we know that even if the NSA had been free to pick any moment in 1997-98 and any of the first 16 valid candidates, it would have had barely 30 bits of freedom. Not enough to look for a weak curve on purpose, nor to plant a backdoor.

There are loose ends. Some valid curves were discarded for no apparent reason: in the P-256 run, candidate 876 also produced a valid curve and wasn’t published. There’s a rejection criterion nobody has been able to explain, although Filippo points out that these calculations, which take minutes today, were state of the art in 1997, and that there may simply have been a bug in some algorithm. It’s also still unknown how the base points of P-224, P-256, P-384 and P-521 were chosen.

Filippo, who reimplemented the algorithm in Go to verify it, closes the “rehabilitation arc” of the NIST curves: with this finding, deterministic signatures, formally verified implementations and the 2015 complete addition formulas, he now personally recommends them over Curve25519. With a very Filippo footnote: just in time for them to be retired in favour of post-quantum signatures.

My takeaway

I keep three things. First, memory plays tricks: Solinas told the phrase story in good faith, and that false lead had many people searching in the wrong direction for years. Second, the Anthropic team donated the bounty to ISRG, the organisation behind Let’s Encrypt, and the donation tripled it to $36,864. A nice ending for a cryptography story.

And third is how it was solved. It didn’t take brute force or a supercomputer, but looking at the problem from another angle: thinking about how software was written in 1997 instead of searching for a forgotten phrase. Just like the hardware reverse engineering case from a few days ago, the key is that the result can be checked objectively: 160 bits that match exactly leave no room for argument, and anyone can verify it with ten lines of Python.

Sources: Claude reveals ECDSA curve origins, Anthropic, and The NIST Elliptic Curves Seeds Bounty Has Been Claimed, Filippo Valsorda.