Claude AI Resolves NSA’s 25-Year Cryptographic Enigma
Anthropic, an AI safety and research organization, recently reported a significant breakthrough involving the origins of cryptographic seeds utilized by the National Security Agency (NSA) for five NIST elliptic curves. This development addresses a long-standing cryptographic mystery that has persisted for approximately 25 years, revealing insights into how the seeds were generated in under 30 minutes using their internal Claude model.
The findings were compiled and shared in a report dated October 16, wherein Anthropic attributed the generation of these seeds to a standard C pseudorandom number generator, specifically designed to initialize using Unix timestamps, rather than relying on concealed passphrases. This discovery, while shedding light on the processes behind public curve parameters, does not involve private keys or the secrets associated with signatures. Anthropic emphasized the nature of the research as historical reconstruction, clarifying that they did not find any cryptographic vulnerabilities or new methods of attack that would necessitate altering current deployments.
The significance of the discoveries can be traced back to the year 2000 when the National Institute of Standards and Technology (NIST) adopted the Elliptic Curve Digital Signature Algorithm (ECDSA) as part of its FIPS 186-2 Digital Signature Standard. Initially, the seeds they published were used to verify the derivation of curve parameters. However, the obscure origins of these seeds led to apprehension and speculation regarding whether the NSA had intentionally influenced the selection of these curves, raising questions within the cryptographic community.
In response to this uncertainty, a bounty created by the well-known cryptographer Filippo Valsorda invigorated researchers to delve deeper into the origins of these seeds. Various narratives had emerged, hinting that the seeds may have been inspired by humorous phrases linked to Jerry Solinas, a notable NSA mathematician. However, the Claude model took a different approach.
Instead of relying on anecdotal evidence, Claude meticulously analyzed programming patterns prevalent in 1990s C libraries. It identified lrand48, a linear congruential generator with a 48-bit internal state, as key to understanding the seed origins. The model meticulously scanned the seeds that were made public across 34 different generator-output-slice combinations. Among these, four binary-curve seeds contained five 32-bit words, with the highest bits consistently zero. This finding was consistent with the known 31-bit output of the lrand48 generator.
In further exploration, Claude enumerated the 17 hidden state bits and conducted checks on subsequent outputs to recover potential generator states, leading to illuminating insights. The seeds linked to prime curves tended to expose fewer bits from each generator call compared to their binary counterparts. Utilizing the Lenstra–Lenstra–Lovász lattice basis reduction algorithm, Claude reconstructed internal states from these truncated outputs. This intricate process led to the successful retrieval of five seeds from NIST and five example seeds from ANSI X9.62, corroborating a construction that collected bytes from lrand48().
Most revealing were the initialization values, which corresponded to Unix timestamps between May 1997 and April 1998. The reconstruction effort resulted in the reproduction of several well-known curves: P-192, P-224, P-256, P-384, and P-521. Particularly for P-256, the standardized seed emerged as candidate number 1,842, initialized on August 16, 1997.
Moreover, Claude also reconstructed the base-point generation associated with P-192 and several ANSI example curves, utilizing the generator from FreeLIP, an arithmetic package developed by Arjen Lenstra. Notably, these base points are distinct from the curve seeds provided earlier, serving as fixed points for various cryptographic operations.
Despite the remarkable strides made in this endeavor, it is essential to note that the reconstruction is not entirely complete. Anthropic acknowledged that they could not provide clarity regarding the B-163 seed or several essential base points in their findings. The researchers also noted instances of skipped candidates that seemed to yield appropriate curves, leaving certain foundational questions about the original selection criteria open for further exploration.
Anthropic contends that their timestamp-based constructions, which can be reproduced, alleviate concerns about intentional manipulation of the seed generation, though they do not conclusively establish the rationale behind every historical decision nor definitively rule out the possibility of alternative generation processes.
The $36,864 bounty for this investigation will be donated to the Internet Security Research Group, symbolizing a commitment to advancing knowledge and transparency in the field of cryptography. For industry stakeholders, this revelation signifies an increase in transparency concerning public cryptographic parameters, albeit without unearthing any classified secrets or demonstrating weaknesses in ECDSA authentication methods.