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

21–30 of 102 posts

Re: NIST Elliptic Curves Seeds Bounty

#21

Post by tedunangst »

monocasa wrote: post #18
woodruffw wrote: post #6

Earlier quoted context omitted.

Yes, SHA-1 is still considered preimage resistant. But preimage resistance isn't that important here, if the hypothesis about seed structure is correct: SHA-1 is also very fast and trivial to parallelize, and someone dedicated to exploring the permutation space of "Jerry needs a raise" stands a decent chance of discovering the original input.

Except the Jerry needs a raise story has been floating around for a while now. The obvious choices have been mined out.

How much actual effort has been spent mining this space?

Re: NIST Elliptic Curves Seeds Bounty

#22

Post by woodruffw »

monocasa wrote: post #18
woodruffw wrote: post #6

Earlier quoted context omitted.

Yes, SHA-1 is still considered preimage resistant. But preimage resistance isn't that important here, if the hypothesis about seed structure is correct: SHA-1 is also very fast and trivial to parallelize, and someone dedicated to exploring the permutation space of "Jerry needs a raise" stands a decent chance of discovering the original input.

Except the Jerry needs a raise story has been floating around for a while now. The obvious choices have been mined out.

I hadn't heard it before. Whether or not it's an old story is secondary to visibility/mass awareness.

Re: NIST Elliptic Curves Seeds Bounty

#23

Post by tptacek »

colmmacc wrote: post #8
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…

By the late nineties using both MD5 and SHA1 for "additional robustness" together in ad-hoc constructions was also en vogue. SSLv2 and SSLv3 are good examples. The outputs match the size of a SHA1, but it wouldn't be that shocking if the pipeline were some form of echo "$string" | md5sum | sha1sum.

What's smart about this bounty is that these kinds of silly hashing constructions, and scalable pipelines for figuring them out through brute force, are the bread and butter of password crackers, which is practically a sport now. So you'd be optimistic that if the problem is interesting enough, somebody will work it out if there's like, a pre-MD5 hash or something.

Re: NIST Elliptic Curves Seeds Bounty

#24

Post by throw0101a »

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

Re: NIST Elliptic Curves Seeds Bounty

#27

Post by kevincox »

tedunangst wrote: post #19
worewood wrote: post #11

Earlier quoted context omitted.

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

What do you if pi doesn't create a nice curve?

You come up with a hopefully simple rule to try again. Like skip the first byte and try again.

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.

Re: NIST Elliptic Curves Seeds Bounty

#28

Post by nullc »

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

Re: NIST Elliptic Curves Seeds Bounty

#29

Post by PeterisP »

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 from generating hashes of many, many variations of similar strings until one gives me constants with the properties I need.

Re: NIST Elliptic Curves Seeds Bounty

#30

Post by tedunangst »

kevincox wrote: post #27
tedunangst wrote: post #19

Earlier quoted context omitted.

What do you if pi doesn't create a nice curve?

You come up with a hopefully simple rule to try again. Like skip the first byte and try again. 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.

Ah, of course, just drop bits until it "happens" to work. You would suggest that, instead of the simple and obvious solution of using pi times e.
Post reply on HN