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

91–100 of 102 posts

Re: NIST Elliptic Curves Seeds Bounty

#91

Post by acqq »

dfox wrote: post #90
acqq wrote: post #89

Earlier quoted context omitted.

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

And we come once again back to the start: _because_ there's an explicit algorithm right there in the standard which allows to start from something "not special" like the digits of Pi or even the ASCII strings of the beginning of the Declaration of Independence, why the completely opaque constants instead? Even if it's, as Filippo suggests, because "the counter has to be there because only one in every 192 to 521 hashes is actually good to make a curve out of", if the counter is a known part of the process of such a selection, all these details could still have been "open".

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.

Re: NIST Elliptic Curves Seeds Bounty

#93

Post by matja »

PeterisP wrote: post #29
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…

> if anyone does find them, that'll be a pretty devastating blow to the theory that the NIST P-curves were maliciously generated 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 f…

Exactly. How many gramattically correct sentances are there, vs what is the probability that a "random" hash used as an EC seed results in poor security? Research[0] has demonstrated it's not a theoretical vulnerability in the EC selection process.

[0] https://bada55.cr.yp.to/bada55-20150927.pdf

Re: NIST Elliptic Curves Seeds Bounty

#94

Post by Vecr »

exabrial wrote: post #88
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!

Finding it actually increases the confidence is the curves, it's a parameter that's known and fixed anyway so it's not secret or anything.

Re: NIST Elliptic Curves Seeds Bounty

#96

Post by cnull »

nullc wrote: post #28
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…

I burned an unreasonable amount of cpu power searching for input that were used to produce the ~166 bit 'random' value used to construct G in secp256k1 and secp224k1 without success. (in both cases the parameters choice of G is the double of a point with a suspiciously sized x coordinate, and the same for both curves). For those curves the choice of G is the only particularly high entropy input into their selection,…

[flagged]

Re: NIST Elliptic Curves Seeds Bounty

#97

Post by cnull »

cnull wrote: post #96
nullc wrote: post #28

Earlier quoted context omitted.

I burned an unreasonable amount of cpu power searching for input that were used to produce the ~166 bit 'random' value used to construct G in secp256k1 and secp224k1 without success. (in both cases the parameters choice of G is the double of a point with a suspiciously sized x coordinate, and the same for both curves). For those curves the choice of G is the only particularly high entropy input into their selection,…

[flagged]

[flagged]

Re: NIST Elliptic Curves Seeds Bounty

#98

Post by cnull »

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…

[flagged]

Re: NIST Elliptic Curves Seeds Bounty

#99

Post by littlestymaar »

tptacek wrote: post #53
pests wrote: post #43

Earlier quoted context omitted.

Its funny - all this doubt and suspicion of the NSA but then you end your post about how NSA has been saving our asses. Maybe they aren't so bad afterall? /s

They're not, in fact, comic book villains. They have a pretty understandable mission, and then a set of organizational values that are sharply different than those of technologists.

I'm not sure you're helping here, given such a description also fits Hamas or drug cartels very well…
Post reply on HN