10 ms·
NIST Elliptic Curves Seeds Bounty
- hellowien 3y ago[flagged]
- hellowien 3y ago[flagged]
- hellowien 3y ago[flagged]
- mcpherrinm 3y agoI'm one of the people contributing to the bounty because if it really is a password-crackable phrase, it would be of significant historical impact to know.
- tptacek 3y agoSome 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 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. Of course, NIST/NSA then set about destroying its reputation in the 2000's, and this explanation wasn't nearly enough to quell conspiracy theories. But when Jerry Solinas went back to reconstruct the seeds, so NIST could demonstrate that the seeds really were benign, he found that he'd forgotten the string he used! If you're a true conspiracist, you're certain nobody is going to find a string that generates any of these seeds. On the flip side, if anyone does find them, that'll be a pretty devastating blow to the theory that the NIST P-curves were maliciously generated --- even for people totally unfamiliar with basic curve math. So: pretty fun bounty.
- colmmacc 3y agoBy 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.
- tptacek 3y agoWhat'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.
- worewood 3y ago> 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
- tedunangst 3y agoWhat do you if pi doesn't create a nice curve?
- some_furry 3y agoDoesn't pi by definition make a nice curve? (Dumb geometry joke, sorry. I know what you mean.)
- kevincox 3y agoYou 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.
- monocasa 3y agoI mean sha-1 is for sure broken, but I thought that was mainly concerning stuff like collisions via a length extension attack and other known plaintext attacks. Finding what amounts to a passphrase just given a hash was still generally untractable I thought.
- tptacek 3y agoIt's a simple dictionary attack, which is how most password hashes are broken. This has really nothing to do with SHA1 itself.
- woodruffw 3y agoYes, 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.
- monocasa 3y agoExcept the Jerry needs a raise story has been floating around for a while now. The obvious choices have been mined out.
- tedunangst 3y agoHow much actual effort has been spent mining this space?
- woodruffw 3y agoI hadn't heard it before. Whether or not it's an old story is secondary to visibility/mass awareness.
- ilc 3y agoNow, for the real question: Did Jerry get a raise?
- glompers 3y agoThey're still in seed stage
- freedude 3y agoI came here for this...
- quickthrower2 3y agoHe got a rise out of the conspiracy people
- deleted 3y ago[deleted]
- vagab0nd 3y agoHere's professor Dan Boneh explaining the background: https://youtu.be/8WDOpzxpnTE?t=892 https://youtu.be/8WDOpzxpnTE?t=892
- nembal 3y agoHas Jerry ever got the raise? (:
- tptacek 3y agoSadly, Jerry Solinas died a few months ago.
- gregw2 3y agoNow he needs a different kind of raise? (Sorry, couldn't help myself.)
- postexitus 3y agoAccording to D&D 5e, you can only case Raise Dead if the subject is dead for less than 10 days. Even if those conditions are satisfied, the creature's soul needs to be both willing and at liberty to rejoin the body. So, no.
- quickthrower2 3y agoNo but you might get a $12k bonus
- cushpush 3y agoit's a joke right
- cushpush 3y agoYou guys are gonna revisit this post in 20 years and see I was right, cracking ECC is impossible, and starting with a "could have looked like this" seed phrase is a wild goose chase multiplied by a needle in a haystack.
- henry-aryn-ai 3y ago[flagged]
- xu3kev 3y agoIf you're feeling lucky, you can give it a shot by guessing the sha1 hash here: https://wending.dev/hash_guessing/ https://wending.dev/hash_guessing/
- Aachen 3y agoWait, 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
- bigbacaloa 3y ago[dead]
- jeffrallen 3y agoI 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.
- physicsguy 3y ago> 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.
- geraldwhen 3y agoThe NSA employs US math professors in number theory.
- mike_hearn 3y agoI 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 get it. The article repeats this party line, although it's great to now see the problem being taken more seriously with an organized bounty programme. I'll be surprised but happy if anyone actually finds pre-images. But the frequency with which concerns are blown off here is just not good enough. I've done some cryptography work in the past and for several years had to regularly review cryptography papers as part of my job. I've attended cryptography conferences, talked with researchers, implemented various "exotic" things with elliptic curve cryptography and so on. Not exactly an insider but not a complete outsider either. The party line here looks very dangerous to me. Let's recap the arguments here because neither of them seem strong and neither are actually mathematical at their core. 1. If there was a way to execute a kleptographic attack on NIST curve standardization, academics would have found it by now. If not academics, then someone in industry. 2. Dual_EC_DRBG was detected as suspicious immediately, so the public cryptography community is good at spotting back doors. For (1) why should that be so? It actually seems unlikely to me. Cryptography suffers the same problems as the rest of academia w.r.t. the file drawer problem and "publish or perish" incentives. If you're an up and coming university researcher, which path is more profitable for you? Develop some clever new zero knowledge proof algorithm and be fairly certain to publish some cool new paper that gets cited a lot, or start attacking an algorithm that "everyone" already knows to be incredibly strong and almost certainly come up with nothing. If you take the latter the expected outcome is that you languish in obscurity at best or simply perish at worst (lose funding, exit academia with nothing to show and being seen as a crank). Put another way the argument for the strength of academic understanding is that lots of really clever people have studied this in depth and found nothing. There is a Consensus Of Experts. But because you don't get to publish null results in academia, there's actually no way to know how much effort has been put towards this kind of problem. That's why assertions about academic crypto-analytic supremacy are always so handwavey and difficult to reason about. There's no actual numerical proof of work being done, and we know that some fields of academia have extreme difficulty with things being declared a "consensus" for social reasons that later have to be walked back. Moreover, researching kleptography specifically (how to backdoor standards) isn't a good career path because kleptography isn't useful for anything unless you're the NSA, so you probably won't be able to easily transition to a post-academic career in industry on the back of that expertise and you won't get many citations. The NSA doesn't have any of these problems. It can pay better wages than academia, hire more researchers than all of academia put together, and then assign them full time to research that is likely to be a dead end or which is useful only for backdooring standards. It can also easily build multi-disciplinary teams and fund research that academic cryptography just can't tackle at all due to lack of hardware budgets. And it has been doing exactly that for decades. If I had to bet on whose understanding of ECC is better, the NSA's or academia's, well, all the firepower is on the side of the government. It's not even a close competition. In fact we can even measure how much firepower the government has, hence the well worn line about how many maths PhDs they hire, but we actually have no idea how much firepower academia levels at this part of the problem space. So we're left with argument (2), people immediately raised the alarm about Dual_EC_DRBG so the NSA must actually kinda suck at designing backdoors. But this isn't an ideal argument because people immediately raised concern about the NIST curves too. The only difference is that in the former case, there was already a known algorithm that could be used to pull off the needed attack, and in this case there isn't. Fundamentally there's no reason this debate should even be needed. It's been known for decades how to avoid doubt here, that's the whole reason the NIST curves are the output of SHA1 to begin with. The best time to phase out the NIST curves was decades ago, the second best time is today.
- zakk 3y ago> The NIST elliptic curves that power much of modern cryptography were generated in the late ‘90s by hashing seeds provided by the NSA. I find this deeply troubling. So the seeds were provided by the NSA and they said "don't worry, they were generated hashing a trivial sentence. Unfortunately we forgot it now, but trust us, it's just Jerry joking about getting a raise, nothing more..." I can't believe this didn't undergo further scrutiny earlier, and I can't believe the seeds haven't been chosen in a more sensible way, such as combining random seeds provided by different parties with competing interests, also including hardware RNGs, etc...
- GTP 3y ago> I can't believe the seeds haven't been chosen in a more sensible way, such as combining random seeds provided by different parties with competing interests, also including hardware RNGs, etc... This is because you're looking at it from the perspective of someone living in 2023 with knowledge of what happened between the 90s and now. While that would have been a good way to go, at the time few people would have seen the need for it.
- chinathrow 3y agoWell, with today's internet traffic mostly being encrypted, what would they need their large data centers such as Bluffdale for? https://en.wikipedia.org/wiki/Utah_Data_Center https://en.wikipedia.org/wiki/Utah_Data_Center
- rollulus 3y agoSo 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?
- mike_hearn 3y agoYou 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 elliptic curve related standards, the fact that this mechanism didn't create trust was pointed out immediately, and neither NIST nor the NSA did anything to address the concern. Just like with Dual_EC_DRBG. Triply problematic: the NSA explicitly told people in 2015 not to upgrade past the NIST curves to other curves, because quantum computers will soon be good enough to break ECC entirely and so everyone should switch to post-quantum crypto instead (which is new and still experimental widely used etc). If ECC worked fine, QC was far off and you wanted to keep people on the NIST curves for as long as possible this is exactly what you would say. The cryptography community has not exactly covered itself in glory over this situation. It's been nearly 25 years now. There are newer curves that don't have this problem, why are the NIST curves still being used by anything? Where is the effort to phase them out, like there was with SHA1? This article even seems to be advertising them.
- tptacek 3y agoSHA1 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.
- GTP 3y agoThis is yet another instance where more transparency on the NIST/NSA side would have been beneficial in the long run. If they said from the start, "here are the seeds, we generated them by computing SHA1(insert_solinas_string_here)" the whole debate would have never started in the first place.
- ZigCame 3y ago[dead]
- exabrial 3y agoJust 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.
- koromak 3y agoSeems like you'd need to spend 12K in server cost if you wanted to find this in any reasonable amount of time.