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

51–60 of 102 posts

Re: NIST Elliptic Curves Seeds Bounty

#51

Post by cperciva »

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…

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.

Re: NIST Elliptic Curves Seeds Bounty

#52

Post by Mistletoe »

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…

Did he get that raise?

Re: NIST Elliptic Curves Seeds Bounty

#53

Post by tptacek »

pests wrote: post #43
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…

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.

Re: NIST Elliptic Curves Seeds Bounty

#54

Post by Aachen »

xu3kev wrote: post #49

If you're feeling lucky, you can give it a shot by guessing the sha1 hash here: https://wending.dev/hash_guessing/

Wait, that just generates the sha1 of your input string and nothing more? Because as the post says, it has to include a counter of some sort. I'm sure the NSA's seeder didn't just sit there and enter 500 unique phrases until they hit one that gives a nice curve, if they had any idea about cryptography and computers whatsoever. Or even if that's how it went down, variants with a dot at the end, capitalizing the sentence, title casing, ...

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

Re: NIST Elliptic Curves Seeds Bounty

#55

Post by pclmulqdq »

tptacek wrote: post #35
pclmulqdq wrote: post #34

Earlier quoted context omitted.

I might be suspicious of “Give Jerry a $3263958374 raise,” but that would launch an interesting hunt as to what property they were exactly mining for.

For the reason stated in the article, it's actually pretty likely that there's a counter in there somewhere. A 31-bit number like "3263958374" doesn't seem especially interesting cryptographically.

Yeah, that counter is separate from a counter embedded in an ASCII string. The one thing that kind of string indicates is that it almost certainly wasn't the first string they tried.

Re: NIST Elliptic Curves Seeds Bounty

#57

Post by duskwuff »

Dylan16807 wrote: post #45
quickthrower2 wrote: post #39

Earlier quoted context omitted.

You could however test different schemes like this prior to announcing the scheme.

There's only so much room for simple methods. 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.

And if it's possible to get an easy-to-break configuration in a relatively small number of attempts, it's probably because there's something fundamentally broken about the entire construct, not just the seed you picked. And that sort of brokenness is likely to be a lot harder to hide.

Re: NIST Elliptic Curves Seeds Bounty

#58

Post by jeffrallen »

I recently said:

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

Re: NIST Elliptic Curves Seeds Bounty

#59

Post by physicsguy »

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

Re: NIST Elliptic Curves Seeds Bounty

#60

Post by dmurray »

api wrote: post #47
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 hope it's something like SHA1("Bill Clinton is a poopy head.")

I'm hoping for something more like "The bodies are buried at 2100 15th St".
Post reply on HN