NIST Elliptic Curves Seeds Bounty
words.filippo.io
words.filippo.io
At the time, the "pass a string through SHA1" thing was meant to increase confidence in the curve seeds; the idea was that SHA1 would destroy any possible structure in the seed, so NSA couldn't have selected a deliberately weak seed. Of course, NIST/NSA then set about destroying its reputation in the 2000's, and this explanation wasn't nearly enough to quell conspiracy theories.
But when Jerry Solinas went back to reconstruct the seeds, so NIST could demonstrate that the seeds really were benign, he found that he'd forgotten the string he used!
If you're a true conspiracist, you're certain nobody is going to find a string that generates any of these seeds. On the flip side, if anyone does find them, that'll be a pretty devastating blow to the theory that the NIST P-curves were maliciously generated --- even for people totally unfamiliar with basic curve math.
So: pretty fun bounty.
It's standard to use transcendental constants like pi or e for this purpose as you can't select them. A phrase could in theory be selected to yield a more desirable hash
(Dumb geometry joke, sorry. I know what you mean.)
Assuming that you publish your definition of "a nice curve" then third parties can verify that you used the first offset in pi that worked.
So maybe you get to pick the most crackable for you out of 25 options. But you can't hide a proper backdoor like that.
If one may choose between one or the other without arousing suspicion, that's one bit of entropy.
If I can add the possibility of sin(1) and cos(1), that's two bits.
And remind me: are we using sha1, or md5? Or perhaps sha1 -> md5, or md5 -> sha1?
And so on, until I have enough bits to reimplement the suspicious seed in the cracks of all these innocuous, and very poorly specified "standard" choices.
Dan Bernstein (and some other cryptographer?) wrote about this and did a demo creating over a million curves in a short/practical amount of time on commodity hardware. All of them had seeds specified using a "standard" method like what you mention above.
It makes me think all cryptographers ought to just go ahead and choose suspicious seeds where prudent, kinda like if you're going to play the lottery, just go ahead and choose the numbers 1 2 3 4 5 etc. At least then you get instant, free information about the lack of knowledge of the people who complain that you're doing it wrong.
For a longer history see the mentioned-in-article paper by Koblitz and Menezes, "A Riddle Wrapped in an Enigma" (which is more asking why the NSA said, in 2015, that things should move towards a post-quantum world):
* https://eprint.iacr.org/2015/1018
* https://eprint.iacr.org/2015/1018.pdf
The same "backdoor" thinking seems to have been present with (EC)DSA:
> Proponents of RSA bitterly opposed DSA, and they claimed that the NSA was promoting DSA because they had inserted a back door in it (“No Back Door” was the slogan of the anti-DSA campaign). However, they gave no evidence of a back door, and in the two decades since that time no one has found a way that a back door could be inserted in DSA (or ECDSA).
Then there was this little tidbit:
> As the heated debate contin- ued, the NSA representative left to make a phone call. When he returned, he announced that he was authorized to state that the NSA believed that ECC had sufficient security to be used for secure communications among all U.S. government agencies, including the Federal Reserve. People were stunned. In those days the NSA representatives at standards meetings would sit quietly and hardly say a word. No one had expected such a direct and unambiguous statement from the NSA. The ECC standards were approved.
Other actions by the NSA that were treated as suspicious were tweaks to DES (which later turned out to be defence against differential cryptanalysis) and weaknesses in the original SHA ("SHA-0") which the final version ("SHA-1") does not have.
ElGamal/DSA is fragile and difficult to implement securely in a way that doesn't reveal secret k. ECC (and somewhat particularly NIST curves[1]) is also very difficult to implement securely from side channel attacks[2].
Consideration of "backdoors" should be broader than just mathematical equations on paper. "backdoors" could also include deliberate choice of algorithm or parameters that are fragile and difficult to implement in a secure way to minimise risk of side channel leakage of secrets. This is especially important in a whole variety of applications such as passports, payment cards and TPMs.
[1] https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf#p...
[2] Specifically, implementation of: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic...
IMHO this isn't evidence of a backdoor. Side-channel protection is hard. RSA decryption and especially keygen are also tricky to implement in a side-channel-protected way, and a widespread timing attack on RSA decryption in many libraries was published earlier this year [3].
The NIST p-curves used the state-of-the-art elliptic curve shape for general operations when they were released: short Weierstrass curves over prime fields. Edwards curves are easier to defend against side channels and are overall a better choice (with their own rough edges, mostly involving the cofactor), but those were not known until 2007. Montgomery curves (similar rough edges to Edwards, plus the point at infinity) were known earlier and are nice for key exchange, but they are not as nice for signatures.
Overall I would not choose the NIST curves for a new design today, because Edwards/Montgomery curves are a better choice. But I think the evidence they were backdoored (mathematically or otherwise) is weak.
The NSA's mission has changed, in the sense of its real priorities for securing comms vs. spying on them. They were clearly different at the time of creation of DES vs. at the Snowden leaks, so I wouldn't take that episode as too much evidence of helpful intent in the 90s.
For those curves the choice of G is the only particularly high entropy input into their selection, and it's provably almost irrelevant-- the choice of it lets them know one specific arbitrary discrete log. (you can imagine a contrived protocol where this would be a backdoor, but it would be a pretty contrived protocol). But since it's the only really unknown parameter I thought it was worth searching for.
If someone does find the seed used for the P-curves it might also be similar to the one used for the the generators of those other curves and solve their minor mystery too.
IDK, if I don't think that finding that a seed matches a hash of "Give Jerry a raise of $100000 dollars now!!!" is any evidence for that, because if I had a desire to generate malicious constants, and knew some unusual property that they must have to be weak, then nothing would prevent me from generating hashes of many, many variations of similar strings until one gives me constants with the properties I need.
If you're convinced the P-curves must be backdoored, despite the computer science arguments that suggests they really couldn't have been, then you should comfort yourself in the knowledge that we're probably not going to find the seed strings any time soon; presumably Solinas tried pretty hard himself!
If you were evil and motivated you'd probably want to hide your variables in the innocent looking part, the simple English or the punctuation, instead.
GP is making a different argument along the lines of last week’s Twitter fad generating intelligible English sentences which spell out the first few bytes of their hash.
I don't think that's what happened, but it does mean that "some variation of give Jerry a raise" doesn't mean the value wasn't chosen maliciously.
In the article, under the subtitle "Step back, what is this about?" is:
"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."
Note the sentence: “verifiably at random” according to ANSI X9.62.
Now, the mentioned ANSI X9.62 describes very formal algorithms of what “verifiably at random” should mean:
"If it is desired that an elliptic curve be generated verifiably at random, then select parameters (SEED, a, b) using the technique specified in Annex A.3.3.1"
and then goes on to specify an exact algorithm both how the parameters are selected in A.3.3 and then in A.3.4 the verification algorithm: "The technique specified in this section verifies that the defining parameters of an elliptic curve were indeed selected using the method specified in Annex A.3.3"
So, if I understand correctly, the authors spent enough energy both to construct the algorithms to generate the constants and make the SEED public as well as the algorithms to later verify the parameters given the publicly known SEED as an input. And to publish all that in ANSI X9.62.
If that was the idea of “verifiably at random” according to ANSI X9.62, and if then nobody knows the SEED, then it appears that the very procedure, for which a lot of energy was spent to be developed or described, was just not followed. From which it can be concluded that the "if" condition of the sentence was just not true:
"If it is desired that an elliptic curve be generated verifiably at random..."
(Not to mention that the algorithms published there clearly aren't "simply SHA1 hashes" in the sense result = SHA1( seed ) but, casually looking, a concatenation of only some bits of output from multiple SHA1 runs over the increments of the seed, which could suggest that nobody who tries any human written string as a seed would ever find a result by expecting a match of a whole constant with an output of a single SHA1 pass? Has anybody calculated how big would be a chunk of bits from a single SHA1 run actually for every of the constants?)
Now, I probably miss something here, if it is so, I'd like to know what.
And if the argument is that the publishing of human-readable seeds was unnecessary because the retries of the procedure could have been performed until some exploit was possible, why even define and publish these definitions? Was it an error? Or something else?
The claim here is that the procedure used for choosing the SEED in the first step involved SHA-1 of some ASCII text with a counter.
By the way the construction with incrementing counter (steps 3 respective 4) is horribly inefficient PRNG that expands/shrinks the entropy in the SEED to the size of field element one bit at a time. I suspect that the inefficiency is intentional to make it even more obvious that authors did not try enough SEEDs to be able to specifically select weak one.
That's the story as much as I see it: there's a constant that doesn't appear to be "arbitrary" enough in a sense that there's a suspicion that it could be too "special" if nobody can recognize it, and nobody can show how that one was generated.
And as there's an official procedure to turn something to something "more random" that "something" appears to be still missing.
BTW I don't think that the "inefficiency" you see in the steps there changes anything.
Also you have to consider the historical context. The procedure was originally designed to generate parameters for cryptosystems that were very much built on the assumption that SHA-1 is secure hash. Any method to choose a weak SEED in a reasonably practical way involves either breaking SHA-1 (collision does not really help, you would need preimage) or the underlying ECC structure having some gaping security issue that only NSA knows about (ie. there being ridiculously many weak curves).
At least, that's my understanding why there's still talk about it all, and this bounty: those who don't like the opaque constants argue: why aren't they "open", if really "irrelevant"? Now, if the bounty shows that the constants come from something like
SHA-1("Jerry and Alice deserve a raise. 1398")
then all this looks a little better, especially if it can be shown that that "1398" was the first integer that "worked" for the selected phrase, according to the publicly known criteria.
GCHQ in the U.K. hires more mathematicians than any other research institute or University in the country. Not sure about the US equivalents but I imagine it’s similar.
Diffie-Helman key exchange was known about by GCHQ and the NSA prior to it being rediscovered by Diffie and Helman. I think it’s hard to assume anything about the underlying capabilities of intelligence institutions. Not saying they do know this but it’s also not impossible, this stuff is their bread and butter.
The usual response to these concerns is to argue that academics are so excellent that they would certainly have discovered what the NSA was up to by now, if there was a way to do it, and anyone who doesn't agree with that is as FUDy pleb who just doesn't get it. The article repeats this party line, although it's great to now see the problem being taken more seriously with an organized bounty programme. I'll be surprised but happy if anyone actually finds pre-images. But the frequency with which concerns are blown off here is just not good enough.
I've done some cryptography work in the past and for several years had to regularly review cryptography papers as part of my job. I've attended cryptography conferences, talked with researchers, implemented various "exotic" things with elliptic curve cryptography and so on. Not exactly an insider but not a complete outsider either. The party line here looks very dangerous to me.
Let's recap the arguments here because neither of them seem strong and neither are actually mathematical at their core.
1. If there was a way to execute a kleptographic attack on NIST curve standardization, academics would have found it by now. If not academics, then someone in industry.
2. Dual_EC_DRBG was detected as suspicious immediately, so the public cryptography community is good at spotting back doors.
For (1) why should that be so? It actually seems unlikely to me. Cryptography suffers the same problems as the rest of academia w.r.t. the file drawer problem and "publish or perish" incentives. If you're an up and coming university researcher, which path is more profitable for you? Develop some clever new zero knowledge proof algorithm and be fairly certain to publish some cool new paper that gets cited a lot, or start attacking an algorithm that "everyone" already knows to be incredibly strong and almost certainly come up with nothing. If you take the latter the expected outcome is that you languish in obscurity at best or simply perish at worst (lose funding, exit academia with nothing to show and being seen as a crank).
Put another way the argument for the strength of academic understanding is that lots of really clever people have studied this in depth and found nothing. There is a Consensus Of Experts. But because you don't get to publish null results in academia, there's actually no way to know how much effort has been put towards this kind of problem. That's why assertions about academic crypto-analytic supremacy are always so handwavey and difficult to reason about. There's no actual numerical proof of work being done, and we know that some fields of academia have extreme difficulty with things being declared a "consensus" for social reasons that later have to be walked back.
Moreover, researching kleptography specifically (how to backdoor standards) isn't a good career path because kleptography isn't useful for anything unless you're the NSA, so you probably won't be able to easily transition to a post-academic career in industry on the back of that expertise and you won't get many citations.
The NSA doesn't have any of these problems. It can pay better wages than academia, hire more researchers than all of academia put together, and then assign them full time to research that is likely to be a dead end or which is useful only for backdooring standards. It can also easily build multi-disciplinary teams and fund research that academic cryptography just can't tackle at all due to lack of hardware budgets. And it has been doing exactly that for decades.
If I had to bet on whose understanding of ECC is better, the NSA's or academia's, well, all the firepower is on the side of the government. It's not even a close competition. In fact we can even measure how much firepower the government has, hence the well worn line about how many maths PhDs they hire, but we actually have no idea how much firepower academia levels at this part of the problem space.
So we're left with argument (2), people immediately raised the alarm about Dual_EC_DRBG so the NSA must actually kinda suck at designing backdoors. But this isn't an ideal argument because people immediately raised concern about the NIST curves too. The only difference is that in the former case, there was already a known algorithm that could be used to pull off the needed attack, and in this case there isn't.
Fundamentally there's no reason this debate should even be needed. It's been known for decades how to avoid doubt here, that's the whole reason the NIST curves are the output of SHA1 to begin with. The best time to phase out the NIST curves was decades ago, the second best time is today.
As a side note, in the past a PhD student was tasked with the "not interesting sounding and apparently useless in practice" task of filling the gaps in OCB2's security proof. That's how it was discovered that it was utterly broken.
I find this deeply troubling. So the seeds were provided by the NSA and they said "don't worry, they were generated hashing a trivial sentence. Unfortunately we forgot it now, but trust us, it's just Jerry joking about getting a raise, nothing more..."
I can't believe this didn't undergo further scrutiny earlier, and I can't believe the seeds haven't been chosen in a more sensible way, such as combining random seeds provided by different parties with competing interests, also including hardware RNGs, etc...
This is because you're looking at it from the perspective of someone living in 2023 with knowledge of what happened between the 90s and now. While that would have been a good way to go, at the time few people would have seen the need for it.
Doubly problematic: NIST is known to have been compromised and putting backdoors into elliptic curve related standards, the fact that this mechanism didn't create trust was pointed out immediately, and neither NIST nor the NSA did anything to address the concern. Just like with Dual_EC_DRBG.
Triply problematic: the NSA explicitly told people in 2015 not to upgrade past the NIST curves to other curves, because quantum computers will soon be good enough to break ECC entirely and so everyone should switch to post-quantum crypto instead (which is new and still experimental widely used etc). If ECC worked fine, QC was far off and you wanted to keep people on the NIST curves for as long as possible this is exactly what you would say.
The cryptography community has not exactly covered itself in glory over this situation. It's been nearly 25 years now. There are newer curves that don't have this problem, why are the NIST curves still being used by anything? Where is the effort to phase them out, like there was with SHA1? This article even seems to be advertising them.
The list of plausible variations one should try might never be exhaustive, but this page doing nothing but generating a sha1 hash makes it practically impossible to find you the hash even if you got the string right with correct punctuation and capitalization. The easiest/least thing it could do is check if the first or last ten bytes match to see if the resulting hash was incremented, though even that would mostly be asking people to waste time on the page, since the author knows it won't go anywhere.
It should be remarked on the page that it is a toy for demonstration purposes and will not actually let you find the seed even if you guessed correctly
> Something I've learned from a career of watching cryptographer flame wars: Don't bet against Bernstein, and don't trust NIST.
I should amend that to:
Something I've learned from a career of watching cryptographer flame wars: Don't bet against Bernstein or Filippo, and don't trust NIST. When these two rules are in conflict... still don't trust NIST.
Finding what amounts to a passphrase just given a hash was still generally untractable I thought.
Did Jerry get a raise?
I'm showing my age here, but as someone that lived through and had to mitigate the results of the md5 disater, I'm all for a variety of [verified] cryptographic algorithms being available. I think having edwards curves, NIST curves, or others is healthy for the ecosystem.
(Sorry, couldn't help myself.)