SafeCurves:
choosing safe curves for elliptic-curve cryptography

Twist security

Background: small-subgroup attacks

A small-subgroup attack on DH works as follows. Instead of sending a legitimate curve point eP to Bob, Eve sends Bob a point Q of small order, pretending that Q is her public key. Bob computes nQ as usual, where n is Bob's secret key; computes a hash of nQ as a shared secret key for, e.g., AES-GCM; and uses AES-GCM to encrypt and authenticate data. Because Q has small order, there are not many possibilities for nQ; Eve can simply enumerate the possibilities and check which possibility successfully verifies the data. This attack reveals n modulo the order of Q.

Typical curve choices have order hℓ, where ℓ is the large prime order of the specified base point P and h is a very small cofactor. The only possible orders of curve points Q are then

• ℓ (too many possibilities to enumerate) times divisors of h, and
• divisors of h.

Eve's best strategy (assuming the curve is cyclic, which typical curve choices are) is then to take a curve point Q of order h, so that the attack reveals n mod h. If Bob chose n as a uniform random integer modulo hℓ then after this attack there are still ℓ equally likely possibilities for n. If Bob chose n as hs where s is a uniform random integer modulo ℓ then the attack reveals nothing, and there are still ℓ equally likely possibilities for n. In both cases Eve's best strategy is to continue with the rho method in the group generated by P, of prime order ℓ. There is a slight loss of security if Bob instead chose n as a uniform random integer modulo ℓ; then the attack reduces n to just ℓ/h possibilities, allowing a "kangaroo" computation, roughly sqrt(h) times faster than the rho method.

Small-subgroup attacks for multiplicative groups were introduced in 1997 Lim–Lee.

An implementor can stop a small-subgroup attack by rejecting any Q for which hQ = 0, either by carrying out a short computation or by checking against a precomputed list. But this creates a conflict between simplicity and security. An implementation that does not include this check is simpler and more likely to be produced, and will pass typical functionality tests.

A curve designer can protect against this type of attack by choosing curves with h=1. A protocol designer can protect against this type of attack for any curve by specifying n=hs. Even without any defenses, the impact is limited to sqrt(h).

Invalid-curve attacks

Much more serious is an invalid-curve attack. In this case Eve sends Bob a point Q of small order on another curve. For example, instead of sending Bob a point (x,y) satisfying a standard short Weierstrass equation y^2=x^3+ax+b, Eve sends a point (x,y) satisfying another short Weierstrass equation y^2=x^3+ax+c where c is different from b. The standard formulas for scalar multiplication on short Weierstrass curves do not involve the constant coefficient b, so they automatically also work for y^2=x^3+ax+c. Bob will successfully compute n(x,y) without realizing that anything is amiss.

The advantage of an invalid-curve attack is that Eve has many more points Q to choose from. Eve can run the attack using a point Q_2 of order 2 on one curve, a point Q_3 of order 3 on another curve, a point Q_5 of order 5 on another curve, etc., revealing n mod 2, n mod 3, n mod 5, etc. Soon Eve has enough information to interpolate Bob's entire public key n using an explicit form of the Chinese remainder theorem. This attack was introduced in 2000 Biehl–Meyer–Müller.

An ECC implementor can stop an invalid-curve attack by checking whether the input point Q satisfies the correct curve equation; this does not take much time, and it guarantees that Q is on the original curve. But this creates a conflict between simplicity and security. An implementation that does not include this check is simpler and more likely to be produced, and will pass typical functionality tests.

A curve designer cannot protect against this attack by choosing better curves. For example, for fixed non-zero a the short Weierstrass curves y^2=x^3+ax+b cover roughly 25% or roughly 50% of all isomorphism classes of elliptic curves, depending on p. These curves have roughly 4 sqrt(p) different orders, and a huge number of points Q of small order. An implementation that receives uncompressed field elements x and y from another party therefore must check whether (x,y) is on the curve.

A protocol designer can help protect against this attack by specifying point compression. An implementation that receives a compressed point, such as x and just one bit of y, will naturally detect invalid inputs when it reconstructs the missing coordinate. However, point compression costs some time and, more importantly, some implementation effort, again creating a conflict between simplicity and security.

