To the best of my current knowledge, it's at most possible that the NSA backdoored the NIST curves. I'm unaware of anyone in academia positively proving the existence thereof.
If your threat model doesn't include the NSA or other intelligence agency level state actors, ECDSA with NIST P-521 will serve you just fine.
(ECDSA is per se a questionable abuse of elliptic curves born from patent issues now long past, but it's not a real, exploitable security problem, either, if implemented correctly.)
As far as I know, there's no concrete evidence that the NSA has compromised the security of the NIST curves. That would be weird for them to do, since they use those curves internally to encrypt data classified at Secret and higher.
I still doubt that there's a backdoor in the NIST curves because they're still widely used and recommended for top secret information, among other reasons.
If there were a backdoor and it leaked (or the math behind it was independently rediscovered!) the result could be catastrophic. Snowden showed that the NSA is absolutely vulnerable to leaks.
Unfortunately, we have no way to validate that the NSA did not grind the "seed" used to generate their parameters to search for curves which were strong or weak against some publicly unknown property which is only found in candidate curves at a one in a billion level.
This is a weakness in the methodology used to pick the parameters, somewhat lovingly mocked by the BADA55 curves: https://bada55.cr.yp.to/vr.html
It's not unreasonable for people to be concerned about this. Injecting intentional weaknesses into cryptosystems used by others was a fundamental objective for the NSA, which drove programs as significant as the CIA literally purchasing the at-the-time world largest manufacturer of encipher machines in order to ensure that it continued ship NSA designed intentionally weakened systems for decades ( https://www.washingtonpost.com/graphics/2020/world/national-... ). That was, of course, somewhat before the establishment of the relevant ECC standards-- but the cloud of operational secrecy prevents us from knowing that much about what NSA has been up to more recently.
The curve used in Bitcoin though isn't a NIST curve, and its generation procedure is about as close as you can get to rigid parameters without having rigid parameters as an explicit design goal.
a=0 (required for the endomorphism), field is 3 mod 4 for fast sqrt, increment field from 2^256-2^32-1024 (fast limb structure) until you find a prime field with a non-trivial cube root of unity (required for endomorphism) and until you can obtain a curve with prime order, set B to the lowest value that does. The result of that procedure is secp256k1. (you can actually drop some of the requirements above and still get the same parameters too, but I am pretty confident that this was their search criteria) -- so no high entropy "random" inputs.
Two pieces of information that add up to a larger story:
* The NSA/CSS Commercial Solutions Center (NCSC) is specifically built around Elliptic Curve Cryptography that they acquired from Certicom.
>The NCSC also manages the Elliptic Curve Cryptography (ECC) program on behalf of the NSA/CSS. Elliptic curve provides greater security and more efficient performance than first generation public key techniques currently in use. NSA/CSS purchased a license that covers intellectual property in a restricted field of use to assist in the implementation of elliptic curves to protect U.S. and allied government information. - https://www.nsa.gov/business/programs/ncsc.shtml
* Certicom designed the Elliptic Curve DRBG (Dual_EC) algorithm including the backdoor (Certicom patented the backdoor functionality in 2005)[0]. The NSA then included this algorithm + backdoor into NIST standard and payed RSA 10 million dollars to make it the default DRBG.
Putting these two facts together suggests that the NCSC was responsible for the Dual_EC backdoor.
What about the theory that the NIST encryption curves may be backdoored ?
If this is the case, if I would be the NSA I would strongly push for free cryptography, to make sure that only the US can decrypt the communications and have a strategic advantage.
NIST EC DSA curves are the only ones used by CAs, are manipulatable, and have no explanation for their origin. Pretty much the entire HTTPS web is likely an open book to the NSA.
Which of the above do you think are "NSA-designed algorithms"?
The real NSA algorithms are part of "Suite A", which you don't have to worry about trusting because they aren't public. (I've chosen not to use things like the NIST curves for ECDSA, though.)
The problem with NIST (and I believe they admitted this is a problem) is that NIST is required by law to use the relevant experts from government agencies[0], which normally is fine, and exactly what you want. However, the agency when it comes to security is NSA, and their in the business of undermining it. Thus the whole ECC backdoor debacle.[1]
NIST seems like a good agency trying to do the right things. It's just that they're forced to work with bad actors.
Speaking of Zero Trust and the NSA, isn't the NSA the agency that published the weak Elliptic Curve Cryptography constant that allowed a backdoor into SSL encryption?
What if the NIST curves were backdoored not by the NSA as a whole, but a rogue individual within the NSA, with the goal of making that backdoor available to a foreign power and/or the highest bidder?
It seems unlikely to me, because the NSA has so many brilliant people working for them, but it also seems like (at least superficially) it would explain just about every element of their reaction to this situation. They're used to being years or decades ahead of everyone else (e.g. differential cryptanalysis), and being caught off-guard would be an uncomfortable position for them.
But if the NSA had backdoored that and you were working for the NSA, that's exactly what you would say. What if the NSA wants to get people off elliptic curves because it's the other stuff that they can crack?
This kind of logic is attractive on message boards but makes little sense in the real world.
What NSA needs are NOBUS ("nobody but us") backdoors. Dual_EC is a NOBUS backdoor because it relies on public key encryption, using a key that presumably only NSA possesses. Any of NSA's adversaries, in Russia or Israel or China or France, would have to fundamentally break ECDLP crypto to exploit the Dual_EC backdoor themselves.
Weak curves are not NOBUS backdoors. The "secret" is a scientific discovery, and every industrialized country has the resources needed to fund new cryptographic discoveries (and, of course, the more widely used a piece of weak cryptography is, the more likely it is that people will discover its weaknesses). This is why Menezes and Koblitz ruled out secret weaknesses in the NIST P-curves, despite the fact that their generation relies on a random number that we have to trust NSA about being truly random: if there was a vulnerability in specific curves NSA could roll the dice to generate, it would be prevalent enough to have been discovered by now.
Clearly, no implementation flaw in Windows could qualify as a NOBUS backdoor; many thousands of people can read the underlying code in Ghidra or IDA and find the bug, once they're motivated to look for it.
No, you can't trust NIST on security. They've certified algorithms they must have known were deliberately weakened in every generation: DES in the 1970s, the Clipper chip in the 80s, "export-grade" RSA in the 90s, and broken RNGs in the 2000s.
The deliberate weakening generally comes from the NSA, but NIST is required to work with them on security standards.
A number of reputable security researchers claim that NIST's misdeeds were all unintentional and they've learned their lesson and there won't be any more backdoors. Perhaps. Ultimately they serve the US administration, so in the long term it depends on whether future administrations actually want everyone to have unbreakable cryptography. Doesn't seem like a safe thing to count on.
I've wondered about this, but I don't trust myself to figure out the answer. Even though I have a background in math and I've done some cryptography related work, I know enough about the crypto space to know that I don't know enough to make my own decisions. The featured article by Filippo Valsorda makes a lot of sense.
On the other hand, if the NSA really could find backdoors into elliptic curves (perhaps with a great deal of work) they would be motivated to gaslight the rest of us about elliptic curves by creating article like TFA.
Yes. It's also hard to know whether "they" didn't try "hard enough" to get "better" curves or whether "they" didn't know any better(†) or whether "they" intentionally made these "bad" curves. That's why I don't want to call it a backdoor.
(†) We know that historically NSA had secret cryptography knowledge, the most famous example being differential cryptanalysis and the subsequent hardening of DES (although IBM also knew about that). Since it's a secret agency we cannot know the current state of their secret knowledge; my gut tells me though that since crypto has become a much more open/scientific discipline in the last 10-15 years that they probably don't have much of that anymore.
For these ciphers, it seems less likely that NSA has a backdoor that no-one else could find.
Notably in the case of dual-EC there was a recommended curve chosen by the NSA. That was easy to backdoor by knowing how the curve was generated.
Maybe, but this argument holds less weight given that they’re the ones pushing for inclusion of these algorithms in the NIST standards, and are really only advocating against the hybrid algorithms.
I honestly think the NSA learned their lesson with the whole debacle around Dual_EC_DRBG and skepticism about their elliptic curve seeds - especially given the continued exponential growth in sensitive electronic communications and records, they want the algorithms as secure as possible without a backdoor that could leak and be a foot-gun for US communications as well.
Instead, they’ll just throw more money at making a usable quantum computer than the next country spends on their entire cryptographic infrastructure, and get targeted backdoors into software/hardware implementations of the encryption algorithms so they can focus their attacks more precisely.
If your threat model doesn't include the NSA or other intelligence agency level state actors, ECDSA with NIST P-521 will serve you just fine.
(ECDSA is per se a questionable abuse of elliptic curves born from patent issues now long past, but it's not a real, exploitable security problem, either, if implemented correctly.)
reply