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].

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 |