Invalid-curve attacks against ladders

Fortunately, invalid-curve attacks are drastically limited by single-coordinate ladders such as the Montgomery ladder and the Brier–Joye ladder. For example, any input x that is not on a Montgomery curve By^2=x^3+Ax^2+x is guaranteed to be on the "twisted" curve (B/u)y^2=x^3+Ax^2+x, where u is a non-square in F_p. Specifically, if (x^3+Ax^2+x)/B is a nonzero square then x represents two points (x,+-sqrt((x^3+Ax^2+x)/B)) on the original curve; if (x^3+Ax^2+x)/B is a non-square then x represents two points (x,+-sqrt((x^3+Ax^2+x)u/B)) on the twisted curve; if (x^3+Ax^2+x)/B is zero then x represents one point (x,0) on each curve. The Montgomery ladder formulas for By^2=x^3+Ax^2+x also compute scalar multiplication for the twisted curve (B/u)y^2=x^3+Ax^2+x, so the attacker can use points of small order on either of these curves, but the single input coordinate does not provide any other attack options.

The general picture is that single-coordinate ladders work for curves isomorphic to the original curve and for one other isomorphism class of curves, namely all the nontrivial quadratic twists of the original curve. If the original curve has p+1-t points then any nontrivial quadratic twist has p+1+t points. Often a nontrivial quadratic twist is called "the twist".

An ECC implementor can stop an invalid-curve attack against ladders by checking whether the input coordinate x belongs to a point Q on the correct curve equation; this requires determining whether x^3+Ax^2+x is a square. This computation is doable but noticeable in the overall computation of nQ; also this creates a conflict between simplicity and security. An implementation that does not include this check is simpler and more likely to be produced, and will pass typical functionality tests.

A curve designer can protect against this attack by choosing better curves, namely twist-secure curves. This renders the checks unnecessary, as explained below. Twist-secure curves for DH were proposed in a 2001 Bernstein talk and a 2001 Bernstein posting; see also 2006 Bernstein and 2008 Fouque–Lercier–Réal–Valette.

Security against twist attacks

SafeCurves requires single-coordinate ladder DH to remain secure even if

• Bob chooses n only up to ℓ;
• Bob does not multiply n by the cofactor h for the original curve;
• Bob does not multiply n by the cofactor h' for the twist; and
• Bob does not bother to check whether incoming points are on the original curve.

Specifically, SafeCurves quantitatively evaluates combined attacks that use small-subgroup attacks as described above together with invalid-curve attacks using the twist. SafeCurves requires the resulting security level to be at least 2^100. If both cofactors are very small then the security level here is close to the standard rho security level.

Here are two examples showing how to optimize combined attacks:

1. Assume that the original curve has order hℓ and that the twist has order h'ℓ' where ℓ and ℓ' are primes around 2^200, h and h' are around 2^50, and h and h' are coprime. Assume that Bob chooses n as a number less than ℓ. The attacker computes n modulo h in at most 2^50 operations (trying all h possible values of nQ against some AES-GCM encrypted text); computes n modulo h' in at most 2^50 operations; obtains n modulo hh' using CRT; and does a kangaroo attack against the ℓ/(hh') possibilities of n in time 2^50, for a total of 2^51.6 operations.
2. Assume instead that ℓ' is around 2^94; that ℓ is around 2^200; that h' is a product of primes q, r, and s around 2^8, 2^18, and 2^90; that h is around 2^10; and again that h and h' are coprime. Assume again that Bob chooses n as a number less than ℓ. In this situation the best attack is as follows: compute n modulo h in about 2^10 operations; compute n modulo q and r in about 2^18 operations; obtain n modulo hqr using CRT; apply a kangaroo attack to the remaining ℓ/(hqr) possibilities for n. Here hqr is around 2^36, so the kangaroo attack takes only about 2^82 operations. Note that the attacker did not use a point of order s here, since searching all the multiples of the point would have taken 2^90 operations; the combined attack balances the cost of the brute-force searches with the cost of a kangaroo attack on the remaining DLP in the main subgroup. Note also that a standard ECDLP problem for the group of order ℓ' would have been much easier to solve, using only 2^47 operations, but would have required Bob to expose a twisted curve point nQ to the attacker, rather than using a hash of nQ to encrypt data.

