SafeCurves:
choosing safe curves for elliptic-curve cryptography

Rigidity

There are documented instances, and many more suspected instances, of standards being manipulated by attackers. This raises the question of how users of standard curves can be assured that the curves were not generated to be weak.

SafeCurves requires curve shapes for which the ECC security story is as simple as possible, for example by requiring prime fields. This still leaves various security dangers such as incompleteness and transfers, but SafeCurves checks for these dangers in a publicly verifiable way. There is still a potential lack of assurance in the following corner case:

• public ECC cryptanalysis might have missed an attack that applies to a small fraction of curves,
• an attacker might have figured out this attack, and
• the attacker might have manipulated the choices of standard curves to be vulnerable to this secret attack.

SafeCurves requires rigidity to protect ECC users against this possibility. Rigidity is a feature of a curve-generation process, limiting the number of curves that can be generated by the process. The attacker succeeds only if some curve in this limited set is vulnerable to the secret attack. For comparison, without rigidity, the attacker can freely generate curves until finding a curve vulnerable to the secret attack.

SafeCurves classifies existing curve-generation processes into four levels of protection:

• Fully rigid: The curve-generation process is completely explained. Consider, for example, a curve-generation process that takes primes larger than 2^224 for (explained) security reasons, takes the smallest prime larger than 2^224 for (explained) efficiency reasons, takes the curve shape y^2=x^3-3x+b for (explained) efficiency reasons, and takes the smallest positive integer b meeting various (explained) security criteria. This provides the maximum available protection against malicious curve generators: the only possible flexibility for the curve generator is in the choice of security and efficiency criteria, and one expects public research to produce convergence on those criteria.
• Somewhat rigid: The curve-generation process is not completely explained, but the unexplained parts do not give the curve generators many bits of control.
• Manipulatable: The curve-generation process has a large unexplained input, giving the curve generator a large space of curves to choose from. Consider, for example, a curve-generation process that takes y^2=x^3-3x+H(s) meeting various security criteria, where s is a large random "seed" and H is a hash function. No matter how strong H is, a malicious curve generator can search through many choices of s, checking each y^2=x^3-3x+H(s) for vulnerability to a secret attack; this works if the secret attack applies to (e.g.) one curve in a billion.
• Trivially manipulatable: The curve-generation process has a large unexplained input, giving the curve generator a large space of curves to choose from, and there is an efficient method to work backwards from a specified curve in this space to the input. Consider, for example, a curve-generation process that simply produces y^2=x^3-3x+b for a random b. This process is trivially manipulatable: a malicious curve generator can publish any desired b. This works even in the most extreme case, a secret attack that applies to just one curve, provided that the attacker can somehow compute this curve.

The following table reports the protection provided by various existing curves:

