Bounty offered for secret NSA seeds behind NIST elliptic curves algo

Tue Oct 10 12:50:13 PDT 2023

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 at yahoo.com <jdb10987 at yahoo.com> wrote:
> https://www.bleepingcomputer.com/news/security/bounty-offered-for-secret-nsa-seeds-behind-nist-elliptic-curves-algo/

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 at 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/827d3797dd6df34f6bf8b6a843ebd62cab62758a/nist-and-ansi-prime-order-seeds-increments-99-percent.txt
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