# zbMATH — the first resource for mathematics

GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce bias. (English) Zbl 1306.94023
Sarkar, Palash (ed.) et al., Advances in cryptology – ASIACRYPT 2014. 20th international conference on the theory and application of cryptology and information security, Kaoshiung, Taiwan, R.O.C., December 7–11, 2014. Proceedings, Part I. Berlin: Springer (ISBN 978-3-662-45610-1/pbk). Lecture Notes in Computer Science 8873, 262-281 (2014).
Summary: 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]\psi (P)$$, for $$\psi$$ 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 \lambda$$ is close to uniform, or pick a uniform $$k$$ instead and decompose it as $$k_1 + k_2 \lambda$$ 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 = \text{ord}(P)$$, we provide a security proofs under mild assumptions. However, if they are chosen as random integers of $$\lfloor\frac 12 \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 \in [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.
For the entire collection see [Zbl 1301.94003].

##### MSC:
 94A60 Cryptography 14G50 Applications to coding theory and cryptography of arithmetic geometry 94A62 Authentication, digital signatures and secret sharing
Full Text: