On October 16, Anthropic released a special study.
One employee handed over a problem that has plagued the cryptography community for more than two decades to Claude's internal research model, in which Claude spent less than half an hour tracing the way five NIST elliptical curve seeds were generated without providing a critical clue.
The results showed that the seeds came from an old pseudo-random number generator in the C language library.lrand48The initial state of the generator is determined by the Unix timestamp.
The discovery did not break the ECDSA and did not lead to a new attack method. Anthropic believes that it further reduces the likelihood that the corresponding curve will be implanted in the back door by humans.
A string of digits has plagued the cryptography industry for more than two decades
ECDSA is a widely used elliptical digital signature algorithm.
In 2000, NIST listed several standard curves of different security levels in the FIPS 186-2 standard, including P-192, P-224, P-256, P-384 and P-521.
These curves are accompanied by a set of parameters known as "seeds". According to the generating process in the standard, the hash value of the seed is involved in determining the curve coefficient.
The problem is that the seeds are provided by the National Security Agency, and public documents do not specify their origin or explain the selection process. The outside world has long been concerned that designers may have screened a large number of candidate curves and selected parameters with some hidden characteristics from them.
In 2015, NSA cryptographer Jerry Solinas recalled that the seeds may have come from a joking catchphrase, such as "pay up to Bob and Jerry", but he didn't remember the specifics, and the archival files long ago were not found.
Claude found the source of the seeds
Many of Anthropic's employees had previously searched for the "seeds" using the Humor Dictionary, but were unsuccessful and later found the clue to be wrong.
In October, an employee asked an internal study model to find out how the "seeds" were produced.
In less than half an hour, Claude found the source of NIST's P-192, P-224, P-256, P-384 and P-521 seeds.
These seeds are not from any hash algorithm, but from a C language library.lrand48A random number generator is generated, which initializes the generator using the Unix time string as the seed value.
Specific algorithms use the Unix timestamptInitiate a random number generator and run a certain number of times.n Each generation extracts 20 bytes as a candidate seed.
The first 20 bytes are the first candidate seeds, and the next 20 bytes are the second candidate seeds, in this way. In the P-256 example, the generator runs to 1842 and only produces the final written standard seeds.
How did you find Claude?
The search around the rumored curve was never successful, and Claude changed his perspective and began to speculate on how the software that generated the curve might have worked that year.
Claude speculated that the software used pseudo-random number generators from the C language library back in the 1990s, which were less secure than early pseudo-random number generators and whose output was usually characterized by identifiable features.
Once the output characteristics are identified, it is possible to determine which generator the software uses and to further restore it to its original state.
Claude wrote a scanning program that moved gradually across each open seed and checked whether the adjacent data blocks could have come from a random number generator in the 1990s. The scanning covered a combination of 34 random number generators and output intercepts.
Claude subsequently discovered a rule in the high positions of some of the seeds: these positions are all zero.
If each seed is written in five 32-bit letters, then four of the 10 seeds correspond to this characteristic.
The probability of this happening at random is about 58 percent. This is the linear symmetry generator.lrand48 A typical feature is that it returns only high 31 bits in a 48-bit internal state.
To restore the generator state, Claude extracted the first 32 bits of the first 217 possible words of 17 hidden bits, and then checked whether the next four words corresponded continuously. This method worked for all four of the seeds.
The seeds of the prime number curve also come from.lrand48 However, 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 the intersectional linear symmetry generator is a typical G-problem that can be solved using the Lenstra-Lenstra-Lovász-Georgian abbreviation, the LLL algorithm.
At first Claude didn't know which bits the seed retained in its internal state, so he ran a solver for all possible bit windows.
In the end, five NIST prime-curve seeds and five ANSI X9.62 seeds showed the same pattern:lrand48() >> 23
Each recovered 48-bit internal state is able to reproduce all 160 bits of the corresponding seed, and this precise matching cannot be caused by accidental factors.
This linear symmetry generator can run either upward or backward. Thus, Claude starts back and forth from the corresponding state of each seed until finding the corresponding one.srand48 The state of the initialized format. The format requires a lower 16-bit equivalent.0x330E 。
On average, this form of internal state occurs once every 65536 steps. Therefore, merely finding a state that matches the format is not enough to constitute evidence.
The key is that the seeds of the ten prime curves correspond.srand48 All of the initial values can be interpreted as a Unix timeline, with dates ranging from May 1997 to April 1998.
This illustrates that the program used the Unix timestamp to set the initial value for weakly secure pseudo-random number generators.
The initial value of the four binary curves read directly corresponds to February 1984. If these time series values are multiplied by 2, they point to April 17, 1998, about two weeks from the generation time of the P-224 curve.
Therefore, the program at the time may have dealt with the system clock by dividing it by 2.
The following is an internal reflection of Claude's time:
This is shocking. It solves a 25-year-old puzzle.
Oh, and so on. I have to remain suspicious: am I in some kind of simulation or test environment? These seeds match the real numerical values in my memory.
Well, does that make sense in reality? According to the information I have, this reward has not been solved before.
All highs are zero, 20 bits in total, and the probability of random occurrence is about one-millionth. So, this really comes from the real world.
Wait, I still need to judge the rationality carefully. Why hasn't anyone found such a clear clue for 25 years?
I've done the verification using direct computation: a 32-bit initial value plus a smaller index can accurately match 160-bit seeds. For 10 seeds, each matching 160-bit, it can't be just a coincidence.
Claude also traces the source of the base points of 6 curves, such as P-192. The results show that these base points are generated by random number generators in the FreeLIP suite of integers.
What does that mean?
The time slot itself does not have encryption security.lrand48 They have long been regarded as weak random number generators. However, they play the role of generating open curve parameters and are not used to protect private keys.
More importantly, this set of generating processes can be publicly replicated. Compared to unknown source commands or human-specified parameters, ordinary random number generators add time slots to explain less space left for secret manipulation curves.
Some problems remain. In the process of generating P-256, the 876th candidate appears to have met the requirements, but the 1842nd was finally adopted. Several other operations also skipped a few available curves, and the specific screening criteria are unclear. The seeds of the B-163 curve have not yet been found, and the base point generation methods for P-224, P-256, P-384 and P-521 have not been explained.
Anthropic believes that the number of candidates who have been skipped is small enough to support the hypothesis of "deliberately selecting the weak curve", a finding that increases the confidence of the outside world in relevant parameters but cannot yet be seen as a complete restoration of the entire design process.
The study also shows another way in which front-end models engage in real-world research.
In one task, Claude completed assumptions, code writing, pattern recognition, mathematical algorithm calls and results verification. Because the generator state can be recalculated, 160-bit seeds can also be accurately reproduced, resulting in stronger testability.
It still relies on humans to ask questions, provide open data, and confirm results through reproducible computation, but when the boundaries of the problem are clear, the data are open and the results can be rigorously verified, front-end models are becoming a highly efficient research tool.
The $36,864 prize, which was previously set up to find the source of the seeds, will be donated to the Internet Security Research Group.
The link is as follows:
© THE