# SafeCurves:choosing safe curves for elliptic-curve cryptography

 Curve parameters: Fields Equations Base points Prime proofs
 ECDLP security: Rho Transfers Discriminants Rigidity
 ECC security: Ladders Twists Completeness Indistinguishability

## 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.

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
= 151574876586344350951092838162750565943171857126657289419000711361563821

NIST P-384

39402006196394479212279040100143613805079739270465446667949681528863784143880477088695575868365581090168780292281997
= 2^384 + 1388124618062372383266477281309613480665449362152301975181

Curve41417

5288447750321988791615322464262168318627237463714249754277190395559387193645633287411691377616107457765456896611395456028803
= 0x80000000000000000000000000000000000000000000000000014c336dbeb308f9fdd4c90e3fcc7529c30e7e4f18e5a1ef95083
= 2^411 + 33364140863755142520810177694098385178984727200411208589594755

Ed448-Goldilocks

181709681073901722637330951972001133588410340171829515070372549795160160121825800627002436557645897001734148521830156375752993149532941
= 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 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

Version: This is version 2013.10.23 of the twist.html web page.