Curve	Rigid?	Comments
Anomalous	fully rigid✔	Follows the most concise method in the literature for generating anomalous curves: prime shape 11m(m+1)+3, and curve of j-invariant -2^15. Uses the smallest prime with m above 2^100.
M-221	fully rigid✔	p is largest prime smaller than 2^221; B=1; A > 2 is as small as possible.
E-222	fully rigid✔
NIST P-224	manipulatable	Coefficients generated by hashing the unexplained seed bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5.
Curve1174	fully rigid✔	Prime chosen "very close to, but not above, a power of 2" for efficiency. Prime chosen 3 mod 4 for compatibility with Elligator 1. The only primes 3 mod 4 within 32 of 2^e for e between 200 and 300 are 2^206-5, 2^212-29, 2^226-5, 2^243-9, 2^251-9, 2^285-9; first four rejected for security level, and last rejected for efficiency, producing 2^251-9. Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency. Complete Edwards curve chosen for security. Curve and twist orders chosen as {4*prime,4*prime} for security. d chosen to have the form -(c+1)^2/(c-1)^2 with c=2/s^2 for compatibility with Elligator 1. d=-1174 is smallest qualifying integer in absolute value.
Curve25519	fully rigid✔	Prime chosen "as close as possible to a power of 2" for efficiency reasons ("save time in field operations"). Prime chosen "slightly below 32k bits, for some k" for efficiency reasons ("no serious concerns regarding wasted space"). k=8 chosen for "a comfortable security level". 2^255-19 chosen above 2^255+95, 2^255-31, 2^254+79, 2^253+51, 2^253+39 "because 19 is smaller than 31, 39, 51, 79, 95". Montgomery curve shape y^2=x^3+Ax^2+x chosen for efficiency ("to allow extremely fast x-coordinate point operations"). (A-2)/4 selected as a small integer for efficiency ("to speed up the multiplication by (A-2)/4"). Curve and twist orders required to be {4*prime,8*prime} for security ("protect against various attacks ... here 4, 8 are minimal"). Primes required to be above 2^252 for security ("theoretical possibility of a user's secret key matching the prime"), ruling out A=358990 and A=464586. A=486662 chosen as smallest positive integer meeting these requirements.
BN(2,254)	fully rigid✔	p chosen sparse, close to 2^256, within BN family; using u=−(2^62 + 2^55 + 1). p congruent 3 modulo 4 to have z^2+1 irreducible; b=2 to have twist be y^2=x^3+ (1 − 2i).
brainpoolP256t1	somewhat rigid✔	Several unexplained decisions: Why SHA-1 instead of, e.g., RIPEMD-160 or SHA-256? Why use 160 bits of hash input independently of the curve size? Why pi and e instead of, e.g., sqrt(2) and sqrt(3)? Why handle separate key sizes by more digits of pi and e instead of hash derivation? Why counter mode instead of, e.g., OFB? Why use overlapping counters for A and B (producing the repeated 26DC5C6CE94A4B44F330B5D9)? Why not derive separate seeds for A and B?
ANSSI FRP256v1	trivially manipulatable	No explanation provided.
NIST P-256	manipulatable	Coefficients generated by hashing the unexplained seed c49d3608 86e70493 6a6678e1 139d26b7 819f7e90.
secp256k1	somewhat rigid✔	GLV curve with 256 bits and prime order group; prime and coefficients not fully explained but might be minimal
E-382	fully rigid✔
M-383	fully rigid✔
Curve383187	fully rigid✔	p is largest prime smaller than 2^383; B=1; A > 2 is as small as possible.
brainpoolP384t1	somewhat rigid✔	See brainpoolP256t1.
NIST P-384	manipulatable	Coefficients generated by hashing the unexplained seed a335926a a319a27a 1d00896a 6773a482 7acdac73.
Curve41417	fully rigid✔	Prime chosen above 2^(32*12) for security, but below 2^(32*13) for efficiency. Prime chosen very close to, but not above, a power of 2 for efficiency. Prime 2^414-17 is uniquely closest. Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency. Complete Edwards curve chosen for security. Curve and twist cofactors limited to {4,8} for security. d=3617 is smallest qualifying integer in absolute value.
Ed448-Goldilocks	fully rigid✔	Minimal cofactor 4. -39081 is the first negative d where E and ~E have 4*prime order. Choice of 2^448-2^224-1: "The coefficients are all 32-bit aligned, which helps full-radix implementations with UMAAL or similar. It’s a Solinas trinomial prime, which also reduces the number of carries required. The center tap doesn’t interfere with Karatsuba multiplication."
M-511	fully rigid✔	p = 5 (mod 8) is largest prime smaller than 2^511; B=1; (A - 2)/4 is as small as possible for A > 2; A^2 - 4 is not a square; curve order is n = 8r and quadratic twist order is n' = 4r'.
E-521	fully rigid✔

Isn't it safest to choose cryptographic parameters at random?

Cryptographic keys lose security when they do not have enough randomness. There is a common confusion between public parameters and public keys, creating a common myth that public parameters lose security unless they are as random as possible.

The literature contains many counterexamples to this myth. For example, there are known attacks that significantly reduce the security level of random genus-3 curves, but the attacks do not apply to specially structured genus-3 curves, namely hyperelliptic curves. As another example, in elliptic-curve cryptography one takes only unusual curves whose group orders have very large prime divisors, because uniform random curves are much less secure than these unusual curves. See 2011 Koblitz–Koblitz–Menezes (Section 11) for more subtle examples.

One should not conclude that uniform random parameters are necessarily bad: there are also examples where adding randomness to parameters is good. To see whether randomness is good or bad for the parameters of any particular system, one needs to study the details of attacks against that system.

All curves that meet the SafeCurves criteria are solidly protected against all published attacks. The criteria are computer-verified, with full details presented on this site to support third-party verification. It is conceivable that some of these curves are vulnerable to an attack that is not publicly known, but there is no basis for guessing whether any particular curve will be more or less vulnerable to attack than a random curve.

ECC users can reasonably choose their own random curves to protect against multiple-target rho attacks. However, giving a random curve to each user also has several obvious costs, and for lower costs one can take steps that have larger security benefits. This is why essentially all ECC applications use shared curves.

What do the manipulatable standards say about this?

