
Twist security
Background: smallsubgroup attacks
A smallsubgroup 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., AESGCM;
and uses AESGCM 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.
Smallsubgroup attacks for multiplicative groups were introduced in
1997 Lim–Lee.
An implementor can stop a smallsubgroup 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).
Invalidcurve attacks
Much more serious is an invalidcurve 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 invalidcurve 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 invalidcurve 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 nonzero 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.
Invalidcurve attacks against ladders
Fortunately,
invalidcurve attacks are drastically limited by
singlecoordinate 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 nonsquare 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 nonsquare
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 singlecoordinate 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+1t 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 invalidcurve 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 twistsecure curves.
This renders the checks unnecessary, as explained below.
Twistsecure 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
singlecoordinate 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 smallsubgroup attacks as described above
together with invalidcurve 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:

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

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 bruteforce 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 
M221

True✔

2^107.3 
E222

True✔

2^108.8 
NIST P224

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 P256

True✔

2^120.3 
secp256k1

True✔

2^109.5 
E382

True✔

2^188.8 
M383

True✔

2^188.3 
Curve383187

True✔

2^188.3 
brainpoolP384t1

True✔

2^118.5 
NIST P384

True✔

2^191.8 
Curve41417

True✔

2^203.8 
Ed448Goldilocks

True✔

2^221.8 
M511

True✔

2^252.3 
E521

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

M221

842498333348457493583344221469362581248531362447993170180305534793
= 0x7ffffffffffffffffffffffffffd4bee2519e2eba1101ff5f7b3f49
= 2^219  877302629400756399719854182285495

E222

1684996666696914987166688442938727098634905596057513265952429863687
= 0x100000000000000000000000000008f3436a16cd07fd0cebdca67307
= 2^220 + 181532584069648727485883454223111

NIST P224

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 P256

3317349640749355357762425066592395746459685764401801118712075735758936647
= 0x1e0a75640070a738557cc30f68bd56eaea65c94f98411d17ac4e16ece1a47
= 3317349640749355357762425066592395746459685764401801118712075735758936647

secp256k1

1013176677300131846900870239606035638738100997248092069256697437031
= 0x99ee564ea5d84f508913936a761b0d5d792a426a7779817ae2f5b67
= 1013176677300131846900870239606035638738100997248092069256697437031

E382

2462625387274654950767440006258975862817483704404090416747798640973052166872502155164123955177369850754744417740979
= 0x1000000000000000000000000000000000000000000000002a04de0de16a111e83a196d7e4efd2d88c1d81ec02c368b3
= 2^380 + 1030303207694556153926491950732314247062623204330168346803

M383

4925250774549309901534880012517951725634967408808180833493204202978852474404940886836912197553998376631916975561717
= 0x1ffffffffffffffffffffffffffffffffffffffffffffffff270d318a7928b230b9b512109c9b6c372887bb482df1bf5
= 2^381  332472551862747032210439589871084306616078468911523226635

Curve383187

4925250774549309901534880012517951725634967408808180833492824513836280681662413952113716808420015056602872733754209
= 0x1fffffffffffffffffffffffffffffffffffffffffffffffe2f4af5af0bd6eea657ca2f69a91f9f77211beee9febe361
= 2^381  712161694434539774737374313066473440599398497955765034143

brainpoolP384t1

151574876586344350951092838162750565943171857126657289419000711361563821
= 0x15f6398259ac7dda2f7c681d30855f35002d98b8be11ffecc00647db8cad
= 151574876586344350951092838162750565943171857126657289419000711361563821

NIST P384

39402006196394479212279040100143613805079739270465446667949681528863784143880477088695575868365581090168780292281997
= 0x1000000000000000000000000000000000000000000000000389cb27e0bc8d21ea7e5f24bb74f58851313e697333ad68d
= 2^384 + 1388124618062372383266477281309613480665449362152301975181

Curve41417

5288447750321988791615322464262168318627237463714249754277190395559387193645633287411691377616107457765456896611395456028803
= 0x80000000000000000000000000000000000000000000000000014c336dbeb308f9fdd4c90e3fcc7529c30e7e4f18e5a1ef95083
= 2^411 + 33364140863755142520810177694098385178984727200411208589594755

Ed448Goldilocks