The following table evaluates the security of various curves against combined attacks. Relevant numerical data (such as ℓ') and further requirements appear later in this page.

Curve	Cost for combined attack above 2^100?	Cost for combined attack
Anomalous	False	2^53.5
M-221	True✔	2^107.3
E-222	True✔	2^108.8
NIST P-224	False	2^58.4
Curve1174	True✔	2^123.3
Curve25519	True✔	2^124.3
BN(2,254)	False	2^93.2
brainpoolP256t1	False	2^44.5
ANSSI FRP256v1	False	2^79.4
NIST P-256	True✔	2^120.3
secp256k1	True✔	2^109.5
E-382	True✔	2^188.8
M-383	True✔	2^188.3
Curve383187	True✔	2^188.3
brainpoolP384t1	True✔	2^118.5
NIST P-384	True✔	2^191.8
Curve41417	True✔	2^203.8
Ed448-Goldilocks	True✔	2^221.8
M-511	True✔	2^252.3
E-521	True✔	2^258.3

ECDLP security for the twist

SafeCurves also imposes all of its ECDLP security requirements upon the twist, specifically upon a subgroup of order ℓ', where ℓ' is the largest prime factor of p+1+t:

• ℓ' is required to be large enough to provide at least 2^100 security against rho. The rho security of this group is labeled twist rho in the tables below.
• ℓ' is required to be different from p; i.e., the number of points on the original curve must not be p+2. This requirement avoids additive transfers for the twist.
• The embedding degree for ℓ' is at least (ℓ'-1)/100. This requirement avoids multiplicative transfers.
• The CM field discriminant is larger than 2^100. The field discriminant for the twist is the same as the field discriminant for the original curve, so the twist does not need to be checked separately.

Some of the ECDLP security requirements for the twist are overkill for DH on the original curve: DH does not actually reveal nQ to Eve, so there is no obvious way for Eve to apply (e.g.) an additive transfer. There are, however, other ECC protocols that make full use of both the original curve and its twist, and twist security is important for these protocols. See, e.g., 1986 Kaliski, 1988 Kaliski, and 2001 Boyd–Montague–Nguyen.

The following tables evaluate the ECDLP security of the twists of various curves.

