Every link on the blog post has a ?ref=words.filippo.io query
parameter on it, regardless of going to different hosts all over the
internet. I have removed these in the copy below.
On 10/8/23, jdb10987@yahoo.com
https://www.bleepingcomputer.com/news/security/bounty-offered-for-secret-nsa...
https://words.filippo.io/dispatches/seeds-bounty/ 05 Oct 2023 # ANNOUNCING THE $12K NIST ELLIPTIC CURVES SEEDS BOUNTY The NIST elliptic curves that power much of modern cryptography were generated in the late ‘90s by hashing seeds provided by the NSA. How were the seeds generated? Rumor has it that they are in turn hashes of English sentences, but the person who picked them, Dr. Jerry Solinas, passed away in early 2023 leaving behind a cryptographic mystery, some conspiracy theories, and an historical password cracking challenge. *Together with some generous matchers, I’m announcing a $12,288 (12 Ki$) bounty for cracking these five hashes, tripled to $36,864 if the recipient chooses to donate it to a 501(c)(3) charity of their choice.*
3045AE6FC8422F64ED579528D38120EAE12196D5 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5 C49D360886E704936A6678E1139D26B7819F7E90 A335926AA319A27A1D00896A6773A4827ACDAC73 D09E8800291CB85396CC6717393284AAA0DA64BA
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, and to Steve Weis for the research that inspired this. ## Step back, what is this about? The NIST elliptic curves (P-192, P-224, P-256, P-384, and P-521[1]) were published by NIST in FIPS 186-2 in 2000, and generated “verifiably at random” according to ANSI X9.62 by taking an arbitrary seed, hashing it with SHA-1, and using the output to derive some of the parameters. A lot of cryptography uses NIST curves, and especially P-256 and P-384. They are in the Commercial National Security Algorithm Suite (the successor of Suite B), and are the curves used by the ECDSA X.509 certificates that secure much of the web. They’re a big deal. Steve Weis has recently published a well researched article[2] on everything we know about those arbitrary seeds embedded in the FIPS 186 specification. Apparently, they were provided by the NSA, and generated by Jerry Solinas in 1997. He allegedly generated them by hashing, presumably with SHA-1, some English sentences that he later forgot.
[Jerry] told me that he used a seed that was something like: SEED = SHA1("Jerry deserves a raise.") After he did the work, his machine was replaced or upgraded, and the actual phrase that he used was lost. When the controversy first came up, Jerry tried every phrase that he could think of that was similar to this, but none matched.
That’s unfortunate, because the NIST curves are—surprisingly—looking better and better: we now have complete addition formulas[3] for them, mitigating their major footgun; we know how to design safer interfaces for them; and we painfully learned to appreciate the value of prime order curves immune to cofactor attacks. However, there is—mostly amongst non-practitioners—some fear that the NSA could have picked the seeds to select some intentionally weak curves. Do I think those fears are well-founded? No. Koblitz and Menezes make a good argument in _A riddle wrapped in an enigma_[4] that even with full control over the seed, the NSA would have had to be aware of a class of weak curves so large that it’s not plausible that no one in academia or industry discovered them in 25 years.[5] Anyway, some FUD[6] persists around the otherwise pretty good NIST curves that would be good to clear up, even if the English preimage of the hashes is not a complete guarantee of rigidity[7,8]. That’s where this bounty comes in. Finding the pre-seeds, the inputs to the hash that generated the seeds, is the bread and butter of password crackers and brainwallet bruteforcers. *This is a call to arms for them to join the search, help fill in a page of cryptographic history, and collect a large bounty or donate an even larger one to charity.* ## Ok, so what do we know about the hashes? To recap Steve Weis’s post, the inputs are probably English phrases which mention Jerry Solinas, possibly someone else, and probably a counter. If you’re actually going for it I recommend reading Steve’s post in full. The counter has to be there because only one in every 192 to 521 hashes is actually good to make a curve out of, depending the bit size of the curve. (This is because one in every ln(N) numbers less than N is prime, for large enough N.[9]) There’s a 99% chance the counter is less than 2400 for the largest curve[10], and less than 1175 for P-256. The seeds for P-192 and P-256 appeared as examples in the previous ANSI X9.62 standard, while all the others were new in FIPS 186-2, so they might have been generated from differently structured sentences. Since testing more hashes is nearly free, I recommend also targeting all the examples from ANSI X9.62 that didn’t make the FIPS standard, as well as the seeds for the binary curves in FIPS 186-2, although they are not included in the bounty. Here’s a recap.
3045AE6FC8422F64ED579528D38120EAE12196D5 # NIST P-192, ANSI prime192v1 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5 # NIST P-224 C49D360886E704936A6678E1139D26B7819F7E90 # NIST P-256, ANSI prime256v1 A335926AA319A27A1D00896A6773A4827ACDAC73 # NIST P-384 D09E8800291CB85396CC6717393284AAA0DA64BA # NIST P-521 31A92EE2029FD10D901B113E990710F0D21AC6B6 # ANSI prime192v2, not eligible for bounty C469684435DEB378C4B65CA9591E2A5763059A2E # ANSI prime192v3, not eligible for bounty E43BB460F0B80CC0C0B075798E948060F8321B7D # ANSI prime239v1, not eligible for bounty E8B4011604095303CA3B8099982BE09FCB9AE616 # ANSI prime239v2, not eligible for bounty 7D7374168FFE3471B60A857686A19475D3BFA2FF # ANSI prime239v3, not eligible for bounty 85E25BFE5C86226CDB12016F7553F9D0E693A268 # NIST B-163, not eligible for bounty 74D59FF07F6B413D0EA14B344B20A2DB049B50C3 # NIST B-233, not eligible for bounty 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE # NIST B-283, not eligible for bounty 4099B5A457F9D69F79213D094C4BCD4D4262210B # NIST B-409, not eligible for bounty 2AA058F73A0E33AB486B0F610410C53A7F132310 # NIST B-571, not eligible for bounty
The format of the string is part of the mystery. It could end with a period or not, end with a newline or not, the counter could be decimal (with or without leading zeroes) or binary (16 or 32 bit), and it could come after the period or separated some other way. The same sentence with different counters could have been used to generate all the seeds, or they could be different sentences, or they could include the curve name or size. Human memory is notoriously fallible, so it could also be that some of the details in the second-hand recollections are wrong. *[Edited to add]* It could even be that instead of a counter they started with SHA-1(s), and then tried SHA-1(SHA-1(s)), and so on. Or maybe they started with SHA-1(s), and then incremented the hash like IP2BS(BS2IP(h) + 1), which is what ANSI X9.62, Section A.3.3.1 does to the seed to extend it. The latter can be accounted for by adding to the list of targets the decrements of each of the hashes above. Here's a list of ~12k hashes that cover 99% of the probability space for each of the prime order curve seeds in both FIPS 186-2 and ANSI X9.62.[11] *Assuming checking many hashes is relatively cheap, this is the list of hashes you should attack. (Or, if you have the option, you can get the same result by only comparing the first 16 bytes of the hash.)*
nist-and-ansi-prime-order-seeds-increments-99-percent.txt [12]
The good news is that SHA-1 is tremendously fast to bruteforce, and _YOU_ are the experts in cracking passphrases you know nothing about. ## Cool, what’s the fine print? The bounty will pay out to the first person(s) to email the pre-seeds for the five prime-order NIST curves to seeds@filippo.io. Half the bounty ($6,144) will pay out to the first submission of _at least one_ pre-seed, and the other half will pay out to the first submission of _all five_ pre-seeds. They can of course go to the same person, so don’t wait to have them all to submit. Even one would make history. If successful, you can either choose to receive the cash bounty, or select a U.S. 501(c)(3) charity to receive triple the amount. We reserve the right to veto charity choices dramatically incompatible with our values, but we won’t be jerks about it. If it’s not legally allowed for a U.S. person or Italian national to send money to you, you will have to select the charity option. You’re responsible for any taxes on the cash bounty. I fully trust every matcher, and I am guaranteeing the full amount of the bounty personally, so you don’t have to. Put “ANTISPAM” in the subject line of any submission to hit my allowlisting rules. The Received header of my mail host will be the unappealable criterion of what submission arrived first. The bounty expires if the seeds become publicly known, otherwise it’s valid until announced otherwise on this page. If the bounty is being cancelled or lowered, it will be announced six months in advance. (We don’t want anyone to feel cheated of their resources.) We don’t actually care how you find the seeds. It can be bruteforcing, clever guessing, sleuth work tracking down NSA employees (don’t get arrested), or even recovering that old backup of when you used to work at NIST. If you don’t want us to, we won’t ask questions. May the hashrate be ever in your favor, and let's fill out a page of cryptographic history. For updates, you might want to follow me on Bluesky[13] or Mastodon[14]. *Subscribe to Cryptography Dispatches for more!* [https://words.filippo.io/dispatches/] 1: Not a typo for 512. There’s a very conveniently shaped prime at 2^521-1. We do typo that a lot in code. 2: https://saweis.net/posts/nist-curve-seed-origins.html 3: https://eprint.iacr.org/2015/1060 4: https://eprint.iacr.org/2015/1018.pdf 5: The NSA's precedents, namely Dual_EC_DRBG[15], are why some people find the seeds suspicious. I find them reassuring. First, selecting weak seeds (which are just hash inputs, not "keys" like in Dual_EC_DRBG), would not be a NOBUS backdoor[16]. Second, the Dual_EC_DRBG design immediately stuck out like a sore thumb and library authors had to be paid to implement it; this suggests the NSA is kinda bad at backdoors, not magical. 6: https://en.wikipedia.org/wiki/Fear,_uncertainty,_and_doubt 7: https://twitter.com/lauriewired/status/1700982575291142594 8: Rigidity is the design generalization of nothing up my sleeves numbers[17]. The idea is that if you set your goals explicitly and then make only obvious and rational and optimal choices in a design, there is no wiggle room to pick intentionally weak outcomes. FWIW, I think rigidity is overrated: there is no such thing as an objectively best choice, and reasonable people disagree, and it’s possible to craft rational arguments for many different choices. Anyway, it’d be nice to settle the argument by bringing the NIST curves up in their level of rigidity by cracking the seeds. 9: https://en.wikipedia.org/wiki/Prime_number_theorem 10: https://www.wolframalpha.com/input?i2d=true&i=Power%5B%5C%2840%291+-+Divide%5B1%2C521%5D%5C%2841%29%2Cx%5D+%3D+0.01 11: A better approach would be to include all the decrements up to the previous hash that generates a valid prime-order curve, but I didn't feel like reimplementing all that. If 12k hashes is too many, let me know and I'll produce the smaller, more precise list. 12: https://gist.github.com/FiloSottile/3a2105ef6d1f2bc038d756c883f99231/raw/827... 13: https://bsky.app/profile/filippo.abyssdomain.expert 14: https://abyssdomain.expert/@filippo 15: http://en.wikipedia.org/wiki/Dual_EC_DRBG 16: https://en.wikipedia.org/wiki/NOBUS 17: https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number