Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

NIST Elliptic Curves Seeds Bounty

words.filippo.io

Post reply on HN
Print view View original

71–80 of 102 posts

Re: NIST Elliptic Curves Seeds Bounty

#71

Post by raverbashing »

stavros wrote: post #66
cperciva wrote: post #51

Earlier quoted context omitted.

Conceivably there's a subset of weak values and Jerry tried "Give me more money", "Jerry deserves more money", etc until he found a phrase which produced a weak value. 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.

Agreed, I wouldn't have thought so a few weeks ago, but after seeing the messages that contain the first few SHA bytes of themselves in themselves, I don't know how implausible it is that they might have generated billions of strings and hashes and then chosen the weaker ones.

I'd think it's a bit implausible. Especially with the computing power (and optimizations) available at the time

Re: NIST Elliptic Curves Seeds Bounty

#72

Post by GTP »

This is yet another instance where more transparency on the NIST/NSA side would have been beneficial in the long run. If they said from the start, "here are the seeds, we generated them by computing SHA1(insert_solinas_string_here)" the whole debate would have never started in the first place.

Re: NIST Elliptic Curves Seeds Bounty

#73

Post by meithecatte »

acqq wrote: post #67
tptacek wrote: post #3

Some of the backstory here (it's the funniest fucking backstory ever): it's lately been circulating --- though I think this may have been somewhat common knowledge among practitioners, though definitely not to me --- that the "random" seeds for the NIST P-curves, generated in the 1990s by Jerry Solinas at NSA, were simply SHA1 hashes of some variation of the string "Give Jerry a raise". At the time, the "pass a strin…

However, I don't find it funny reading all the "gory" details: 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." N…

The standards claim that the existence of such a (SEED, a, b) tuple is enough to show that there is nothing special about the curve in question. But if one in a billion curves have a special property that only you know about, which would make it easier for you to attack the cryptosystem, you can try a variety of different SEED values until you find a desirable curve.

Re: NIST Elliptic Curves Seeds Bounty

#74

Post by less_less »

dhx wrote: post #62
throw0101a wrote: post #24

Earlier quoted context omitted.

> Some of the backstory here (it's the funniest fucking backstory ever): it's lately been circulating --- though I think this may have been somewhat common knowledge among practitioners, though definitely not to me --- that the "random" seeds for the NIST P-curves, generated in the 1990s by Jerry Solinas at NSA, were simply SHA1 hashes of some variation of the string "Give Jerry a raise". For a longer history see the…

> "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)." 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" shou…

> 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].

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.

[3] https://people.redhat.com/~hkario/marvin

Re: NIST Elliptic Curves Seeds Bounty

#75

Post by GTP »

mike_hearn wrote: post #70
physicsguy wrote: post #59

> 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. 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 rediscove…

I think you're right to be suspicious, especially because the arguments for it not being possible are presented as if they are mathematical but are actually social. 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…

I'm still not fully convinced by your point about what's best to fuel an academic career. While putting it as trying to find vulnerabilities into some specific cryptosystem largely believed to be secure indeed doesn't sound that interesting, if you instead put it as finding new attacks for elliptic curve cryptography we're back again the "cool paper with lots of citations" territory.

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.

Re: NIST Elliptic Curves Seeds Bounty

#76

Post by GTP »

zakk wrote: post #61

> The NIST elliptic curves that power much of modern cryptography were generated in the late ‘90s by hashing seeds provided by the NSA. 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 und…

> 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.

Re: NIST Elliptic Curves Seeds Bounty

#77

Post by mike_hearn »

GTP wrote: post #75
mike_hearn wrote: post #70

Earlier quoted context omitted.

I think you're right to be suspicious, especially because the arguments for it not being possible are presented as if they are mathematical but are actually social. 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…

I'm still not fully convinced by your point about what's best to fuel an academic career. While putting it as trying to find vulnerabilities into some specific cryptosystem largely believed to be secure indeed doesn't sound that interesting, if you instead put it as finding new attacks for elliptic curve cryptography we're back again the "cool paper with lots of citations" territory. As a side note, in the past a PhD…

You only get a cool paper with lots of citations if you actually do find a new attack. If you spend a four year PhD searching and come up with nothing, which is what the field tells you to expect, then you end up with nothing. At the NSA you get a four year salary, maybe even a promotion, who knows.

Re: NIST Elliptic Curves Seeds Bounty

#78

Post by postexitus »

gregw2 wrote: post #65
tptacek wrote: post #26

Earlier quoted context omitted.

Sadly, Jerry Solinas died a few months ago.

Now he needs a different kind of raise? (Sorry, couldn't help myself.)

According to D&D 5e, you can only case Raise Dead if the subject is dead for less than 10 days. Even if those conditions are satisfied, the creature's soul needs to be both willing and at liberty to rejoin the body. So, no.

Re: NIST Elliptic Curves Seeds Bounty

#79

Post by chinathrow »

zakk wrote: post #61

> The NIST elliptic curves that power much of modern cryptography were generated in the late ‘90s by hashing seeds provided by the NSA. 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 und…

Well, with today's internet traffic mostly being encrypted, what would they need their large data centers such as Bluffdale for?

https://en.wikipedia.org/wiki/Utah_Data_Center

Re: NIST Elliptic Curves Seeds Bounty

#80

Post by Ar-Curunir »

dhx wrote: post #62
throw0101a wrote: post #24

Earlier quoted context omitted.

> Some of the backstory here (it's the funniest fucking backstory ever): it's lately been circulating --- though I think this may have been somewhat common knowledge among practitioners, though definitely not to me --- that the "random" seeds for the NIST P-curves, generated in the 1990s by Jerry Solinas at NSA, were simply SHA1 hashes of some variation of the string "Give Jerry a raise". For a longer history see the…

> "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)." 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" shou…

The only reason DSA is used is because the natural signature scheme was patented (Schnorr).
Post reply on HN