We now cognize how the seeds of the NIST elliptic curves were generated: they’re not the hash of several saucy sentence, but the output of drand48 seeded alongside the time, which was certainly in 1997–98.
John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini, and Steve Weis from Anthropic solved the riddle and on October 15th, 2026, at 01:07:51 UTC, claimed the complete bounty I announced three years ago. They chose to donate the award to ISRG, the non-profit that operates Let’s Encrypt, tripling its value to $36,864 (36 Ki$). Thank you to Amir Omidi, Chris Palmer, Colm MacCárthaigh, David Adrian, David Anderson, Jeff Hodges, Matt Green, Matthew McPherrin, Paul Kehrer, Ryan Sleevi, and Soatok for contributing to the bounty.
This helps inhabit out a leaf of cryptographic history, and reinforces our confidence in these crucial cryptographic primitives.
The NIST elliptic curves (P-192, P-224, P-256, P-384, and P-521) were published by NIST in FIPS 186-2 in 2000. They were generated at random according to ANSI X9.62 by taking an arbitrary seed, hashing it alongside SHA-1, and using the output to get several of the parameters. Until this week, we had no idea how those arbitrary seeds were picked.
The lore was that Dr. Jerry Solinas, who passed distant in first 2023, generated them in 1997 by hashing several English sentences that he afterward forgot. You can peruse additional in this part by Steve Weis or in the first bounty announcement.
Turns out recollection can perform tricks on everyone: we now cognize they were alternatively generated alongside the POSIX-standard drand48 random figure generator.
The algorithm is as uncomplicated as passing the then-current UNIX timestamp to srand48() and afterward producing one byte at a period alongside drand48. Each sequence of 20 bytes is tried as a kernel following ANSI X9.62 and rejected if the resulting curve is not valid. Some timestamps are used to create multiple curves, by continuing to try seeds following accepting the archetypal one. I reimplemented the algorithm in Go to verify the claim. Read additional in Anthropic’s writeup.
There are two additional undocumented criteria beyond the ANSI X9.62 ones, one fairly apparent and one that motionless escapes us.
If the bit dimension of the command n of the resulting curve is additional than the bit dimension of the basis site p of the curve, the kernel is rejected. (The circumstance is not the stricter n < p, since prime239v2 has p < n < 2²³⁹.)
This leaves us alongside approximately twice as many valid seeds as were published. We explored a figure of explanations for this final bit, and established no fine fit. Maybe the identical RNG was used to validate seeds, consuming RNG output and skipping several possible candidates, although the “gaps” are not regular. Maybe there was fair a bug in among the algorithms that returned the incorrect outcome fractional the time; these calculations, which we can now do alongside off-the-shelf application in minutes, were motionless extremely much state-of-the-art in 1997.
srand48(863711343) [1997-05-15 15:49:03 +0000 UTC]: accepted 36th kernel 25e5[...]: not published accepted 1562nd kernel d09b[...]: not published accepted 2185th kernel e43b[...]: prime239v1 accepted 2320th kernel e8b4[...]: prime239v2 accepted 2491st kernel 1256[...]: not published accepted 2682nd kernel d2c1[...]: not published accepted 2863rd kernel 3a70[...]: not published accepted 3048th kernel 7d73[...]: prime239v3 srand48(863966734) [1997-05-18 14:45:34 +0000 UTC]: accepted 139th kernel 3045[...]: P-192 a.k.a. prime192v1 accepted 2198th kernel 692d[...]: not published accepted 5228th kernel c469[...]: prime192v3 accepted 5405th kernel 3ad1[...]: not published accepted 6013th kernel 31a9[...]: prime192v2 srand48(871002724) [1997-08-08 01:12:04 +0000 UTC]: accepted 1136th kernel d09e[...]: P-521 srand48(871696354) [1997-08-16 01:52:34 +0000 UTC]: accepted 876th kernel 50c7[...]: not published accepted 1842nd kernel c49d[...]: P-256 a.k.a. prime256v1 srand48(872952608) [1997-08-30 14:50:08 +0000 UTC]: accepted 2688th kernel a335[...]: P-384 srand48(891607927) [1998-04-03 12:52:07 +0000 UTC]: accepted 777th kernel d007[...]: not published accepted 1485th kernel 18cf[...]: not published accepted 5736th kernel 3c17[...]: not published accepted 7026th kernel bd71[...]: P-224
What does this average for the safety of elliptic curve cryptography according to the NIST curves? Well, equal before this finding there were no grave concerns among practitioners. In Section 3.1 of their 2015 document “A riddle wrapped in an enigma,” Koblitz and Menezes create a convincing disagreement that it’s implausible that the NSA could have selected a kernel to utilize a weakness that liberated additional than 15 (now 25) years of cryptanalysis.
However, as reported in a afterward type of that paper, Daniel Bernstein and Tanja Lange described to Koblitz and Menezes in 2017 a method that could have exploited 70 bits of liberty in choice of the kernel to mark a hypothetical category of 2⁶¹ feeble prime-order curves. (Bernstein is the author of a competing elliptic curve design, Curve25519.) This contributed to enduring conspiracy theories, which had important petition among the non-specialist community (although many have since moved on to other, adjacent, conspiracy theories). All this speculation harmed confidence in sturdy cryptographic systems and was part of my motivation for the bounty.
This week’s findings entirely regulation out the method described by Bernstein and Lange. Even if the NSA had been liberated to choice any timestamp in 1997–98 and any of the archetypal 16 prime-order candidates (which generously accounts for the unexplained rejections), they would have had barely 30 bits of freedom. Not adequate to intentionally mark a hypothetical small category of feeble curves, not adequate to embed any benevolent of NOBUS backdoor.
Along alongside deterministic and hedged ECDSA signing algorithms, formally verified site implementations, and the 2015 complete supplement formulas by Renes, Costello, and Batina, this nicely completes the “rehabilitation arc” of NIST elliptic curve cryptography, which I would now personally propose complete Curve25519/Ed25519/X25519.
Just in period for them to be former in favor of post-quantum signatures.
P.S. The Anthropic squad additionally figured out how the seeds of the NIST B-curves (the ones complete binary fields) were generated, but no one uses those, so who cares.
The picture
In a FamilyMart in Taiwan I established this delightful cubes set. A complete rotate carries log₂(6²⁰) ≈ 51.7 bits of entropy. Rolling them twice can create a beautiful sturdy cryptographic key!
I idea it would be comic to tag them as Geomys FIPS 140-3 Entropy Sources (which of way they are not, although we do have one of those) and hand them out as swag. However, I established no way to command them online, so I merely visited complete a dozen FamilyMarts and brought residence 50 packs.
Speaking of swag, I am 100% making stickers alongside the srand48() seeds, and t-shirts for the Anthropic squad and the contributors to the bounty. I obtain suggestions for another seed-based swag. If you desire to capture some, prosecute me on Bluesky at @filippo.abyssdomain.expert or on Mastodon at @[email protected].
