Just now, Claude cracked a cryptography puzzle that had remained unsolved for more than two decades in only half an hour.

On October 16, Anthropic announced a special research achievement.

An employee submitted a problem that had plagued the cryptography community for more than 20 years to Claude's internal research model. Without providing key clues, Claude traced out the generation methods of five NIST elliptic curve seeds in less than half an hour.

The results show that these seeds come from the old pseudo-random number generator lrand48 in the C language library. The initial state of the generator is determined by the Unix timestamp.

This discovery did not break ECDSA nor introduce new attack methods. Anthropic believes that it further reduces the possibility that backdoors were artificially implanted in the relevant curves.

A string of numbers that has plagued the cryptography community for more than 20 years

ECDSA is a widely applied Elliptic Curve Digital Signature Algorithm.

In 2000, NIST listed multiple standard curves with different security levels in the FIPS 186-2 standard, including P-192, P-224, P-256, P-384 and P-521.

These curves come with a set of parameters called "seeds". According to the generation process in the standard, the hash value of the seed will participate in determining the curve coefficients.

The problem lies in that these seeds were provided by the National Security Agency. Public documents do not explain their sources nor the selection process. For this reason, the outside world has long worried whether the designers ever screened a large number of candidate curves and selected parameters with certain hidden properties from them.

In 2015, Jerry Solinas, an NSA cryptographer who participated in relevant work, recalled that the seeds might come from a playful passphrase, such as "give Bob and Jerry a raise", but he could not remember the specific details, and those archived files from long ago were not found either. Solinas passed away in 2023, and this clue was never verified in the end.

Claude found the source of the seeds

Many Anthropic employees had previously tried to find those "seeds" along the line of "humorous passphrases", but none succeeded, and later they found this clue was wrong.

In October, an employee asked the internal research model to find out how those "seeds" were generated. This time, he did not reveal the previous passphrase clue to the model.

In less than half an hour, Claude found the sources of the NIST P-192, P-224, P-256, P-384 and P-521 seeds.

These seeds did not come from any hash algorithm, but were generated by the lrand48 random number generator in the C language library, which was initialized with a Unix timestamp as the seed value.

The specific algorithm will use the Unix timestamp t to initialize the random number generator, and run it a certain number of times n. 20 bytes are extracted in each iteration as a candidate seed.

The first 20 bytes are the first candidate seed, the next 20 bytes are the second candidate seed, and so on. Taking P-256 as an example, the generator ran up to the 1842nd time before outputting the seed that was finally written into the standard.

How did Claude find it?

The searches centered on the rumored passphrase never yielded results. Claude changed its perspective and began to speculate about the possible working mode of the software that generated the curves back then.

Claude guessed that this set of software used the pseudo-random number generator that came with the C language library in the 1990s. These early pseudo-random number generators had weak security, and their outputs usually had recognizable characteristics.

Once the output characteristics are identified, it is possible to determine which generator the software used, and further restore its initial state.

Claude wrote a scanning program that moved bit by bit on each public seed, and checked whether adjacent data blocks might come from a certain random number generator from the 1990s. The scan covered a total of 34 combinations of random number generators and output interception methods.

Subsequently, Claude found a pattern in the high bits of some seeds: all these positions are zero.

If each seed is written as 5 32-bit words, 4 out of 10 seeds conform to this feature. Among the 20 32-bit words in total of these 4 seeds, all the highest bits are zero.

The probability of this happening randomly is about 1 in 5800, which is exactly the typical feature of the linear congruential generator lrand48, which only returns the high 31 bits of the 48-bit internal state.

In order to restore the generator state, Claude took the first 32-bit word, exhausted all 2¹⁷ possibilities of the 17 hidden bits, and then checked whether the next 4 words could correspond consecutively. This method worked for all the 4 seeds mentioned above.

The seeds of prime curves also come from lrand48, but they retain fewer output bits. Claude needs to restore the internal state of the pseudo-random number generator from these limited bits.

