The construction of the NIST curves essentially preludes trapdoors.
It doesn't completely preclude having a purposefully weak curve based on some publicly unknown weakness. ... but at the same time it also doesn't preclude the the curves having been selected to be stronger against some publicly unknown weakness (as was done with DES).
I don't think the backdoor in the NIST curves, if any, is that the curves themselves are not secure, but that they are so hard to implement that it's practically guaranteed that implementations have more-or-less critical issues / side channels.
Good point, forgot how brittle the other curves were. I believe many require unbiased randomness or something?
> I haven't spoken to a cryptographer who believes the NIST curves are backdoored
From what I can infer, I would say this is highly unlikely. That still leaves enough room for things to be interesting, so… nope. I won't touch NIST curves willingly with my current knowledge.
My post specifically pointed out "It doesn't completely preclude having a purposefully weak curve based on some publicly unknown weakness." -- just that there is nowhere to embed a secret key that only the NSA would know. The only room in it would be for narrow vulnerabilities that others could discover-- just because there aren't that many bits of control.
[As an, aside, the NIST curves do not use random primes, E.g. P-256 is 2^256 - 2^224 + 2^192 + 2^96 - 1, which is a solinas prime with a pretty obvious performance driven structure. As is the case for all the other NIST P-whatever curves. Using primes chosen for field performance is pretty common, e.g. curve 25519 uses a crandall prime]
My comment was pointing out that those NIST curves like P-256 and P-224 can't have a trapdoor-- meaning a hidden secret key that allows the NSA and only the NSA to compromise the use-- in the curve themselves.
Some application of the curve could have its own trapdoor, as dualECdrbg did.
"NIST publishes recommendations on which ones to use, but people prefer to use other curves (like secp256k1) that are less likely to have backdoors built into them"
Does this make any sense? How is a curve going to have backdoors on it? Or he means a specific implementation? Or is this a joke? I'm confused
tptacek makes a number of good points but I find it hard to agree with this one:
> there is concern that the NIST curves are backdoored and should be disfavored and replaced with Curve25519 and curves of similar construction.
Of course, "there is concern" is pretty vague, but it should be made clear that such concerns are in the realm of pure speculation at this point. There is simply no known way of constructing a "backdoored" elliptic curve of prime order over a prime field (in particular, the closest thing resembling such a backdoor, namely Teske's key escrow technique based on isogenies from GHS-weak curves, cannot work over a prime field). Scientifically speaking, I don't see more reasons to believe the assertion that "NIST parameters are backdoored because they aren't rigid" than the (equally unfounded) speculation that "Curve25519 may be weak because it has small parameters/a special base field/composite order/etc.".
Moreover, to say that the NSA has backdoored the NIST curve parameters is to assume that they have known, for quite a long time now, a serious weakness affecting a significant fraction of all elliptic curves of prime order over a given base field that has so far escaped the scrutiny of all mathematicians and cryptographers not working for a TLA. Being leaps and bounds ahead of the academic community in an advanced, pure mathematical subject doesn't quite align with what we know about NSA capabilities.
Don't take this the wrong way: there are good reasons to favor Curve25519 and other implementation-friendly elliptic curves (namely, they are faster, and they are fewer ways of shooting yourself in the foot if you implement them), but "NIST curves are backdoored" is not a very serious one.
The issue with the NIST P- curves is that there's no good reason to trust them. And, for what it's worth, being ahead of academia on pure math isn't science fiction; NSA employs a lot of mathematicians. But the notion of a backdoor in the NIST curves is totally speculative.
Despite its very weird submission as a story to HN, what you'd been reading was just a very long HN comment; I wrote it in a single draft and in the style I would use when writing a comment.
the NIST curves are unsafe, regardless of if they are backdoored. In order to use them safely, you have to carefully prepare your private key, because some keys are unsuitable. for curve 25519, you just need a decent secure random, all keys in the keyspace are good.
The reasons for using the NIST curve might have less to do with technical merits or security aspects, and more with regulations and certifications. Certifying something including cryptography already certified (NIST curve) is easier/cheaper than otherwise.
As for backdoors, nobody really knows .. the nature of the algorithm itself makes it practically impossible to even detect a backdoor, even when there is one. So far, no evidence of that though. So if there is a backdoor, then whoever has knowledge of it is damned good in keeping it a secret. In my opinion a bit too good to be likely. That said, NIST has been caught before with their pants down. Rather awkward, since that's the organization supposed to certify such things. One can even wonder what worth or real meaning certifications still have, after they got caught with what they did. I'd personally consider it mostly a national US affair, but the reality is that the rest of the world is still dominated by US standards when it comes to the internet.
All in all, the reasons for using the NIST curve might be more economical and people doing security by marking check boxes, rather than about actual security or efficiency.
Interesting link, and yes it does look like the GOST curves are really suspect. I didn't see a graph for the NIST curves and they do not appear to have called them out.
There's a big difference though with the GOST curves. They were generated in what seems to be a 100% opaque manner, meaning they could have been back-calculated from something.
The NIST curves were generated in a way that was verifiably pseudorandom (generation involved a hash of a constant) but the constant was not explained. This makes it effectively impossible to straight-up back-calculate these curves from something else. NIST/NSA would have had to brute force search for parameters giving rise to breakable curves, which is the basis of the reasoning I've seen by cryptographers I quoted above.
Note that the cryptographers I've seen make this argument aren't arguing that the NIST curves could not be suspect. What they're arguing is that if they are in fact vulnerable and were found by brute force search using 90s computers, all of elliptic curve cryptography may be suspect. If we (hypothetically) knew for a fact they were vulnerable but did not know the vulnerability, we'd know that some troubling percentage of ECC curves are vulnerable to something we don't know and would have no way of checking other curves. We'd also have no way of knowing if other ECC constructions like Edwards curves or Koblitz curves are more or less vulnerable.
So the argument is: either the NIST curves are likely okay, or maybe don't use ECC at all.
Bruce Schneier was for a time a proponent of going back to RSA and classical DH but with large (4096+ bit) keys for this reason. RSA has some implementation gotchas but the math is better understood than ECC. Not sure if he still advocates this.
Personally I think the most likely origin of the NIST constants was /dev/urandom. Remember that these were generated back in the 1990s before things like curve rigidity was a popular topic of discussion in cryptography circles. The goal was to get working curves with some desirable properties and that's about it.
That's sort of, but not really, what Safecurves means. The curves marked "not safe" are mostly not misuse-resistant. It's much easier to end up with security vulnerabilities working with them than with the curves Bernstein and Lange design, which are designed for performance and to be bulletproof in actual use.
(There is an idea in Safecurves of "rigidity", which is roughly the extent to which we can be sure that the curve parameters weren't chosen to somehow advantage their designers; the curves mentioned in this post are not particularly rigid. If you believe the NIST curves are all backdoored, then yes, you can't trust these curves).
No, it's not; the fullness of our glasses is orthogonal to the specific cryptographic issue we're discussing. I would recommend against the NIST P- curves.
One fortunate result of the Snowden disclosures is that for several reasons, some rational and some irrational, the market value of NIST/FIPS certification has plummeted --- it's still an issue if you're selling to the government, but no longer carries security cachet.
As a result, there's minimal upside to adopting cryptographic primitives and constructions simply because they have NIST standards backing them. Which means there's minimal upside to using the NIST curves.
Meanwhile, there are multiple downsides. One of them is the potential for backdoors, but I don't need to reach that issue in my analysis because another is the difficulty of safely implementing curve software with the NIST P-curves.
I wouldn't contest that no crypto engineer "seriously believes NIST P-curves are backdoored", but I know some high profile crypto engineers who seriously think and demonstrate how they might be flawed and could have been backdoored since day one. [1] [2]
It's almost impossible to prove they were backdoored, but considering the sensitivity of the subject, I understand why many consider this unknown a reason to distrust NIST P-curves.
None of "simple", "fast", and "not backdoored" capture the real reason why Curve25519 is so deservedly popular; the real issue is that Curve25519 is misuse-resistant: random strings are, for 25519 ECDH, valid public keys, and the arithmetic rules for the curve he chose permit straightforward constant-time implementations.
I haven't spoken to a cryptographer who believes the NIST curves are backdoored (or, for that matter, in any of the elaborate hocus-pocus around the Brainpool curves being untrustworthy). But the NIST curves are difficult to use safely, which is why nobody likes them.
The NIST backdoor stuff is an argument that appeals more to message board nerds than to practitioners.
(Is NIST itself trustworthy? Fuck no. The Dual_EC CSPRNG seems pretty clearly to have been a backdoor at this point.)
There are all sorts of pitfalls and potential attacks even if the curves are truly random[1]. Some curves also require you to verify whether public keys are valid points on the curve (and their security breaks if you don't do so). So they're harder to implement safely. Others are hard to implement in a way that avoids timing attacks.
This is one of the reasons more paranoid people have generally preferred Curve25519 over the NIST curves -- the NIST curves have very arbitrary base point values which (in theory) could have been backdoored. NIST later published a proof that if you hashed some other arbitrary values, you get the base points -- but then the follow up question is where did the other arbitrary values come from.
There have been attempts in this direction, it's absolutely doable to use a shared seed where many people contribute a random value.
However ultimately a different approach was chosen that solves the same problem: You don't choose an arbitrary curve, instead you define a set of properties that you want your curve to have, based on security, speed and ease of implementation. Then you end up picking the very first curve that fulfils that property.
That's how Curve25519 was created. There's very little wiggle room in there.
Also it should be said that the hypothesies of choosing a "bad" curve that noone can spot are very hypothetical. We know these NIST curves have an unexplained random seed, but noone has an idea how this could've been used for a backdoor.
Daniel J. Bernstein actually regards the 521 curve as the only secure NIST curve, asserting that the 256 and 384 curves have too many suspicious and unexplained terms.
"To be fair I should mention that there's one standard NIST curve using a nice prime, namely 2^521 – 1; but the sheer size of this prime makes it much slower than NIST P-256."
For the sake of historical accuracy, the NIST backdoor argument goes back to 1999 and Michael Scott [1]. I don't really buy it: if the NIST curves can't be trusted purely by association, then I find it very hard to trust the other curves as well.
The NIST and NSA didn't have a hand in deriving Curve 25519, which was created by a very well trusted cryptographer Daniel J. Bernstein. One of the goals of Curve 25519, IIRC, was to use parameters chosen from a handful of mathematical constants as seeds, as opposed to black box constants which could be chosen by an attacker with advanced cryptographic knowledge. (e.g.: the largest employer of mathematicians in the country, the NSA.)
It doesn't completely preclude having a purposefully weak curve based on some publicly unknown weakness. ... but at the same time it also doesn't preclude the the curves having been selected to be stronger against some publicly unknown weakness (as was done with DES).
[Not that I'd recommend them.]
reply