Francisco Rodríguez-Henríquez

Gora Adj, Jesús-Javier Chi-Domínguez, Víctor Mateu et al.

In SIDH and SIKE protocols, public keys are defined over quadratic extensions of prime fields. We present in this work a projective invariant property characterizing affine Montgomery curves defined over prime fields. We then force a secret 3-isogeny chain to repeatedly pass through a curve defined over a prime field in order to exploit the new property and inject zeros in the A-coefficient of an intermediate curve to successfully recover the isogeny chain one step at a time. Our results introduce a new kind of fault attacks applicable to SIDH and SIKE.

Jesús-Javier Chi-Domínguez, Francisco Rodríguez-Henríquez, Benjamin Smith

Let $q = 2^n$, and let $E / \mathbb{F}_{q^{\ell}}$ be a generalized Galbraith--Lin--Scott (GLS) binary curve, with $\ell \ge 2$ and $(\ell, n) = 1$.We show that the GLS endomorphism on $E / \mathbb{F}_{q^{\ell}}$ induces an efficient endomorphism on the Jacobian $J_H(\mathbb{F}_q)$ of the genus-$g$ hyperelliptic curve $H$ corresponding to the image of the GHS Weil-descent attack applied to $E/\mathbb{F}_{q^\ell}$, and that this endomorphism yields a factor-$n$ speedup when using standard index-calculus procedures for solving the Discrete Logarithm Problem (DLP) on $J_H(\mathbb{F}_q)$. Our analysis is backed up by the explicit computation of a discrete logarithm defined on a prime-order subgroup of a GLS elliptic curve over the field $\mathbb{F}_{2^{5\cdot 31}}$. A Magma implementation of our algorithm finds the aforementioned discrete logarithm in about $1,035$ CPU-days.

Daniel Cervantes-Vázquez, Mathilde Chenu, Jesús-Javier Chi-Domínguez et al.

CSIDH is a recent quantum-resistant primitive based on the difficulty of finding isogeny paths between supersingular curves. Recently, two constant-time versions of CSIDH have been proposed: first by Meyer, Campos and Reith, and then by Onuki, Aikawa, Yamazaki and Takagi. While both offer protection against timing attacks and simple power consumption analysis, they are vulnerable to more powerful attacks such as fault injections. In this work, we identify and repair two oversights in these algorithms that compromised their constant-time character. By exploiting Edwards arithmetic and optimal addition chains, we produce the fastest constant-time version of CSIDH to date. We then consider the stronger attack scenario of fault injection, which is relevant for the security of CSIDH static keys in embedded hardware. We propose and evaluate a dummy-free CSIDH algorithm. While these CSIDH variants are slower, their performance is still within a small constant factor of less-protected variants. Finally, we discuss derandomized CSIDH algorithms.