GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-Bit Nonce Bias

The fastest implementations of elliptic curve cryptography in recent years have been achieved on curves endowed with nontrivial efficient endomorphisms, using techniques due to Gallant–Lambert–Vanstone (GLV) and Galbraith–Lin–Scott (GLS). In such implementations, a scalar multiplication [

k

]

P

is computed as a double multiplication [

k

1

]

P

 + [

k

2

]

ψ

(

P

), for

ψ

an efficient endomorphism and

k

1

,

k

2

appropriate half-size scalars. To compute a random scalar multiplication, one can either select the scalars

k

1

,

k

2

at random, hoping that the resulting

k

 = 

k

1

 + 

k

2

λ

is close to uniform, or pick a uniform

k

instead and decompose it as

k

1

 + 

k

2

λ

afterwards. The main goal of this paper is to discuss security issues that may arise using either approach.

When

k

1

and

k

2

are chosen uniformly at random in

$[0,\sqrt{n})$

,

n

 = ord(

P

), we provide a security proofs under mild assumptions. However, if they are chosen as random integers of

$\lfloor\frac12\log_2 n\rfloor$

bits, the resulting

k

is slightly skewed, and hence not suitable for use in schemes like ECDSA. Indeed, for GLS curves, we show that this results in a bias of up to 1 bit on a suitable multiple of

$k\bmod n$

, and that this bias is practically exploitable: while lattice-based attacks cannot exploit a single bit of bias, we demonstrate that an earlier attack strategy by Bleichenbacher makes it possible. In doing so, we set a record by carrying out the

first ECDSA full key recovery using a single bit of bias

.

On the other hand, computing

k

1

and

k

2

by decomposing a uniformly random

k

 ∈ [0,

n

) avoids any statistical bias, but the decomposition algorithm may leak side-channel information. Early proposed algorithms relied on lattice reduction and exhibited a significant amount of timing channel leakage. More recently, constant-time approaches have also been proposed, but we show that they are amenable to power analysis: we describe a template attack that can be combined with classical lattice-based attacks on ECDSA to achieve full key recovery on physiscal devices.