The possibility of attackers manipulating standard curve choices was raised in the late 1990s, when NSA volunteered to "contribute" elliptic curves to the committee producing ANSI X9.62. NSA did in fact end up producing various elliptic curves later standardized by ANSI X9.62, SEC 2, and NIST FIPS 186-2; these curves were subsequently deployed in many applications.

In response to NSA's contributions, ANSI X9.62 developed "a method for selecting an elliptic curve verifiably at random", and a procedure to "verify that a given elliptic curve was indeed generated at random"; it even claims that this procedure "serves as proof (under the assumption that SHA-1 cannot be inverted) that the parameters were indeed generated at random". However, this procedure does not verify randomness; it verifies only that the curve coefficients were produced as SHA-1 output. The claimed "proof" is nonexistent. The ANSI X9.62 curve-generation method is not trivially manipulatable but it is manipulatable.

IEEE P1363 copied the same curve-generation method and stated that it allows "others to verify that the curve was indeed chosen pseudo-randomly". However, "pseudo-random" is not the same as "random", and does nothing to stop a malicious curve generator from searching through many choices of seeds. NIST correctly characterized the verification procedure for these curves as merely checking "that the coefficient b was obtained from s via the cryptographic hash function SHA-1".

SEC 2 version 1.0 copied the curves that NSA had produced for NIST, and copied the incorrect ANSI X9.62 claim that the curves were "chosen verifiably at random". SEC 2 further claimed that the curves were chosen "by repeatedly selecting a random seed and counting the number of points on the corresponding curve until appropriate parameters were found". This claim might be correct but is certainly not verifiable.

What do other sources say about this?

Shortly after the NIST curves were announced, 1999 Scott pointed out that the curves were not in fact verifiably random:

Now if the idea is to increase our confidence that these curves are therefore completely randomly selected from the vast number of possible elliptic curves and hence likely to be secure, I think this process fails. The underlying assumption is that the vast majority of curves are "good". Consider now the possibility that one in a million of all curves have an exploitable structure that "they" know about, but we don't.. Then "they" simply generate a million random seeds until they find one that generates one of "their" curves. Then they get us to use them. And remember the standard paranoia assumptions apply - "they" have computing power way beyond what we can muster. So maybe that could be 1 billion.

Scott recommended a rigid curve-generation method as an alternative, and concluded his posting as follows: "So, sigh, why didn't they do it that way? Do they want to be distrusted?"

In 2005, Brainpool identified the lack of explanation of the NSA/NIST curve seeds as a "major issue" (p.2). Brainpool required a rigid curve-generation method, as noted above, with seeds "generated in a systematic and comprehensive way" rather than being generated randomly. At one point Brainpool incorrectly described its curves as "random". At several points Brainpool described its requirement as a requirement to be "verifiably pseudo-random", but this understates what Brainpool actually requires and seems likely to cause confusion.

In May 2013, Bernstein–Lange again raised the possibility of NSA having searched through a billion curves. In September 2013, Schneier wrote

Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can. ... I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.

What about rigid choices of subgroups?

For each curve considered by SafeCurves, the order ℓ of the specified subgroup of the group of rational points is prime and larger than sqrt(p)+1. A curve cannot have two different subgroups meeting this requirement.

What about rigid choices of base points?

For each curve considered by SafeCurves, the specified base point is a generator of the specified subgroup. SafeCurves does not place restrictions on the choice of this base point. If there is a "weak" base point W allowing easy computations of discrete logarithms, then ECDLP is weak for every base point: an attacker can compute log_P Q as the ratio of log_W Q and log_W P modulo ℓ. Typical ECC protocols, such as signatures, are designed to be secure for all choices of base point.

There are some protocols where base-point rigidity is important. For example, a "random" ECDLP challenge, computing the discrete logarithm of Q base P, could have a back door for the challenge creator. Certicom's ECDLP challenges use rigid generators P and Q of the subgroup to prevent Certicom from choosing the discrete logarithm in advance.

For some curves the specified base point is chosen rigidly. The usual choice is the generator with smallest possible x-coordinate for short Weierstrass curves or Montgomery curves, or smallest possible y-coordinate for Edwards curves. The reason for x vs. y here is that y(-P)=y(P) for Edwards, allowing y as a ladder coordinate, while x(-P)=x(P) for the others, allowing x as a ladder coordinate.

Brainpool multiplies this smallest point by a mostly rigid hash; Brainpool states that a small point "could possibly" allow side-channel attacks. However, there is no indication that this adds any protection against serious side-channel attacks, such as template attacks. Serious defenses, such as secret sharing, work for any choice of base point.