Curve	ℓ'
Anomalous	142215960774543971001476431146737 = 0x703048d8c5db158c233fbeaeef1 = 142215960774543971001476431146737
M-221	842498333348457493583344221469362581248531362447993170180305534793 = 0x7ffffffffffffffffffffffffffd4bee2519e2eba1101ff5f7b3f49 = 2^219 - 877302629400756399719854182285495
E-222	1684996666696914987166688442938727098634905596057513265952429863687 = 0x100000000000000000000000000008f3436a16cd07fd0cebdca67307 = 2^220 + 181532584069648727485883454223111
NIST P-224	177594041488131583478651368420021457 = 0x22340ff0f7eba57b33ac73e28a14d1 = 177594041488131583478651368420021457
Curve1174	904625697166532776746648320380374280115004475121138339093035488349999675019 = 0x200000000000000000000000000000008869a3b202cf8cb76bb2ba02e99368b = 2^249 + 11332719920821432534773113288178349707
Curve25519	14474011154664524427946373126085988481603263447650325797860494125407373907997 = 0x1fffffffffffffffffffffffffffffffd6420c42ba10c6534fdb39cb4614581d = 2^253 - 55484635554744707071703875581767296995
BN(2,254)	49603261419390422248082736481 = 0xa046db2da9d98120e62d8561 = 49603261419390422248082736481
brainpoolP256t1	401601867518226318515439169 = 0x14c3280dca3d4480aab0641 = 401601867518226318515439169
ANSSI FRP256v1	837116414630376960702915782614178937699338555837 = 0x92a19928f2506abd9379499cf6ce820fdf9811bd = 837116414630376960702915782614178937699338555837
NIST P-256	3317349640749355357762425066592395746459685764401801118712075735758936647 = 0x1e0a75640070a738557cc30f68bd56eaea65c94f98411d17ac4e16ece1a47 = 3317349640749355357762425066592395746459685764401801118712075735758936647
secp256k1	1013176677300131846900870239606035638738100997248092069256697437031 = 0x99ee564ea5d84f508913936a761b0d5d792a426a7779817ae2f5b67 = 1013176677300131846900870239606035638738100997248092069256697437031
E-382	2462625387274654950767440006258975862817483704404090416747798640973052166872502155164123955177369850754744417740979 = 0x1000000000000000000000000000000000000000000000002a04de0de16a111e83a196d7e4efd2d88c1d81ec02c368b3 = 2^380 + 1030303207694556153926491950732314247062623204330168346803
M-383	4925250774549309901534880012517951725634967408808180833493204202978852474404940886836912197553998376631916975561717 = 0x1ffffffffffffffffffffffffffffffffffffffffffffffff270d318a7928b230b9b512109c9b6c372887bb482df1bf5 = 2^381 - 332472551862747032210439589871084306616078468911523226635
Curve383187	4925250774549309901534880012517951725634967408808180833492824513836280681662413952113716808420015056602872733754209 = 0x1fffffffffffffffffffffffffffffffffffffffffffffffe2f4af5af0bd6eea657ca2f69a91f9f77211beee9febe361 = 2^381 - 712161694434539774737374313066473440599398497955765034143
brainpoolP384t1	151574876586344350951092838162750565943171857126657289419000711361563821 = 0x15f6398259ac7dda2f7c681d30855f35002d98b8be11ffecc00647db8cad = 151574876586344350951092838162750565943171857126657289419000711361563821
NIST P-384	39402006196394479212279040100143613805079739270465446667949681528863784143880477088695575868365581090168780292281997 = 0x1000000000000000000000000000000000000000000000000389cb27e0bc8d21ea7e5f24bb74f58851313e697333ad68d = 2^384 + 1388124618062372383266477281309613480665449362152301975181
Curve41417	5288447750321988791615322464262168318627237463714249754277190395559387193645633287411691377616107457765456896611395456028803 = 0x80000000000000000000000000000000000000000000000000014c336dbeb308f9fdd4c90e3fcc7529c30e7e4f18e5a1ef95083 = 2^411 + 33364140863755142520810177694098385178984727200411208589594755
Ed448-Goldilocks	181709681073901722637330951972001133588410340171829515070372549795160160121825800627002436557645897001734148521830156375752993149532941 = 0x400000000000000000000000000000000000000000000000000000000335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d = 2^446 + 338093476319795454673879205005611543518120263611892369342742379277
M-511	1675975991242824637446753124775730765934920727574049172215445180465220503759171922590715015775614839398225846029626614843464365685435390161686550775636333 = 0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd09402019e7015310a9aa2285d910cbaa7db5f7ab2abde80b567d48a9128a16d = 2^509 - 21449509519271495248089063028136243684141513254869666057931081617655350124179
E-521	1716199415032652428745475199770348304317358825035826352348615864796385795849414350585403168667069427851954496630506286414241711051155779588293592851887420053 = 0x800000000000000000000000000000000000000000000000000000000000000002ea4939b8b9037a08c94750a1813ac0fb04273ba96570e0babf15dbca0ae7f295 = 2^519 + 337554763258501705789107630418782636071904961214051226618635150085779108655765

Curve	Cofactor	Twist cofactor
Anomalous	1	3^3 * 5 * 47 * 4093 * 2013751 * 2376645121788851
M-221	2^3	2^2
E-222	2^2	2^2
NIST P-224	1	3^2 * 11 * 47 * 3015283 * 40375823 * 267983539294927
Curve1174	2^2	2^2
Curve25519	2^3	2^2
BN(2,254)	1	3^3 * 3583 * 298908837206431 * 11711184643015782903697616449
brainpoolP256t1	1	5^2 * 175939 * 492167257 * 8062915307 * 2590895598527 * 4233394996199
ANSSI FRP256v1	1	7 * 439 * 11760675247 * 3617872258517821
NIST P-256	1	3 * 5 * 13 * 179
secp256k1	1	3^2 * 13^2 * 3319 * 22639
E-382	2^2	2^2
M-383	2^3	2^2
Curve383187	2^3	2^2
brainpoolP384t1	1	7 * 11^2 * 241 * 5557 * 125972502705620325124785968921221517
NIST P-384	1	1
Curve41417	2^3	2^3
Ed448-Goldilocks	2^2	2^2
M-511	2^3	2^2
E-521	2^2	2^2

