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, √n), n = ord(P), we provide a security proofs under mild assumptions. However, if they are chosen as random integers of [1/2 log_2 n] 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 mod 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.