181709681073901722637330951972001133588410340171829515070372549795160160121825800627002436557645897001734148521830156375752993149532941
= 0x400000000000000000000000000000000000000000000000000000000335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
= 2^446 + 338093476319795454673879205005611543518120263611892369342742379277

M511

1675975991242824637446753124775730765934920727574049172215445180465220503759171922590715015775614839398225846029626614843464365685435390161686550775636333
= 0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd09402019e7015310a9aa2285d910cbaa7db5f7ab2abde80b567d48a9128a16d
= 2^509  21449509519271495248089063028136243684141513254869666057931081617655350124179

E521

1716199415032652428745475199770348304317358825035826352348615864796385795849414350585403168667069427851954496630506286414241711051155779588293592851887420053
= 0x800000000000000000000000000000000000000000000000000000000000000002ea4939b8b9037a08c94750a1813ac0fb04273ba96570e0babf15dbca0ae7f295
= 2^519 + 337554763258501705789107630418782636071904961214051226618635150085779108655765

Curve 
Cofactor 
Twist cofactor 
Anomalous

1

3^3 * 5 * 47 * 4093 * 2013751 * 2376645121788851

M221

2^3

2^2

E222

2^2

2^2

NIST P224

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 P256

1

3 * 5 * 13 * 179

secp256k1

1

3^2 * 13^2 * 3319 * 22639

E382

2^2

2^2

M383

2^3

2^2

Curve383187

2^3

2^2

brainpoolP384t1

1

7 * 11^2 * 241 * 5557 * 125972502705620325124785968921221517

NIST P384

1

1

Curve41417

2^3

2^3

Ed448Goldilocks

2^2

2^2

M511

2^3

2^2

E521

2^2

2^2

Curve 
Cost for twist rho above 2^100? 
Cost for twist rho 
Anomalous

False

2^53.2 
M221

True✔

2^109.3 
E222

True✔

2^109.8 
NIST P224

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 P256

True✔

2^120.3 
secp256k1

True✔

2^109.5 
E382

True✔

2^189.8 
M383

True✔

2^190.3 
Curve383187

True✔

2^190.3 
brainpoolP384t1

True✔

2^118.1 
NIST P384

True✔

2^191.8 
Curve41417

True✔

2^205.3 
Ed448Goldilocks

True✔

2^222.8 
M511

True✔

2^254.3 
E521

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

M221

True✔

True✔

842498333348457493583344221469362581248531362447993170180305534792 = (l'1)/1

E222

True✔

True✔

842498333348457493583344221469363549317452798028756632976214931843 = (l'1)/2

NIST P224

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 P256

True✔

True✔

1658674820374677678881212533296197873229842882200900559356037867879468323 = (l'1)/2

secp256k1

True✔

True✔

168862779550021974483478373267672606456350166208015344876116239505 = (l'1)/6

E382

True✔

True✔

2462625387274654950767440006258975862817483704404090416747798640973052166872502155164123955177369850754744417740978 = (l'1)/1

M383

True✔

True✔

2462625387274654950767440006258975862817483704404090416746602101489426237202470443418456098776999188315958487780858 = (l'1)/2

Curve383187

True✔

True✔

4925250774549309901534880012517951725634967408808180833492824513836280681662413952113716808420015056602872733754208 = (l'1)/1

brainpoolP384t1

True✔

True✔

151574876586344350951092838162750565943171857126657289419000711361563820 = (l'1)/1

NIST P384

True✔

True✔

39402006196394479212279040100143613805079739270465446667949681528863784143880477088695575868365581090168780292281996 = (l'1)/1

Curve41417

True✔

True✔

5288447750321988791615322464262168318627237463714249754277190395559387193645633287411691377616107457765456896611395456028802 = (l'1)/1

Ed448Goldilocks

True✔

True✔

45427420268475430659332737993000283397102585042957378767593137448790040030456450156750609139411474250433537130457539093938248287383235 = (l'1)/4

M511

True✔

True✔

418993997810706159361688281193932691483730181893512293053861295116305125939792980647678753943903709849556461507406653710866091421358847540421637693909083 = (l'1)/4

E521

True✔

True✔

1716199415032652428745475199770348304317358825035826352348615864796385795849414350585403168667069427851954496630506286414241711051155779588293592851887420052 = (l'1)/1

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