NIST’s Elliptic Curve Cryptography: AI Dispelled a 25-Year-Old Doubt

Elliptic curves developed by NIST, foundational to most digital certificates and signatures, stem from initial values provided without explanation by the NSA in the late 1990s, raising suspicions of a backdoor. A model from Anthropic has revealed these to be simple timestamps. While doubts may fade, they do not alter the post-quantum timeline governing decisions made by Chief Information Security Officers (CISOs), and uncover a new potential of models: applied cryptanalysis.

The Anthropic Frontier Red Team, responsible for the Claude model, published an explanation on October 16 detailing the seeds that generated the NIST-standardized elliptic curves used in its FIPS 186-2 signature standard from 2000. These mathematical constructs underlie a significant portion of asymmetric cryptography, enabling key negotiations for encrypted connections and producing ECDSA signatures that authenticate TLS certificates for websites and software. The most widely used curve, P-256, secures a considerable volume of encrypted communications.

To create such a curve, an initial value known as a seed is required to establish its parameters. The seeds for NIST’s curves were provided by Jerry Solinas from the NSA, without any justification. This silence fostered suspicion that a purposefully chosen seed might conceal a vulnerability known only to its creator—a backdoor. In fact, the NIST had withdrawn the Dual_EC_DRBG random number generator from its recommendations in 2014, citing public distrust following revelations about a potential backdoor. Access requests for documents sent to the NIST and NSA in 2018 yielded no results, according to an investigation published in 2023 by cryptographer Steve Weis, one of ten authors of the Anthropic publication. In October 2023, independent cryptographer Filippo Valsorda launched a bounty of $12,288—tripled if donated to a nonprofit—for anyone who could find the seeds from P-192 to P-521.

Seeds Derived from 1997 and 1998 Timestamps

According to Anthropic, an employee queried an unspecified internal model on how these seeds were produced, without revealing the existing theory of a humorous phrase passed through a hashing function. The model theorized that the seeds originated from a pseudo-random number generator from the 1990s C libraries. Such a generator produces sequences of seemingly random numbers, fully determined by its initialization value, which is sufficient to recreate the entire sequence.

The model identified the structure of the bits as linked to lrand48, a standard generator of the time. It then reconstructed the internal state through exhaustive searching and later through lattice reduction—a method that discovers hidden values from partial information—before reversing it back to find its initialization value. The seeds for the first five NIST curves and five example curves from the ANSI X9.62 standard therefore stem from a generator initialized by the computer’s clock at the program’s launch, occurring between May 1997 and April 1998.

The seed for P-256 corresponds to August 16, 1997, and the 1,842nd candidate drawn. The same analysis also elucidates the base points of six curves, another construction parameter sourced from the FreeLIP library by mathematician Arjen Lenstra. Anthropic states that the seeds’ results were obtained in less than half an hour, and has published the code to reproduce them. The team donated the $36,864 bounty to the Internet Security Research Group, the organization behind Let’s Encrypt.

Verified Results, Backdoor Elimination

The publication’s significance is bolstered by third-party verification. Filippo Valsorda re-implemented the algorithm and corroborated the outcome on the same day. To conceal a weakness would have required testing an impractically large number of seeds. According to him, the NSA had only about thirty bits of freedom, roughly one billion variations, which is insufficient to hide a backdoor solely accessible to the agency. He now recommends the NIST curves, especially as they prepare to be supplanted by post-quantum signatures.

Nonetheless, Anthropic’s work leaves several elements of the NIST curves unexplained, as acknowledged by the authors, including the seed for the binary curve B-163 and the base points from P-224 to P-521. The analysis also excluded valid candidates, like the 876th for P-256. Valsorda identified one rejection criterion, where a seed is discarded if the curve’s order exceeds the number of bits in its defining field. The second criterion remains elusive for him. Anthropic clarifies that this is neither a cryptographic break nor a weakness in the ECDSA algorithm, and that no actions need to be taken.

CISO Attention Turns to Post-Quantum Timeline

For CISOs, this discovery enhances trust in already widely accepted curves, without altering a roadmap defined by the anticipated arrival of quantum computers that will ultimately compromise ECDSA, regardless of the curves’ origins. In 2023, the NIST published SP 800-186, defining the status of each curve, with P-192 classified as legacy and the binary curves deprecated. Its transition timeline, set for November 2024, plans to phase out ECDSA post-2030 for the 112-bit security level, banning it after 2035 in favor of post-quantum signatures standardized in 2024.

The NIST schedule thus remains the sole deadline compelling businesses to inventory their asymmetric cryptography uses, certificate by certificate, and the certificates, hardware security modules, and protocols relying on P-256 will be removed based on this policy. The initial suspicion has faded regarding these decisions, as most researchers trust these curves, according to both the authors and Valsorda.

Applied Cryptanalysis: A New Model Capability

This exercise has, however, revealed a capability of interest to defense. Identifying a weak number generator based on the structure of its outputs, and then recovering its state, are acts of applied cryptanalysis that previously required a specialist. Anthropic noted on October 6, as it expanded its verified access program for cybersecurity teams, that cybersecurity is inherently dual-use.

This competency will also assist in identifying weak generators and poorly produced keys within software and connected devices currently in service. A key derived from a predictable generator can indeed be recalculated by anyone who discovers its initialization value, as demonstrated with the NIST seeds. For security teams, the cryptographic inventory necessitated by the post-quantum transition will gain a new tool, one that attackers might similarly exploit against careless implementations.

Scroll to Top