Claude Uncovers Origins of NIST ECDSA Curve Seeds

Anthropic's Frontier Red Team reports that its internal research model, Claude, successfully reverse-engineered the origins of the NIST ECDSA curve seeds in less than 30 minutes. The investigation resolved long-standing concerns about potential backdoors in the FIPS 186-2 standard by demonstrating that the seeds were generated using a standard C library PRNG, specifically lrand48, initialized with a Unix timestamp.

Reverse-Engineering the Seed Generation

The analysis revealed that the seeds for P-192, P-224, P-256, P-384, and P-521 were produced by seeding lrand48 with a Unix timestamp and iterating to generate 20-byte candidate seeds. For example, the standard seed for P-256 appeared at the 1842nd iteration. The team identified the PRNG type by observing the upper bit patterns, as lrand48 returns only the top 31 bits of its 48-bit state. To reconstruct the internal state of the truncated linear congruential generator, the researchers employed the LLL (Lenstra–Lenstra–Lovász) lattice reduction algorithm.

Verification and Timestamps

The study verified that the seeds for the 10 prime curves correspond to Unix timestamps between May 1997 and April 1998. For the 4 binary curves, the raw timestamps appeared to read as February 1984, but dividing these values by two aligned them with April 17, 1998, two weeks after the P-224 execution. The seed for B-163 remains unresolved.

Base Point Generation

The base points (G) for six curves generated in May 1997, including P-192 and the ANSI X9.62 example curves, were traced to the random number generator in Arjen Lenstra's FreeLIP package. The generation recipe involved:

• Starting with a small integer seed.
• Discarding the first 7 outputs.
• Using 26-bit outputs to generate x-coordinate candidates.
• Repeating until a point on the curve was found.

Confirmed seed values for these base points include 20000 for P-192, 20420 for prime239v1, and 20507 for prime239v2. The generation method for the base points of P-224, P-256, P-384, P-521, and NIST binary curves remains unknown.

Security Implications

The findings indicate that the seeds were not malicious backdoors but the result of a simple, clock-based PRNG. This lowers the likelihood of intentional weakness insertion. While skipped candidate curves exist (e.g., candidate 876 for P-256), there is no evidence that weakened curves were easily discoverable. The previous claim by Jerry Solinas that the seeds were hashes of humorous phrases like 'Give Bob and Jerry a raise' was disproven. The associated $36,864 bounty was donated to the Internet Security Research Group, and the reproduction code is available under CC0 1.0 Universal.