Bounty to Recover NIST's Elliptic Curve Seeds | Hacker News Reader

Bounty to Recover NIST's Elliptic Curve Seeds

schneier.com

122 pointsvintagedave17 comments

This was brought up about a week ago, previous discussion - https://news.ycombinator.com/item?id=37784499

Linked directly in the article! Now we are looped!

FWIW, I threw a few GPU-weeks at this trying, for example, all variants of "[Gg]ive <name> a <noun>" or "[Gg]ive <name> and <name2> a <nice-thing-noun>", with various ending punctuation and all numbers from 0-9999 appended, and several other seed patterns, and didn't find anything, using just sha-1(phrase).

There are some other possibilities such as iterated sha1 with addition inside, etc., but I got bored. But before you decide to try the easy way, just note that it's probably not quite as easy "Give Jerry a raise" makes it sound. :-)

Not at all into cryptography, but I did some research last time this was posted. Came to the conclusion that the only chance anyone has would involve:

a) Hunting down and interviewing retired NSA employees b) Spending something like 12K (the prize pool) smashing it with computation, and maybe an AI model to generate useful passphrases.

The person who created those strings died so you won't be able to hunt him down. He was asked just before he died about them and couldn't remember what he used (or in conspiracy mode he wouldn't say)

The guy who generated them said he believed the phrase was a variation of "Give Jerry a raise" --- but he couldn't find/recreate it himself.

It does seem ripe for LLM use: have LLMs generate lots of variations/templates that then you expand with different formatting, numbers at the end, etc.

Too bad there aren't a ton of SHA-1 ASICs sitting around, but that hash was never used in cryptocurrency mining.

There probably are a ton of SHA-1 ASICs sitting around. In a classified, secure compound.

SHA1 password hashes --- which are often iterated and much harder to crack than a simple hash --- are bread and butter for password crackers.

Wouldn't the x86 SHA extensions be as good as an ASIC? You can get a lot of chips for relatively cheap.

I’m not sure how seeing the generating text would give people confidence that the seeds don’t have certain properties that are useful for cryptanalysis. It’s the same issue with nothing-up-my-sleeve constants. If they aren’t agreed upon before design begins, you could iterate on an infinite set of benign-looking constants until you found a set with desirable properties.

It's only if there's a relatively big class of weak curves that you know about that you can find a seed that generates one. It can't be a small set of degenerate cases.

So it definitely adds some confidence.

I bet he couldn't find it because of added/omitted trailing EOL

Or notepad inserted a UTF8 BOM.

If a NIST scientist wanted a random sequence of digits to act as a seed, why wouldn't they just use a hardware random number generator to create them? Surely NIST has some laying around, even back in the 1990's.

It comes down to transparency. How would an external observer tell that the RNG wasn't rigged?

As opposed to "I used a few random English words, but I'm not going to tell anyone what they were, good luck trying to guess them". Would it be less transparent to say "We combined the output of our hardware RNG at this site and one at another lab across the country to help eliminate bias, here's the two input strings, and here is the final string we came up with".

Reply on news.ycombinator.com