3 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 know
by 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.
- littlestymaar 3y agoI'm not sure you're helping here, given such a description also fits Hamas or drug cartels very well…
- dhx 3y ago> "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)." ElGamal/DSA is fragile and difficult to implement securely in a way that doesn't reveal secret k. ECC (and somewhat particularly NIST curves[1]) is also very difficult to implement securely from side channel attacks[2]. Consideration of "backdoors" should be broader than just mathematical equations on paper. "backdoors" could also include deliberate choice of algorithm or parameters that are fragile and difficult to implement in a secure way to minimise risk of side channel leakage of secrets. This is especially important in a whole variety of applications such as passports, payment cards and TPMs. [1] https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf#page=23 https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf#p... [2] Specifically, implementation of: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic...
- less_less 3y ago> ElGamal/DSA is fragile and difficult to implement securely in a way that doesn't reveal secret k. ECC (and somewhat particularly NIST curves[1]) is also very difficult to implement securely from side channel attacks[2]. IMHO this isn't evidence of a backdoor. Side-channel protection is hard. RSA decryption and especially keygen are also tricky to implement in a side-channel-protected way, and a widespread timing attack on RSA decryption in many libraries was published earlier this year [3]. The NIST p-curves used the state-of-the-art elliptic curve shape for general operations when they were released: short Weierstrass curves over prime fields. Edwards curves are easier to defend against side channels and are overall a better choice (with their own rough edges, mostly involving the cofactor), but those were not known until 2007. Montgomery curves (similar rough edges to Edwards, plus the point at infinity) were known earlier and are nice for key exchange, but they are not as nice for signatures. Overall I would not choose the NIST curves for a new design today, because Edwards/Montgomery curves are a better choice. But I think the evidence they were backdoored (mathematically or otherwise) is weak. [3] https://people.redhat.com/~hkario/marvin https://people.redhat.com/~hkario/marvin
- Ar-Curunir 3y ago
- abecedarius 3y ago> tweaks to DES (which later turned out to be defence against differential cryptanalysis) The NSA's mission has changed, in the sense of its real priorities for securing comms vs. spying on them. They were clearly different at the time of creation of DES vs. at the Snowden leaks, so I wouldn't take that episode as too much evidence of helpful intent in the 90s.