Curve	Cost for twist rho above 2^100?	Cost for twist rho
Anomalous	False	2^53.2
M-221	True✔	2^109.3
E-222	True✔	2^109.8
NIST P-224	False	2^58.4
Curve1174	True✔	2^124.3
Curve25519	True✔	2^126.3
BN(2,254)	False	2^47.5
brainpoolP256t1	False	2^44.0
ANSSI FRP256v1	False	2^79.4
NIST P-256	True✔	2^120.3
secp256k1	True✔	2^109.5
E-382	True✔	2^189.8
M-383	True✔	2^190.3
Curve383187	True✔	2^190.3
brainpoolP384t1	True✔	2^118.1
NIST P-384	True✔	2^191.8
Curve41417	True✔	2^205.3
Ed448-Goldilocks	True✔	2^222.8
M-511	True✔	2^254.3
E-521	True✔	2^259.3

Curve	Twist safe against additive transfer?	Twist safe against multiplicative transfer?	Twist embedding degree
Anomalous	True✔	True✔	5079141456233713250052729683812 = (l'-1)/28
M-221	True✔	True✔	842498333348457493583344221469362581248531362447993170180305534792 = (l'-1)/1
E-222	True✔	True✔	842498333348457493583344221469363549317452798028756632976214931843 = (l'-1)/2
NIST P-224	True✔	True✔	177594041488131583478651368420021456 = (l'-1)/1
Curve1174	True✔	True✔	452312848583266388373324160190187140057502237560569169546517744174999837509 = (l'-1)/2
Curve25519	True✔	True✔	14474011154664524427946373126085988481603263447650325797860494125407373907996 = (l'-1)/1
BN(2,254)	True✔	True✔	9920652283878084449616547296 = (l'-1)/5
brainpoolP256t1	True✔	True✔	25100116719889144907214948 = (l'-1)/16
ANSSI FRP256v1	True✔	True✔	209279103657594240175728945653544734424834638959 = (l'-1)/4
NIST P-256	True✔	True✔	1658674820374677678881212533296197873229842882200900559356037867879468323 = (l'-1)/2
secp256k1	True✔	True✔	168862779550021974483478373267672606456350166208015344876116239505 = (l'-1)/6
E-382	True✔	True✔	2462625387274654950767440006258975862817483704404090416747798640973052166872502155164123955177369850754744417740978 = (l'-1)/1
M-383	True✔	True✔	2462625387274654950767440006258975862817483704404090416746602101489426237202470443418456098776999188315958487780858 = (l'-1)/2
Curve383187	True✔	True✔	4925250774549309901534880012517951725634967408808180833492824513836280681662413952113716808420015056602872733754208 = (l'-1)/1
brainpoolP384t1	True✔	True✔	151574876586344350951092838162750565943171857126657289419000711361563820 = (l'-1)/1
NIST P-384	True✔	True✔	39402006196394479212279040100143613805079739270465446667949681528863784143880477088695575868365581090168780292281996 = (l'-1)/1
Curve41417	True✔	True✔	5288447750321988791615322464262168318627237463714249754277190395559387193645633287411691377616107457765456896611395456028802 = (l'-1)/1
Ed448-Goldilocks	True✔	True✔	45427420268475430659332737993000283397102585042957378767593137448790040030456450156750609139411474250433537130457539093938248287383235 = (l'-1)/4
M-511	True✔	True✔	418993997810706159361688281193932691483730181893512293053861295116305125939792980647678753943903709849556461507406653710866091421358847540421637693909083 = (l'-1)/4
E-521	True✔	True✔	1716199415032652428745475199770348304317358825035826352348615864796385795849414350585403168667069427851954496630506286414241711051155779588293592851887420052 = (l'-1)/1