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

81–90 of 102 posts

Re: NIST Elliptic Curves Seeds Bounty

#81

Post by Ar-Curunir »

less_less wrote: post #74
dhx wrote: post #62

Earlier quoted context omitted.

> "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 at…

There are now fairly efficient complete formulae for prime-order curves, so the case for the NIST curves is stronger.

Re: NIST Elliptic Curves Seeds Bounty

#82

Post by acqq »

meithecatte wrote: post #73
acqq wrote: post #67

Earlier quoted context omitted.

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.

I don't think we can complain that there were retries over different human-readable seeds to make an appearance of "verifiably at random" design if the chosen human-readable seeds just haven't been published at all.

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?

Re: NIST Elliptic Curves Seeds Bounty

#84

Post by tptacek »

mike_hearn wrote: post #68
rollulus wrote: post #64

So if I understand this correctly: the community accepted those mysterious strings of unknown origin while it would’ve been trivial to replace them with different strings with a known origin, by providing another but known input to the hash?

You understand the situation correctly, hence why it's kind of disastrous. The phrases "so close" and "you had one job" seem relevant here. Unfortunately, as far as I know this would be the only case related to the NSA and cryptographic standards where someone has alleged incompetence. Normally the stories run the other way. Doubly problematic: NIST is known to have been compromised and putting backdoors into ellipti…

SHA1 was phased out, for another NIST standard, because it was known to be weak (in the sense of a likely cryptographic break --- which happened --- not in the sense of needing to be more careful using it). That's not the case with the P-curves; short of a QC attack that will break all modern curves, it's unlikely the P-curves are going to be broken.

Re: NIST Elliptic Curves Seeds Bounty

#85

Post by dfox »

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 procedures in Annex A.3.3.1 and A.3.3.2 do not really specify how you are supposed to come up with the SEED value used in the first step ("Choose an arbitrary bit string SEED"). Note that this value is part of the output that is published.

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.

Re: NIST Elliptic Curves Seeds Bounty

#86

Post by abecedarius »

throw0101a wrote: post #24
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…

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

> tweaks to DES (which later turned out to be defence against differential cryptanalysis)

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.

Re: NIST Elliptic Curves Seeds Bounty

#87

Post by exabrial »

Just curious, even if we known the origin plaintext becomes known and we can prove it's correct, this doesn't compromise the security of those curves, correct?

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.

Re: NIST Elliptic Curves Seeds Bounty

#88

Post by exabrial »

exabrial wrote: post #87

Just curious, even if we known the origin plaintext becomes known and we can prove it's correct, this doesn't compromise the security of those curves, correct? 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 th…

Ok can someone explain why my comment is drive-by downvoted? This is an important question. Thank you!

Re: NIST Elliptic Curves Seeds Bounty

#89

Post by acqq »

dfox wrote: post #85
acqq wrote: post #67

Earlier quoted context omitted.

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 procedures in Annex A.3.3.1 and A.3.3.2 do not really specify how you are supposed to come up with the SEED value used in the first step ("Choose an arbitrary bit string SEED"). Note that this value is part of the output that is published. 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 incrementin…

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

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.

Re: NIST Elliptic Curves Seeds Bounty

#90

Post by dfox »

acqq wrote: post #89
dfox wrote: post #85

Earlier quoted context omitted.

The procedures in Annex A.3.3.1 and A.3.3.2 do not really specify how you are supposed to come up with the SEED value used in the first step ("Choose an arbitrary bit string SEED"). Note that this value is part of the output that is published. 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 incrementin…

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

The whole point of the procedure as designed is to make how the constant was selected irrelevant to the security of the resulting curve.

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

Post reply on HN