6 ms·
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 knowle
by tptacek 3y ago
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 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.
- tedunangst 3y agoAh, 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.
- quickthrower2 3y agoYou could however test different schemes like this prior to announcing the scheme.
- Dylan16807 3y agoThere'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.
- smegsicle 3y agoa true conspiracist doesn't believe everything he hears
- djbusby 3y agoThat's not true
- some_furry 3y agoI don't trust what you're saying
- foota 3y agoWhy doesn't he just do a reverse i search? :)
- throw0101a 3y ago> 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 * https://eprint.iacr.org/2015/1018.pdf 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.
- pests 3y agoIts 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
- tptacek 3y agoThey'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.
- nullc 3y agoI 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.
- PeterisP 3y ago> 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.
- some_furry 3y agoYeah but Jerry wouldn't have been incentived to do such a thing, would he?
- tptacek 3y agoAt the point where we find an intelligible English string that generates the NIST P-curve seeds, nobody serious is going to take the seed provenance concerns seriously anymore. I think everybody sort of understands that people who don't work in cryptography are always going to have further layers of theory to add, the same way people waiting for the "Mother of All Short Squeezes" do with Direct Share Registration and share votes and stuff. If the bounty program is successful, that's going to end the NIST curve "debate", such as it is. If you're convinced the P-curves must be backdoored, despite the computer science arguments that suggests they really couldn't have been, then you should comfort yourself in the knowledge that we're probably not going to find the seed strings any time soon; presumably Solinas tried pretty hard himself!
- pclmulqdq 3y agoI 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.
- tptacek 3y agoFor 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.
- quickthrower2 3y agoHe kind of “lost his bitcoin” before bitcoin was invented
- yukkuri 3y agoA conspiracy theorist can always find excuses to wave away evidence incompatible with their beliefs
- api 3y agoI hope it's something like SHA1("Bill Clinton is a poopy head.")
- dmurray 3y agoI'm hoping for something more like "The bodies are buried at 2100 15th St".
- cperciva 3y agoConceivably 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.
- stavros 3y agoAgreed, I wouldn't have thought so a few weeks ago, but after seeing the messages that contain the first few SHA bytes of themselves in themselves, I don't know how implausible it is that they might have generated billions of strings and hashes and then chosen the weaker ones.
- raverbashing 3y agoI'd think it's a bit implausible. Especially with the computing power (and optimizations) available at the time
- Mistletoe 3y agoDid he get that raise?
- acqq 3y agoHowever, I don't find it funny reading all the "gory" details: In the article, under the subtitle "Step back, what is this about?" is: "The NIST elliptic curves (P-192, P-224, P-256, P-384, and P-521[1]) were published by NIST in FIPS 186-2 in 2000, and generated “verifiably at random” according to ANSI X9.62 by taking an arbitrary seed, hashing it with SHA-1, and using the output to derive some of the parameters." Note the sentence: “verifiably at random” according to ANSI X9.62. Now, the mentioned ANSI X9.62 describes very formal algorithms of what “verifiably at random” should mean: "If it is desired that an elliptic curve be generated verifiably at random, then select parameters (SEED, a, b) using the technique specified in Annex A.3.3.1" and then goes on to specify an exact algorithm both how the parameters are selected in A.3.3 and then in A.3.4 the verification algorithm: "The technique specified in this section verifies that the defining parameters of an elliptic curve were indeed selected using the method specified in Annex A.3.3" So, if I understand correctly, the authors spent enough energy both to construct the algorithms to generate the constants and make the SEED public as well as the algorithms to later verify the parameters given the publicly known SEED as an input. And to publish all that in ANSI X9.62. If that was the idea of “verifiably at random” according to ANSI X9.62, and if then nobody knows the SEED, then it appears that the very procedure, for which a lot of energy was spent to be developed or described, was just not followed. From which it can be concluded that the "if" condition of the sentence was just not true: "If it is desired that an elliptic curve be generated verifiably at random..." (Not to mention that the algorithms published there clearly aren't "simply SHA1 hashes" in the sense result = SHA1( seed ) but, casually looking, a concatenation of only some bits of output from multiple SHA1 runs over the increments of the seed, which could suggest that nobody who tries any human written string as a seed would ever find a result by expecting a match of a whole constant with an output of a single SHA1 pass? Has anybody calculated how big would be a chunk of bits from a single SHA1 run actually for every of the constants?) Now, I probably miss something here, if it is so, I'd like to know what.
- meithecatte 3y agoThe standards claim that the existence of such a (SEED, a, b) tuple is enough to show that there is nothing special about the curve in question. But if one in a billion curves have a special property that only you know about, which would make it easier for you to attack the cryptosystem, you can try a variety of different SEED values until you find a desirable curve.