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.
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.
From a mathematical perspective, all of the mainstream curves, from the NIST p- curves to the Brainpool curves, are solid.
There are four reasons people use Curve25519: it's faster in software than most implementations of the other curves, it was designed to be mostly misuse-resistant, so you don't have to be as careful checking parameters (a very common vector for ECC curve attacks), it's designed to be simple to make leak-proof implementations (unlike the NIST curves, which are hard to do in constant time), and it has the Dan Bernstein brand.
But if we're talking about index calculus attacks, the NIST curves do fine there too.
There's two stories that often get mixed together. One is an elliptic curve based random number generator (Dual EC DRBG), and yes, everyone who knows the facts believes it's backdoored.
Then there's some much more general concerns about the NIST curves themselve. These concerns come down to that a) we don't really know how they were generated (there are some numbers in the paper that just "appear out of nowhere") and b) that they've been created by the NSA. But there's no concrete proof of any backdooring and it seems relatively implausible, as no method is known that would explain how that backdooring would work. I guess most people familiar with the facts don't believe they are backdoored.
"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
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.
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.
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.
ECDSA is fantastic for all the reasons touched on in this article, but I’m sure the use of NIST curves will draw some criticism. As far as I know, no cryptographer seriously believes the curves to be backdoored, but nonetheless seems to be a hot topic of online discussion. DJB lists them as “unsafe”. Of course, other curve parameters like 25519 don’t have the same widespread deployment that the NIST curves enjoy, so this is a very sensible choice.
A backdoor in Curve25519 hasn’t really been a concern, because unlike P-256, the parameters for the curve didn’t come from NIST. Curve25519 is a djb (https://en.wikipedia.org/wiki/Daniel_J._Bernstein) special.
So unless djb was secretly working with the NSA and willing to risk his reputation to backdoor a highly scrutinized elliptic curve, the risk is low.
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."
I don't think the NIST curves are backdoored, but they obviously have some serious theoretical and practical issues. [1]
As far as I know, neither of these issues is relevant to their usage with ECDSA (although invalid curve attacks should be a good enough reason to avoid using these curves with ECDH completely), but experience with SHA-1 and RC4 has thought us that algorithms with theoretical problems are likely to be practically broken sooner or later.
But NIST curves are not even the main issue with the ES* algorithms in JWT. The real issue is ECDSA:
1. Verification is slow. P-256 is about 2-4 times slower than Ed25519 [2]. This kind of speed hit may often be unacceptable.
2. Nonce reuse is an issue. The PS3 implementation was extremely bad, but random number generators can often be broken. This is not a theoretical issue - it used to happen verify often with docker containers until recently. There are alternative schemes that allow using ECDSA with a deterministic synthetic nonce [3], but this is not supported by any JWT implementation I know of. Ed25519, on the other hand, uses a synthetic nonce.
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.
That's the reason Curve22519 (defined by djb, completely independent of any NIST involvement) has become popular and is being widely used as default in major ECDH implementations (https://en.wikipedia.org/wiki/Curve25519 ). As close to a "standard" as you'd find today that nobody believes to have known weaknesses or backdoors.
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.
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]
Confused.. Safecurves exists because all the standard curves appear to be backdoored. Curve25519 is not a standard curve. How is this FUD?
Curve25519 was first released by Daniel J. Bernstein in 2005,[7] but interest increased considerably after 2013 when it was discovered that the NSA had implemented a backdoor into Dual EC DRBG. While not directly related,[8] suspicious aspects of the NIST's P curve constants[9] led to concerns[10] that the NSA had chosen values that gave them an advantage in factoring[11] public keys.[12]
We keep having this come up with some of the EC curves like NIST P-256 for example. There's no evidence that it is actually backdoored, but the consensus seems to be that the construction is suspicious, unlike the construction for SHA-2.
What do we do with it? Not many in a product development team that is interacting with other companies or organizations can meaningfully defend not using a NIST curve because it looks suspicious.
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.)
reply