We extend the notion of an invalid-curve attack from elliptic curves to genus 2 hyperelliptic curves. We also show that invalid singular (hyper)elliptic curves can be used in mounting invalid-curve attacks on (hyper)elliptic curve cryptosystems, and make quantitative estimates of the practicality of these attacks. We thereby show that proper key validation is necessary even in cryptosystems based on hyperelliptic curves. As a byproduct, we enumerate the isomorphism classes of genus ( g ) hyperelliptic curves over a finite field by a new counting argument that is simpler than the previous methods.
- Introduction
The purpose of public-key validation is to verify that a public key possesses certain arithmetic properties. Public-key validation is especially important in discrete logarithm protocols where a party ( \hat{B} ) combines his private key with a public key received from a second party ( \hat{A} ) to form a group element ( \sigma ). A dishonest party ( \hat{A} ) might select an invalid public key in such a way that the subsequent use of ( \sigma ) in the protocol leaks information about ( \hat{B} )’s private key. Lim and Lee [18] demonstrated the importance of public-key validation by presenting small-subgroup attacks on some discrete logarithm key agreement protocols that are effective if the receiver of a group element does not verify that the element belongs to the desired group of high order (e.g., a prime-order DSA-type subgroup of ( \mathbb{F}_p^* )). In [3, 1], invalid-curve attacks were designed that are effective on elliptic curve protocols if the receiver of a point does not verify that the point indeed lies on the chosen elliptic curve; see also [20, 22, 21]. Chen, Cheng and Smart [6] illustrated the importance of public-key validation in identity-based key agreement protocols that use bilinear pairings.
The performance of low-genus hyperelliptic curves has been shown to be competitive with that of elliptic curves(^*); see [2] for a summary of recent work. We demonstrate that invalid-curve attacks can be successfully mounted on protocols.
2000 Mathematics Subject Classification: 94A60. Key words and phrases: Invalid-curve attacks, hyperelliptic curves. (^*)Elliptic curves are the genus 1 hyperelliptic curves.
based on genus 2 hyperelliptic curves if the appropriate public-key validation is not performed. We also show that singular curves can be used in mounting invalid-curve attacks against (hyper)elliptic curve protocols. We illustrate our attacks on two recently-proposed discrete logarithm protocols — the Twin Diffie-Hellman key agreement scheme [5] and the XCR signature scheme [14].
In order to analyze invalid-curve attacks on hyperelliptic curve cryptosystems, it is useful to know the number ( N_g(q) ) of isomorphism classes of genus ( g ) hyperelliptic curves over a finite field ( \mathbb{F}_q ). The isomorphism classes of genus ( g ) hyperelliptic curves over an algebraically closed field ( K ) are in 1-1 correspondence with the elements of a ((2g-1))-dimensional irreducible subvariety ( H_g ) of the moduli space ( M_g ) over ( K ) (see [11, p.347]), suggesting that number is of the order of ( q^{2g-1} ). This was confirmed by Nart [23], who gave a closed formula for ( N_g(q) ). We give an elementary counting argument that ( N_g(q) = 2q^{2g-1} + O(q^{2g-2}) ).
The remainder of the paper is organized as follows. After laying some of the mathematical groundwork in §2, we present in §3 our derivation of the number of genus ( g ) hyperelliptic curves over a finite field. In §4, we extend the notion of an invalid curve from elliptic curves to genus 2 curves. We also present the notion of an invalid singular curve, and enumerate the invalid elliptic and genus 2 singular curves. Our invalid-curve attacks are demonstrated and analyzed in §5; we conclude in §6.
- Mathematical preliminaries
Notation. The operator ( [x^i] ) denotes the coefficient extraction operator when ( x ) is an indeterminate. For indeterminate ( x ) and polynomial ( f(x) ) we adopt the convention ( [x^i]f(x) = f_i ). The set of monic polynomials of degree ( d ) over a finite field ( \mathbb{F}q ) is denoted by ( \mathcal{P}^d ); the subset of polynomials with at least one repeated root will be denoted by ( \mathcal{P}d^{\geq 2} ). Let ( \tilde{f} = \tilde{f}{d-1}, \tilde{f}{d-2}, \ldots, \tilde{f}_{d-i} ) be an ordered sequence where each ( \tilde{f}_j \in \mathbb{F}_q ). Then
[ \mathcal{P}d := { x^d + \tilde{f}{d-1}x^{d-1} + \cdots + \tilde{f}{d-i}x^{d-i} + f{d-i-1}x^{d-i-1} + \cdots + f_0 \mid \tilde{f}_{d-i-1}, \ldots, f_0 \in \mathbb{F}_q }. ]
For example, ( \mathcal{P}^2_{2,3} ) denotes the set of polynomials of the form ( x^2 – 3x + f_0 ) where ( f_0 \in \mathbb{F}_q ).
A hyperelliptic curve ( \mathcal{H} ) of genus ( g ) over a finite field ( \mathbb{F}_q ) is defined by a non-singular Weierstrass equation
[ \mathcal{H} : y^2 + H(x)y = F(x), ]
where ( F, H \in \mathbb{F}q[x] ), ( F ) is monic, ( \deg(F) = 2g + 1 ), and ( \deg(H) \leq g ). The Jacobian ( J{\mathcal{H}}(\mathbb{F}_q) ) of ( \mathcal{H} ) over ( \mathbb{F}_q ) is the quotient group of the degree zero divisors defined over ( \mathbb{F}_q ) by the group of principal divisors defined over ( \mathbb{F}q ). The divisor classes ( \bar{D} \in J{\mathcal{H}}(\mathbb{F}_q) ) are in one-to-one correspondence with the pairs of polynomials ((u, v)) with ( u, v \in \mathbb{F}_q[x] ), ( \deg(v) < \deg(u) \leq g ), ( u ) monic, and ( u \mid (v^2 + Hv – F) ); we write ( \bar{D} = [u, v] ).
( J_{\mathcal{H}}(\mathbb{F}q) ) is a finite abelian group with ( |J{\mathcal{H}}(\mathbb{F}_q)| \in [(\sqrt{q} – 1)^{2g}, (\sqrt{q} + 1)^{2g}] ) [25]. Given two divisor classes ( \bar{D}_1 = [v_1, v_1] ) and ( \bar{D}2 = [v_2, v_2] \in J{\mathcal{H}}(\mathbb{F}_q) ), Cantor’s algorithm [4] can be used to find the unique divisor ( \bar{D} = [u, v] ) such that ( \bar{D} = \bar{D}_1 + \bar{D}_2 ).
If ( \text{char}(\mathbb{F}_q) \not\in {2, 2g + 1} ) then the same curve ( \mathcal{H} ) (up to isomorphism) can be given by the equation
[ (1) \quad \mathcal{H} : y^2 = f(x) = x^{2g+1} + \sum_{i=0}^{2g-1} f_i x^i. ]
The non-singularity requirement on the equation of ( \mathcal{H} ) means that ( f ) has no repeated roots, in which case we call ( \mathcal{H} ) a non-singular curve. If ( f ) has ( x_0 ) as a repeated root, we call ( \mathcal{H} ) a singular curve, and ( (x_0, y_0) ), where ( y_0^2 = f(x_0) ), a singular point on ( \mathcal{H} ).
The remainder of this work assumes that a hyperelliptic curve ( \mathcal{H} ) of genus ( g ) over a finite field ( \mathbb{F}_q ) is given via (1). The set of all (non-singular) genus ( g ) hyperelliptic curves over ( \mathbb{F}_q ) will be denoted by ( \mathcal{H}^* ). When a hyperelliptic curve ( \mathcal{H} ) is defined over ( \mathbb{F}q ) we will abbreviate ( J{\mathcal{H}}(\mathbb{F}q) ) to ( J{\mathcal{H}} ).
3. The Number of Hyperelliptic Curves
In this section we estimate the number of non-isomorphic genus ( g ) hyperelliptic curves given by (1). First we need the following formula for the number of monic polynomials with no repeated roots and fixed second leading coefficient.
Theorem 1. Let ( g \geq 1 ) be an integer, ( \mathbb{F}_q ) be a finite field, and ( f_2 \in \mathbb{F}_q ). Then
[ \lvert \mathbb{P}{f_2}^{2g+1} \setminus \tilde{\mathbb{P}}{f_2}^{2g+1} \rvert = q^{2g} – q^{2g-1}. ]
Proof. Let ( \bar{\mathbb{F}}_q ) denote the closure of ( \mathbb{F}_q ). The argument proceeds by induction on ( g ).
For ( g = 1 ), consider ( f(x) = x^3 + f_2 x^2 + f_1 x + f_0 \in \mathbb{P}{f_2}^{3} ). Since ( f ) has degree three, it can have at most one repeated root, say ( \alpha ). If ( \alpha \in \mathbb{F}q \setminus \bar{\mathbb{F}}q ) then the conjugates of ( \alpha ) are also repeated roots of ( f ) contradicting the fact that ( f ) has at most one repeated root. Therefore ( \alpha \in \bar{\mathbb{F}}q ). Factoring ( f ) gives ( f(x) = (x – \alpha)^2 (x – \beta) ), where ( \beta = -f_2 – 2\alpha ). Hence, the only degree of freedom is ( \alpha ) and so ( \lvert \tilde{\mathbb{P}}{f_2}^{3} \rvert = q ). And, since ( \lvert \mathbb{P}{f_2}^{1} \rvert = q^2 ), we have ( \lvert \mathbb{P}{f_2}^{1} \setminus \tilde{\mathbb{P}}{f_2}^{1} \rvert = q^2 – q ).
Assume the result holds for all integers ( 1, 2, \ldots, (g – 1) ), where ( g \geq 2 ). We will show the result holds for ( g ). Let ( f(x) = x^{2g+1} + \sum_{j=0}^{2g} f_j x^j \in \mathbb{P}_{f_2}^{2g+1} ). To each repeated root ( \alpha ) of ( f ) with multiplicity ( k \geq 2 ), we associate ( \lfloor k/2 \rfloor ) pairs ((\alpha, \beta)); we call each such pair a paired repeated root of ( f ) corresponding to ( \alpha ). Note that ( f ) can have at most ( g ) paired repeated roots. Since ( f \in \mathbb{F}_q[x] ), if ( f ) has exactly ( i ) paired repeated roots then it can be written as ( f = a^2 b ), where ( a, b \in \mathbb{F}_q[x] ),
[ a(x) = x^i + a_i x^{i-1} + \cdots + a_0, \ b(x) = x^{2(g-i)+1} + \beta x^{2(g-i)} + b_{2(g-i)-1} x^{2(g-i)-1} + \cdots + b_0, ]
and ( b ) has no repeated roots in ( \bar{\mathbb{F}}_q ). Since the coefficient ( \beta ) in ( b(x) ) satisfies ( \beta + [x^{2i-1}]a(x)^2 = f_2g ), ( \beta ) is determined by ( a ) and ( f_2g ). For a fixed ( i \in [1, g – 1] ) the number of polynomials ( b ) of degree ( 2(g-i)+1 ) that have no repeated roots and have fixed ( \beta ) is ( q^{2(g-i)} – q^{2(g-i)-1} ). Therefore, the number of polynomials ( f ) with exactly ( i ) paired repeated roots is ( q^i \cdot (q^{2(g-i)} – q^{2(g-i)-1}) = q^{2g-i} – q^{2g-i-1} ). For ( i = g ) the polynomial ( f ) factors as ( a^2 (x – \beta) ) and as before ( \beta ) is determined by ( a ) and ( f_2g ). Then the number of polynomials ( f ) with exactly ( g ) paired repeated roots equals the number of choices for ( a ), which is ( q^g ).
Hence, the number of polynomials ( f ) with at least one paired repeated root is
[ \lvert \tilde{\mathbb{P}}{f_2}^{2g+1} \rvert = q^g + \sum{i=1}^{g-1} (q^{2g-i} – q^{2g-i-1}) ]
[ = q^g + q^{2g-1} + \sum_{i=2}^{g-1} q^{2g-i} – \sum_{i=1}^{g-1} q^{2g-i-1} = q^{2g-1}. ]
Finally, since (|P_{f_{2g}}^{2g+1}| = q^{2g}), we have [|P_{f_{2g}}^{2g+1} \setminus \tilde{P}{f{2g}}^{2g+1}| = |P_{f_{2g}}^{2g+1}| – |\tilde{P}{f{2g}}^{2g+1}| = q^{2g} – q^{2g-1},] which completes the argument.
Setting (f_{2g} = 0) in Theorem 1 determines the number of polynomials that define a genus (g) hyperelliptic curve over (\mathbb{F}_q), where (\text{char}(\mathbb{F}_q) \notin {2, 2g + 1}). However, such curves can have more than one representation, and we do not wish to distinguish between isomorphic curves. The following result, due to Lockhart [19], gives a one-to-one correspondence between isomorphism classes of curves and equivalence classes of Weierstrass equations.
Theorem 2. [19, Proposition 1.2] If (H_1) and (H_2) are two genus (g) hyperelliptic curves defined over (\mathbb{F}_q), then (H_1) and (H_2) are isomorphic over (\mathbb{F}_q) if and only if there exists (\alpha \in \mathbb{F}_q^*, \beta \in \mathbb{F}_q,) and (t \in \mathbb{F}_q[x]) with (\deg(t) \leq g), such that the change of coordinates ((x, y) \to (\alpha^2 x + \beta, \alpha^{2g+1} y + t(x))), transforms the equation of (H_1) to the equation of (H_2).
Invalid curve attacks are based on the curve representation (and the explicit group law). Hence we are interested in isomorphisms that preserve the representation of curves. Lockhart’s theorem can be specialized to suit our needs as follows.
Suppose that (\text{char}(\mathbb{F}_q)) is odd and (\text{char}(\mathbb{F}_q) \nmid (2g + 1)). Let (H) be a genus (g) hyperelliptic curve over (\mathbb{F}_q), and let (\tau : (x, y) \to (\alpha^2 x + \beta, \alpha^{2g+1} y + t(x))) be an isomorphism to another genus (g) hyperelliptic curve over (\mathbb{F}_q). We claim that if (\tau) preserves the form of equation (1), it must be the case that (\beta = 0) and (t(x) = 0). Indeed, if (t(x) \neq 0) then applying (\tau) to (H) will result in a linear term in (y), which is not present in (1). Now, applying the transformation ((x, y) \to (\alpha^2 x + \beta, \alpha^{2g+1} y)) to (1), the coefficient of (x^{2g}) is ((2g + 1)\beta \alpha^{4g}) which has to be zero as in (1). Since (\alpha \neq 0) and (\text{char}(\mathbb{F}_q) \nmid (2g + 1)) it must be the case that (\beta = 0). Therefore, the class of transformations that correspond to isomorphisms of a hyperelliptic curve that preserve (1) are of the form ((x, y) \to (\alpha^2 x, \alpha^{2g+1} y)), where (\alpha \in \mathbb{F}_q^*). From now on, when we talk about isomorphisms we will identify them with the element (\alpha).
In Theorem 3 we estimate the number of isomorphism classes of genus (g) hyperelliptic curves over finite fields (\mathbb{F}_q) of odd characteristic not dividing (2g + 1). Note that, by Theorem 1, the number of polynomials (f \in \mathbb{F}_q[x]) that give rise to a genus (g) hyperelliptic curve is (q^{2g} – q^{2g-1}), and since the number of isomorphisms (nonzero field elements) is (q – 1) we expect that the number of non-isomorphic curves to be about (q^{2g-1}). A slightly stronger result is proved in [23, Theorem 3.3] that appeared after our paper was submitted. The proof given here is simpler and is presented for the reader’s convenience.
Theorem 3. Let (g) be fixed. Let (\mathbb{F}_q) be a finite field of odd characteristic (p), and suppose that (p \nmid (2g + 1)) and (q > 4g + 2). Then the number of non-isomorphic genus (g) hyperelliptic curves over (\mathbb{F}_q) is [N_g(q) = 2q^{2g-1} + \mathcal{O}(gq^{2g-2}).]
Proof. Let (f \in \tilde{P}{0}^{2g+1} \setminus P{0}^{2g+1}). Define (z_i(f) = 0) if (f_i = 0), and (z_i(f) = 1) otherwise. We will abbreviate (z_i(f)) to (z_i) in case (f) is clear from context. We call the sequence (z(f) = (z_0, z_1, \ldots, z_{2g-1})) the characteristic sequence of (f). We will use (ab) to denote the sequence (z) where (z_0 = a, z_1 = b), and the remaining entries are given by (\tilde{z}). Let (H_{ab}^z) be the set of polynomials (f) with characteristic sequence (z) such that Let ( |z| ) denote the number of nonzero entries in a sequence ( z ). Then (|H_{10}^z| \leq (q-1)^{|z|}) and (|H_{11}^z| \leq (q-1)^{|z|}).
An isomorphism ( \alpha ) acting on the curve ( y^2 = f(x) ) preserves the characteristic sequence ( z ). Indeed, applying an isomorphism ( \alpha : (x, y) \rightarrow (\alpha^2 x, \alpha^2 + y) ) to (1) results in [ \alpha^{4g+2} y^2 = \alpha^{4g+2} x^{2g+1} + \alpha^{4g-2} f_{2g-1} x^{2g-1} + \cdots + \alpha^2 f_1 x + f_0, ] which can be rewritten as [ y^2 = x^{2g+1} + \alpha^{-4} f_{2g-1} x^{2g-1} + \cdots + \alpha^{-4} f_1 x + \alpha^{-4g+2} f_0. ]
Thus the curves ( y^2 = f(x) ) for ( f \in H_{ab}^z ) have the same automorphism group; we denote this group by ( \text{Aut} H_{ab}^z ). Observe also that if the mapping ( \alpha ) is an automorphism then the order of ( \alpha ) in ( \mathbb{F}q ) must divide ( 4g+2 ). Since ( q > 4g+2 ), ( |\text{Aut} H{ab}^z| ) is no larger than ( 4g+2 ) which yields [ \sum_z |H_{01}^z| (|\text{Aut} H_{11}^z| – 2) \leq 4g \sum_z |H_{01}^z| \leq 4g \sum_z (q-1)^{|z|} = 4g \sum_{|z|=1}^{2g-1} \left( \frac{2g-2}{|z|-1} \right) (q-1)^{i-1} = 4g(q-1) \sum_{i=1}^{2g-1} \frac{2g-2}{i} (q-1)^{i-1} = 4g(q-1)q^{2g-2} = O(q^{2g-1}). ]
Note that in the above equations, the sequence ( z ) has its first two coordinates fixed, and therefore the remaining (|z| – 1) nonzero entries are chosen from ( 2g-2 ) possible indices. Similarly, we have [ \sum_z (|H_{11}^z| + |H_{01}^z| + |H_{10}^z|) = q^{2g} – q^{2g-1}. ]
If both ( z_0 ) and ( z_1 ) are equal to zero, then ( 0 ) is a repeated root of ( f ). So if ( f ) has no repeated roots then at least one of ( z_0 ) or ( z_1 ) is nonzero. By Theorem 1 we have [ \sum_{z \in 0z} (|H_{11}^z| + |H_{01}^z| + |H_{10}^z|) = q^{2g} – q^{2g-1}. ]
An automorphism ( \alpha ) that fixes ( f ) when ( f_1 ) and ( f_0 ) are simultaneously nonzero must satisfy ( \alpha^2 = 1 ). There are two such automorphisms, so ( |\text{Aut} H_{11}^z| = 2 ). Therefore, [ N_g(q) = \sum_{z \in 0z} \frac{|H_{10}^z||\text{Aut} H_{ab}^z|}{q-1} = \sum_{z \in 0z} \frac{|H_{10}^z||\text{Aut} H_{ab}^z|}{q-1} = \sum_{z \in 0z} \frac{|H_{10}^z||\text{Aut} H_{ab}^z|}{q-1} = \sum_{z \in 0z} \frac{|H_{10}^z||\text{Aut} H_{ab}^z|}{q-1}. ]
= \frac{1}{q-1} \left( \sum_{01\tilde{z}} |H_{01}\tilde{z}| | \text{Aut} H_{01}\tilde{z} | + \sum_{10\tilde{z}} |H_{10}\tilde{z}| | \text{Aut} H_{10}\tilde{z} | + 2|H_{11}\tilde{z}| \right)
= \frac{1}{q-1} \left( \sum_{01\tilde{z}} |H_{01}\tilde{z}| | \text{Aut} H_{01}\tilde{z} | + \sum_{10\tilde{z}} |H_{10}\tilde{z}| | \text{Aut} H_{10}\tilde{z} | + 2 \left( q^{2g} – q^{2g-1} – \sum_{01\tilde{z}} |H_{01}\tilde{z}| – \sum_{10\tilde{z}} |H_{10}\tilde{z}| \right) \right)
= \frac{1}{q-1} \left( \sum_{01\tilde{z}} |H_{01}\tilde{z}| \left( | \text{Aut} H_{01}\tilde{z} | – 2 \right) + \sum_{10\tilde{z}} |H_{10}\tilde{z}| \left( | \text{Aut} H_{10}\tilde{z} | – 2 \right) + 2 \left( q^{2g} – q^{2g-1} \right) \right)
= \frac{1}{q-1} \left( O(gq^{2g-1}) + O(gq^{2g-1}) + 2q^{2g} – 2q^{2g-1} \right)
= \frac{1}{q-1} \left( 2q^{2g} + O(gq^{2g-1}) \right)
= 2q^{2g-1} + O(gq^{2g-2}),
as required.
- Invalid and singular curves
We now extend the notion of invalid elliptic curves, proposed by Antipa et al. [1], to genus 2 curves. We emphasize that invalid curves are defined with respect to a specific curve representation and explicit formulae for the group law. That is, given a curve representation and formulae for the group operations that do not make use of a specific coefficient in the selected curve representation, one can define an invalid curve with respect to that representation-formulae pair. If the explicit formulae utilize all the coefficients in the curve representation then invalid curves in this context do not exist. However, for curves of genus 1 and genus 2, which are widely considered for cryptographic applications, the notion of invalid curves is indeed relevant and important.
In genus 1 setting, we use the affine formulae for the group law as described in [2, §13.2.1], and refer to these formulae as $F_{1a}$ throughout the paper. The explicit computations in $F_{1a}$ require only the coefficient $f_1$. In our definition of invalid elliptic curves, we include singular elliptic curves as well.
Definition 1. Let $E$ be an elliptic curve defined over $\mathbb{F}_q$ with equation
$$E : y^2 = x^3 + f_1x + f_0.$$
An invalid curve relative to $E$ and $F_{1a}$ is an elliptic curve over $\mathbb{F}_q$ with equation
$$IE : y^2 = x^3 + f_1x + \tilde{f}_0,$$
where $\tilde{f}_0 \neq f_0$ and $IE$ is not isomorphic to $E$. In addition, if the polynomial $\tilde{f}(x) = x^3 + f_1x + \tilde{f}0$ has a repeated root then $IE$ is called an invalid singular curve relative to $E$ and $F{1a}$.
In genus 2 setting, we will use the affine formulae for the group law as described in [2, §14.3.2], and refer to these formulae as $F_{2a}$ throughout the paper. The formulae $F_{2a}$ depends only on $f_2$ and $f_3$. In our definition of invalid hyperelliptic curves, we include singular hyperelliptic curves as well.
Definition 2. Let $H$ be a genus 2 hyperelliptic curve defined over $\mathbb{F}_q$ with equation
$$H : y^2 = x^5 + f_3x^3 + f_2x^2 + f_1x + f_0. $$
An invalid curve relative to $H$ and $F_{2a}$ is a hyperelliptic curve over $\mathbb{F}_q$ with equation
$$IH : y^2 = x^5 + f_3x^3 + f_2x^2 + \tilde{f}_1x + \tilde{f}_0, $$
where $(f_1, f_0) \neq (f_1, f_0)$ and $IH$ is not isomorphic to $H$. In addition, if the polynomial $f(x) = x^5 + f_3x^3 + f_2x^2 + \tilde{f}_1x + \tilde{f}0$ has a repeated root then $IH$ is called an invalid singular curve relative to $H$ and $F{2a}$.
Invalid singular curves are very interesting in the genus 1 case. If $SE$ is an invalid singular curve over $\mathbb{F}_q$ relative to the elliptic curve $E$ over $\mathbb{F}_q$ and $F_1a$, then $SE$ has exactly one singular point $P = (x_0, y_0)$. Applying the isomorphism $(x, y) \rightarrow (x + x_0, y + y_0)$ to $SE$, we can assume that $SE$ is given by the equation
$$SE : y^2 = x^3 + a_2x^2, \quad a_2 \in \mathbb{F}_q, $$
and $P = (0, 0)$ is the singular point of $SE$. Now, let $y^2 – a_2x^2 = (y – \alpha x)(y – \beta x)$ where $\alpha, \beta \in \mathbb{F}_q$. If $a_2 = 0$ then $\alpha = \beta = 0$, and $P$ is called a cusp singularity of $SE$. If $a_2 \neq 0$ then $\alpha = -\beta$, and $a_2 = a_2′; P$ is called a node singularity of $SE$. In this case, $\alpha, \beta \in \mathbb{F}_q$ if $a_2$ is a quadratic residue in $\mathbb{F}_q$; and $\alpha, \beta \in \mathbb{F}_q \setminus \mathbb{F}q^*$, otherwise. It is well known that the set $SE{ns}(\mathbb{F}_q)$ of non-singular $\mathbb{F}q$-points on $SE$ together with the point at infinity forms a group and in fact the group law $F_1a$ for $E$ is also the group law for $SE$. Moreover, if $P$ is a cusp singularity of $SE$ then $SE{ns}(\mathbb{F}_q)$ is isomorphic to the additive group of $\mathbb{F}_q$. If $P$ is a node singularity of $SE$ and $a \in \mathbb{F}q$ then $SE{ns}(\mathbb{F}_q)$ is isomorphic to the order-$(q + 1)$ multiplicative subgroup of $\mathbb{F}_q^*$. In all cases, the isomorphisms are efficiently computable (see [12, §7.2] for more details). The key point in applying singular invalid-curve attacks is that the group law for non-singular elliptic curves can readily be used for the non-singular part of singular elliptic curves.
The next theorem assumes the setting in Definition 1 and establishes the existence and the number of invalid singular elliptic curves.
Theorem 4. Over $\mathbb{F}_q$, where $\gcd(q, 6) = 1$, the number of invalid singular curves relative to $y^2 = x^3 + f_1x + f_0$ and $F_1a$ is
(i) 1, if $f_1 = 0$;
(ii) 2, if $-\frac{f_1}{f_0} \in \mathbb{F}_q$;
(iii) 0, if $-\frac{f_1}{f_0}$ is a quadratic non-residue in $\mathbb{F}_q$.
Proof. Let $f_1 \in \mathbb{F}_q$ be fixed and consider the set of polynomials
$$P_{0, f_1}^3 = { P_{f_0}^3(x) = x^3 + f_1x + f_0′ : f_0′ \in \mathbb{F}_q }. $$
If $P_{f_0}^3(x)$ has a repeated root in $\bar{\mathbb{F}}_q$ then we must have
$$P_{f_0}^3(x) = x^3 + f_1x + f_0′ = (x + a)^2(x + k_0), \quad a, k_0 \in \mathbb{F}_q.$$
or equivalently,
\begin{align} (2) & \quad k_0 = -2a \ (3) & \quad f_1 = -3a^2 \ (4) & \quad f’_0 = -2a^3. \end{align}
For a fixed ( f_1 ), we consider the solutions ((a, k_0, f’_0)) to (2)–(4).
Case (i). If ( f_1 = 0 ) then ((0, 0, 0)) is the only solution to (2)–(4) and so ( P_{0, f_1}^3 ) has exactly one polynomial that has a repeated root, namely ( P(x) = x^3 ). In this case, the curve defined by ( y^2 = P(x) ) has a cusp singularity at ( S = (0, 0) ).
Case (ii). If ( -f_1/3 = a_1^2 ) for some ( a_1 \in \mathbb{F}q^* ) then ((a_1, -2a_1, -2a_1^3)) and ((-a_1, 2a_1, 2a_1^3)) are the only two solutions to (2)–(4). Hence, ( P{0, f_1}^3 ) has exactly two polynomials with repeated roots: ( P(x) = x^3 + f_1x – 2a_1^3 ) in which case the curve defined by ( y^2 = P(x) ) has a node singularity at ( S = (-a_1, 0) ); and ( P(x) = x^3 + f_1x + 2a_1^3 ) in which case the curve defined by ( y^2 = P(x) ) has a node singularity at ( S = (a_1, 0) ).
Case (iii). If ( -f_1/3 ) is a quadratic non-residue in ( \mathbb{F}q ) then the system defined by (2)–(4) has no solutions and so ( P{0, f_1}^3 ) does not contain any polynomial with repeated roots.
In the attacks described in §5, the adversary will need curves with small-order subgroups. In the genus 1 case the adversary has the ability to choose ( f_0 ), and in [1, §4.4] it was already argued that an adversary can efficiently find suitable invalid curves, essentially by picking curves at random. To extend that argument for genus 2 we need the following result.
Theorem 5. Suppose that ( \gcd(q, 30) = 1 ). The number of invalid singular curves relative to ( y^2 = x^5 + f_3x^3 + f_2x^2 + f_1x + f_0 ) and ( \mathcal{F}_{2a} ) over ( \mathbb{F}_q ) is between ( q – 3 ) and ( q + 3 ).
Proof. Let ( f_2, f_3 \in \mathbb{F}_q ) be fixed, and consider the set of polynomials
[ P_{f_1, f’0}^5(x) = { P{f_1, f’_0}(x) = x^5 + f_3x^3 + f_2x^2 + f_1x + f’_0 : f’_1, f’_0 \in \mathbb{F}_q }. ]
If ( P_{f_1, f’_0}^5(x) ) has repeated roots in ( \bar{\mathbb{F}}_q ), then there are two (not mutually exclusive) possibilities:
Case 1. There exist ( a, b, k_0 \in \mathbb{F}_q ) such that
\begin{align} (5) & \quad P_{f_1, f’_0}^5(x) = x^5 + f_3x^3 + f_2x^2 + f_1’x + f’_0 = (x^2 + ax + b)^2(x + k_0). \end{align}
Comparing the coefficients of the same degree terms, we have
\begin{align} (6) & \quad k_0 = -2a \ (7) & \quad f_3 = 2b – 3a^2 \ (8) & \quad f_2 = -2a^3 + 2ab \ (9) & \quad f’_1 = b^2 – 4a^2b \ (10) & \quad f’_0 = -2b^2a. \end{align}
We obtain from (7) and (8) that ( a ) must satisfy ( 5a^3 + f_3a + f_2 = 0 ). Moreover, since ( f_2 ) and ( f_3 ) are already fixed, any choice of ( a ) fixes ( k_0 ) and ( b ) by (6) and (7). Therefore, the number of polynomials ( P_{f_1, f’_0}^5(x) ) of the form (5) is at most three.
Case 2. There exist (a, k_0, k_1, k_2 \in \mathbb{F}_q) such that
[ P_{f_1′, f_0′}(x) = x^5 + f_3x^3 + f_2x^2 + f_1’x + f_0′ = (x + a)^2(x^3 + k_2x^2 + k_1x + k_0). ]
Comparing the coefficients of the same degree terms, we have
[ \begin{align*} (11) & \quad k_2 = -2a \ (12) & \quad k_1 = f_3 + 3a^2 \ (13) & \quad k_0 = f_2 – 2a(f_3 + 2a^2) \ (14) & \quad f_1′ = 2af_2 – 3a^2f_3 – 5a^4 \ (15) & \quad f_0′ = a^2f_2 – 2a^3f_3 – 4a^5. \end{align*} ]
For a fixed pair ((f_2, f_3) \in \mathbb{F}_q \times \mathbb{F}_q), we first count the number of solutions ((a, k_0, k_1, k_2, f_0′, f_1′)) to (11)–(15). Note that if (a = 0) then we must have (k_0 = f_2, k_1 = f_3, k_2 = f_0 = f_1′ = 0). On the other hand, if (a \neq 0), we have (k_1 \neq f_3) and ((k_1 – f_3)/3) is a quadratic residue in (\mathbb{F}_q) for exactly ((q – 1)/2) elements (k_1 \in \mathbb{F}_q).
For each such (k_1), we obtain two solutions determined by setting (a) equal to the square roots of ((k_1 – f_3)/3). That is, there are 1 + 2(((q – 1)/2)) = (q) solutions in total and each solution ((a, k_0, k_1, k_2, f_0′, f_1′)) leads to a polynomial (P_{f_1′, f_0′}(x)) which has either one or two paired repeated roots in (\mathbb{F}q). We note that different solutions may lead to the same polynomial (P{f_1′, f_0′}(x)). It is easy to see that this occurs only if (P_{f_1′, f_0′}(x)) has exactly two paired repeated roots in (\mathbb{F}q) and in this case we show that, for a fixed (P{f_1′, f_0′}(x)), there could exist at most two different solutions that yield this polynomial. The proof is as follows. Suppose there are three different solutions (S := (a, k_0, k_1, k_2, f_0′, f_1′)) and (\tilde{S} := (\tilde{a}, \tilde{k}_0, \tilde{k}_1, \tilde{k}2, f_0′, f_1′)) that yield the polynomial (P{f_1′, f_0′}(x)). If (a = \tilde{a}) then (S = \tilde{S}) by (11), (12) and (13).
Therefore, we will assume that (a, \tilde{a}) and (\tilde{a}) are pairwise different; and in this case one can see that ((x + a)(x + \tilde{a})^2 | (x^3 + k_2x^2 + k_1x + k_0)), which is impossible.
We are now ready to prove the theorem. Suppose that the number of polynomials (P_{f_1′, f_0′}(x)) that have exactly two paired repeated roots both of which are in (\mathbb{F}q) is (\beta), and the number of polynomials (P{f_1′, f_0′}(x)) that have exactly two paired repeated roots both of which are in (\mathbb{F}_q) (\backslash \mathbb{F}q) is (\gamma). Then, by our above argument, the number of solutions ((a, k_0, k_1, k_2, f_0′, f_1′)) to (11)–(15), such that each solution is leading to a polynomial (P{f_1′, f_0′}(x)) that have exactly two paired repeated roots both of which are in (\mathbb{F}q), is at most (2\beta). Hence, there are at least (q – 2\beta) polynomials (P{f_1′, f_0′}(x)) having exactly one paired repeated root in (\mathbb{F}q), and there are at least ((q – 2\beta) + \beta + \gamma) polynomials (P{f_1′, f_0′}(x)) with at least one repeated root in (\mathbb{F}_q). By Case 1, (\beta + \gamma \leq 3), and we can see that (q – \beta + \gamma \geq q – 3).
From Case 1 and Case 2 there are at most (q + 3) polynomials (P_{f_1′, f_0′}(x)) with at least one repeated root in (\mathbb{F}_q).
Remark 1. Let (H : y^2 = x^5 + f_3x^3 + f_2x^2 + f_1x + f_0) be a genus 2 hyperelliptic curve defined over (\mathbb{F}q). According to Theorem 5, there are at least (\chi = q^2 – q – 3) invalid curves relative to (H) and (\mathbb{F}{q^2}). We now argue that if (f_2 \neq 0) or (f_3 \neq 0) then at least (\chi/2) of these curves are pairwise non-isomorphic. Let (H’) and (H”) be two genus 2 hyperelliptic curves over (\mathbb{F}_q) such that
[ \begin{align*} H’ : & \quad y^2 = x^5 + f_3x^3 + f_2x^2 + f_1’x + f_0′ \ H” : & \quad y^2 = x^5 + f_3x^3 + f_2x^2 + f_1”x + f_0”. \end{align*} ]
The curves $\mathcal{H}’$ and $\mathcal{H}”$ are isomorphic if there is an isomorphism $\alpha$
$$\alpha : (x, y) \rightarrow (\alpha^2 x, \alpha^5 y)$$
that applied to $\mathcal{H}’$ gives the equation of $\mathcal{H}”$. Applying $\alpha$ to $\mathcal{H}’$ gives
$$\alpha \mathcal{H}’ : y^2 = x^5 + \alpha^{-4} f_3 x^3 + \alpha^{-6} f_2 x^2 + \alpha^{-8} f_1 x + \alpha^{-10} f_0′.$$
If $f_2 \neq 0$ or $f_3 \neq 0$ then $\mathcal{H}’$ is isomorphic to $\mathcal{H}”$ only if $\alpha^4 = 1$ or $\alpha^6 = 1$. This proves that at least $\frac{\chi}{3} – 1$ isomorphism classes of invalid curves relative to $\mathcal{H}$ and $\mathcal{F}{2a}$ are pairwise non-isomorphic. Hence, there are at least $\left(\frac{\chi}{3} – 1\right)$ isomorphism classes of invalid curves relative to $\mathcal{H}$ and $\mathcal{F}{2a}$, when $f_2 \neq 0$ or $f_3 \neq 0$. We are justified in omitting the case $f_2 = f_3 = 0$ in our argument since there are at most 10 isomorphism classes of such genus 2 hyperelliptic curves defined over $\mathbb{F}_q$ (see [7]).
- Invalid-curve attacks
Suppose that a discrete logarithm cryptographic protocol requires party $\hat{B}$ to use his static (long-term) private key $b$ by computing $\sigma = bP$ for some incoming $P \in J_\mathcal{H}$, where $\mathcal{H}$ is a genus 1 or genus 2 hyperelliptic curve and $P$ has order $n$. If $\hat{B}$ does not verify that $P \in J_\mathcal{H}$ then an adversary $\mathcal{M}$ could launch an invalid-curve attack to learn $b$ by selecting $P \in J_\mathcal{I}$ where $\mathcal{I}$ is an invalid curve or an invalid singular curve with respect to $\mathcal{H}$ (and either $\mathcal{F}{1a}$ or $\mathcal{F}{2a}$). Invalid-curve attacks come in two flavors.
In a small subgroup attack [18], $\mathcal{M}$ selects $\mathcal{I}$ so that $J_\mathcal{I}$ has an element $P$ of small order $r$. The order $r$ is small enough so that the discrete logarithm problem in $\langle P \rangle$ is feasible via exhaustive search; typically $r$ is a small prime. Small subgroup attacks can be used in situations where $\mathcal{M}$ is able to obtain a quantity that is derived from $bP$, for example $k = H(bP)$ where $H$ is a cryptographic hash function. In this case, $\mathcal{M}$ would compute $k’ = H(iP)$ for all $i \in [0, r – 1]$ until $k’ = k$, after which $\mathcal{M}$ concludes that $b \equiv i \pmod{r}$. By repeating the procedure for different curves $\mathcal{I}$ (and different primes $r$) the value $b$ can be recovered via the Chinese Remainder Theorem.
In a large subgroup attack [20, p.58], $\mathcal{M}$ selects an invalid curve $\mathcal{I}$ so that $J_\mathcal{I}$ has an element $P$ of large order $t \approx n$ and so that the discrete logarithm problem in $\langle P \rangle$ can be efficiently solved; this is the case if $t$ is smooth, or if there exists an efficiently computable mapping from $\langle P \rangle$ to another group where efficient DLP algorithms are known. Large subgroup attacks can be used in situations where $\mathcal{M}$ is able to obtain the group element $bP$ itself. In this case, $\mathcal{M}$ would compute $b \mod t$, and thereafter efficiently determine $b$.
There are two main reasons that invalid-curve attacks can be used by $\mathcal{M}$ in the above setting. First, the representation of elements in the valid group $J_\mathcal{H}$ is the same as the representation of elements in the invalid group $J_\mathcal{I}$. Second, the implementation of the group operation in the valid group $J_\mathcal{H}$ is applicable to the invalid group $J_\mathcal{I}$ without any modification. We illustrate our invalid-curve attacks on two recently-proposed discrete logarithm protocols — the Twin Diffie-Hellman key agreement scheme and the XCR signature scheme — that are successful if public-key validation is not performed. We emphasize that our attacks do not illustrate any weaknesses in these protocols, but rather serve to emphasize the importance of public-key validation. More precisely, the attacks we describe do not require the adversary to tamper with hardware or modify registers; the attacks…