Anthropic Claude found how NIST ECDSA curve seeds were generated

For 25 years nobody could explain where the seeds for the NIST ECDSA elliptic curves came from, and some suspected a government backdoor. Anthropic says an internal research model found the answer in under half an hour: the seeds are the output of lrand48, a 1990s C library random number generator, seeded with a Unix timestamp.

The research is published under ten names from Anthropic, including Nicholas Carlini, Paul Crowley, Henry de Valence and Steve Weis. The write-up matches the five NIST prime-curve seeds (P-192, P-224, P-256, P-384 and P-521) and five more from the ANSI X9.62 standard to runs of the same lrand48 generator, with the recovered Unix timestamps falling between May 1997 and April 1998. A Python script that reproduces the published seeds from the recovered state is included.

How Claude found it

An old rumour said the seeds were the hash of a joke passphrase. That turned out to be wrong. Longtime NSA cryptographer Jerry Solinas, who had generated the seeds, died in 2023, and other colleagues at the time did not respond to inquiries, so no new information was available from the people who had done the work. Claude tried a different approach. It guessed the software used a pseudorandom number generator that shipped with 1990s C libraries, wrote a scanner that slid along each published seed one bit at a time, and tested whether adjacent chunks were consecutive outputs of a 1990s-vintage generator.

The scanner covered 34 combinations of generator and output slices. Claude then noticed the top bit was zero for every 32-bit word in four of the ten seeds, which the write-up says would happen by chance with probability one in 5,810. That is the signature of lrand48, which only returns the top 31 bits of a 48-bit state. For the prime-curve seeds, where fewer bits were kept per output, Claude recovered the internal state by running the Lenstra-Lenstra-Lovász lattice reduction algorithm over every window of the output.

What this means for the curves

Anthropic frames the finding as the opposite of a cryptographic attack. The seeds were generated by a known pseudorandom number generator and a Unix clock, and anyone can now reproduce them from the published state, which the post says leaves less room for the hidden-backdoor theories that have sat around the NIST curves since 2000. "This makes us more confident the curves were chosen without any backdoors or intentional weaknesses," the post says.

Three questions remain. One seed, B-163, fits nothing Claude tried. The base points for P-224, P-256, P-384 and P-521 are still unexplained; Claude did find the base points of the six curves generated in May 1997, which come from the random number generator in Arjen Lenstra's FreeLIP library. And nobody knows why 1,841 earlier candidate seeds were skipped for P-256 before the published one at index 1,842.

For a team building software, there is nothing to patch and no action to take. The reason to read the write-up is that a general reasoning model, with no cryptography pipeline wrapped around it, closed a question that cryptographers had been asking for 25 years. Anthropic will donate the $36,864 seed-finding bounty, originally organised by Filippo Valsorda, to the Internet Security Research Group.

Source

Anthropic research: Claude reveals ECDSA curve origins