Claude Discovers Origins of NIST ECDSA Curve Seeds

Anthropic's Frontier Red Team announced that Claude identified the generation mechanism for the mysterious seeds defining NIST ECDSA curves (P-192, P-224, P-256, P-384, P-521). The discovery resolves a 25-year-old cryptographic controversy by revealing that the seeds were not arbitrary or backdoored, but produced by the standard Unix C library random number generator lrand48, initialized with a Unix timestamp.

The Discovery Mechanism

The research team determined that the seeds were generated by extracting 20-byte outputs from an lrand48 instance seeded with a Unix timestamp. By analyzing patterns in the top bits of the seeds, the team identified that the generator only returned the top 31 bits of its 48-bit state. They successfully reconstructed the hidden 17 bits using the LLL (Lenstra–Lenstra–Lovász) lattice basis reduction algorithm.

Key findings include:

• P-256 seed was found at the 1842nd iteration of the generator.
• Timestamps for the 10 prime-curve seeds fall between May 1997 and April 1998.
• Binary-curve seeds correspond to February 1984 timestamps, which align with April 17, 1998, when doubled, suggesting the program used half the clock value.

Base Point Origins

The team also uncovered the generation method for the base point G for six curves created in May 1997 (including P-192 and ANSI X9.62 examples). These points were generated using the random number generator from Arjen Lenstra's FreeLIP package. The process involved seeding with small integers, discarding seven outputs, and reducing a 26-bit output modulo the curve prime until a valid point was found.

Verified seeds for these base points include:

• P-192: seed 20000
• prime239v1: seed 20420
• prime239v2: seed 20507
• prime239v3: seed 20509
• prime192v2: seed 20512
• prime192v3: seed 20517

Implications and Limitations

The findings confirm that the curve selection process did not contain intentional weaknesses or backdoors, addressing long-standing concerns raised by researchers like Neal Koblitz and Alfred Menezes. The $36,864 bounty offered by Filippo Valsorda will be donated to the Internet Security Research Group.

However, some aspects remain unresolved:

• The seed for B-163 has not yet been reconstructed.
• The generation method for base points G on P-224, P-256, P-384, P-521, and NIST binary curves remains unknown.
• The criteria for skipping certain valid curve candidates during generation are unclear, though the low number of skips suggests no intentional weakening.