Invalid curve attack: finding low order points

Question

Background

Here's a description of page 182 of "Guide to Elliptic Curve Cryptography" by Hankerson, Menezes and Vanstone. Here's a quote from that page:

The main observation in invalid-curve attacks is that the usual formulae for adding points on an elliptic curve $E$ defined over $\mathbb F_q$ do not involve the coefficient $b$ (see §3.1.2). Thus, if $E'$ is any elliptic curve defined over $\mathbb F_q$ whose reduced Weierstrass equation differs from $E$’s only in the coefficient $b$, then the addition laws for $E'$ and $E$ are the same. Such an elliptic curve $E'$ is called an invalid curve relative to $E$.

Suppose now that $A$ does not perform public key validation on points it receives in the one-pass ECDH protocol. The attacker $B$ selects an invalid curve $E'$ such that $E'(\mathbb F_q)$ contains a point $R$ of small order $l$, and sends $R$ to $A$. $A$ computes $K=dR$ and $k = KDF(R)$. As with the small subgroup attack, when $A$ sends $B$ a message $m$ and its tag $t=MAC_k(m)$, $B$ can determine $d_l = d \bmod l$. By repeating the attack with points $R$ (on perhaps different invalid curves) of relatively prime orders, $B$ can eventually recover $d$.

Question

I am having a problem understanding one aspect of invalid-curve attacks: given some curve $E$, how does one finds an invalid curve $E'$ ($E$ and $E'$ have same parameters except for coefficient $b$) and a small-order point $R$ on $E'(\mathbb F_q)$? Is there an efficient algorithm for finding curves with small order points?

I would appreciate an example showing how to find such a curve $E'$ and a point $R$ for some "popular" $E$ (e.g. one of the NIST curves).

Related questions

Why do public keys need to be validated?

Attacks on schemes based on elliptic curves when the transmitted points are not on the curve

Answer 1

Is there an efficient algorithm for finding curves with small order points?

Yup, just choose a curve at random and you will find one soon enough. Example with P-256 in Pari/GP.

First create the curve and check that its order matches the expected one just to be sure:

(00:31) gp > p = 115792089210356248762697446949407573530086143415290314195533631308867097853951;
(00:31) gp > b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b;
(00:33) gp > E = ellinit([Mod(-3,p),Mod(b,p)]);
(00:38) gp > n = ellsea(E)
115792089210356248762697446949407573529996955224135760342422259061068512044369
(00:39) gp > isprime(n)
1

Create the invalid curve $y^2 = x^3 - 3x + 2019$ and check its group structure:

(00:40) gp > E2 = ellinit([Mod(-3,p),Mod(2019,p)]);
(00:41) gp > ellgroup(E2)
[115792089210356248762697446949407573529765911662708030293191211169245686839810]
(00:41) gp > n2 = ellsea(E2);
(00:42) gp > factor(n2)

[                                                              2 1]

[                                                              3 1]

[                                                              5 1]

[                                                             13 1]

[                                                            941 1]

[                                                           3001 1]

[                                                         644899 1]

[163029786756926124665585146297685125210696471441070761964520581 1]

So the group is cyclic of highly composite order (unlike the real curve, where the goup has prime order). Just get a random point on it, and check its order:

(00:43) gp > P = random(E2);
(00:43) gp > o = ellorder(E2,P)
115792089210356248762697446949407573529765911662708030293191211169245686839810
(00:44) gp > factor(o)

[                                                              2 1]

[                                                              3 1]

[                                                              5 1]

[                                                             13 1]

[                                                            941 1]

[                                                           3001 1]

[                                                         644899 1]

[163029786756926124665585146297685125210696471441070761964520581 1]

I got lucky; my point is a generator so I can easily generate points whose order is any factor of the group order, e.g.:

(00:46) gp > P2 = ellmul(E2,P,o/2);
(00:47) gp > ellorder(E2,P2)
2
(00:47) gp > P3 = ellmul(E2,P,o/3);
(00:47) gp > ellorder(E2,P3)
3
(00:47) gp > P644899 = ellmul(E2,P,o/644899);
(00:48) gp > ellorder(E2,P644899)
644899

But maybe I just got lucky; what if I try another random point? I'll leave it to you as an exercise to try other random points on the curve, as well as other curves.

Answer 2

I would appreciate an example showing how to find such a curve $E'$ and a point $R$ for some "popular" $E$ (e.g. one of the NIST curves).

I won't actually work out the example (it's a bit more work than I feel like doing at the moment), however I will walk you through the steps:

• Pick a random $b'$ value, and so we have the curve $E' : y^2 = x^3 + ax + b'$

• Use a point counting algorithm (Schoof's) to determine the number of points $n'$ on $E'$

• Search for a small factor $q$ of $n'$; if there is no such small factor (or if there is one, but it's not relatively prime to the other small factors you have previously found), then go back and pick another $b'$

• Pick a random point $H$ on $E'$, and compute $R = (n'/q)H$; double check the order of $R$; if it is not q, then pick another $H$

You're done; you now have a point $R$ with a known small factor $q$; you can add that to your collection.