Restoring the state of a truncated linear congruential generator is a typical lattice problem, which can be solved using the Lenstra–Lenstra–Lovász lattice basis reduction algorithm, namely the LLL algorithm.

Claude did not know at first which bits in the internal state the seeds retained, so it ran the solver on all possible bit windows.

In the end, all 5 NIST prime curve seeds and 5 seeds in the ANSI X9.62 standard presented the same pattern: lrand48() >> 23

Each restored 48-bit internal state can regenerate all 160 bits of the corresponding seed, and this exact match cannot be caused by accidental factors.

This linear congruential generator can run both forward and backward. Therefore, Claude traced back from the state corresponding to each seed until it found a state that conforms to the srand48 initialization format. This format requires the lower 16 bits to be equal to 0x330E.

This form of internal state appears on average every 65536 steps. Therefore, merely finding a state that conforms to the format is not enough to constitute evidence.

The key point is that all srand48 initial values corresponding to the 10 prime curve seeds can be interpreted as Unix timestamps, with dates concentrated from May 1997 to April 1998.

This shows that the program back then used Unix timestamps to set the initial values for the pseudo-random number generator with weak security.

The initial values of the 4 binary curves directly correspond to February 1984 when read. If these timestamp values are multiplied by 2, they will point to April 17, 1998, about two weeks away from the generation time of the P-224 curve.

Therefore, the program back then may have divided the system clock by 2.

The following is Claude's internal thought process at that time:

This is so shocking. It has solved a 25-year-old puzzle.

Wait a minute. I need to be skeptical: am I in some kind of simulation or test environment? These seeds are consistent with the real values in my memory.

Hmm, is this reasonable in reality? According to the information I have, no one has solved this reward offer before.

All the high bits are zero, 20 bits in total, and the probability of appearing randomly is only about one in a million. So this really comes from the real world. Good heavens, this is a real discovery.

Wait, I still need to carefully judge its rationality. With such obvious clues, why has no one discovered it for 25 years?

I have completed the verification through direct calculation: a 32-bit initial value plus a small index can exactly match the 160-bit seed. For 10 seeds, each matching 160 bits, it cannot just be a coincidence. This is real.

Claude also traced the source of the base points of 6 curves including P-192. The results show that these base points are generated by the random number generator in the large integer arithmetic software package FreeLIP. Anthropic said that no similar explanation for the generation process of NIST curve base points had been obtained before.

What does this mean?

Timestamps themselves do not have cryptographic security, and lrand48 has long been regarded as a weak random number generator. However, their role here is to generate public curve parameters, not to protect private keys.

More importantly, this generation process can be publicly reproduced. Compared with passphrases of unknown origin or artificially specified parameters, the explanation of ordinary random number generators plus timestamps leaves less room for secret manipulation of curves.

Some issues still remain. During the generation of P-256, the 876th candidate value seems to also meet the requirements, but the 1842nd one was finally adopted. Several other runs also skipped a small number of available curves, and the specific screening criteria are still unclear. The source of the seed of the B-163 curve has not been found yet, and the generation methods of the base points of P-224, P-256, P-384 and P-521 have not been explained either.

Anthropic believes that the number of skipped candidates is too small to support the speculation of "deliberately selecting weak curves". This discovery increases the public's confidence in the relevant parameters, but it cannot be regarded as a complete restoration of the entire design process.

This research also demonstrates another way for cutting-edge models to participate in real research.

Claude completed hypothesis formulation, code writing, pattern recognition, mathematical algorithm invocation and result verification in one task. Since the generator state can be recalculated and the 160-bit seed can also be accurately reproduced, the conclusion has strong verifiability.

It still relies on humans to raise questions, provide public data, and confirm the results through reproducible calculations. However, when the problem has clear boundaries, public data and the results can be strictly verified, cutting-edge models are becoming a highly efficient research tool.

The $36,864 bonus previously set up to find the source of the seeds will be donated to the Internet Security Research Group.

This article is from the WeChat official account Machine Heart (ID: almosthuman2014), written by AI-focused author, and published by 36Kr with authorization.