International Association
for Cryptologic Research

We investigate a new class of fault-injection attacks against the CSIDH family of cryptographic group actions. Our disorientation attacks effectively flip the direction of some isogeny steps. We achieve this by faulting a specific subroutine, connected to the Legendre symbol or Elligator computations performed during the evaluation of the group action. These subroutines are present in almost all known CSIDH implementations. Post-processing a set of faulty samples allows us to infer constraints on the secret key. The details are implementation specific, but we show that in many cases, it is possible to recover the full secret key with only a modest number of successful fault injections and modest computational resources. We provide full details for attacking the original CSIDH proof-of-concept software as well as the CTIDH constant-time implementation. Finally, we present a set of lightweight countermeasures against the attack and discuss their security.

In this paper, we use genus theory to analyze the hardness of the decisional Diffie–Hellman problem for ideal class groups of imaginary quadratic orders acting on sets of elliptic curves through isogenies (DDH–CGA). Such actions are used in the Couveignes–Rostovtsev–Stolbunov protocol and in CSIDH. Concretely, genus theory equips every imaginary quadratic order $$\mathcal {O}$$ O with a set of assigned characters $$\chi : {\text {cl}}(\mathcal {O}) \rightarrow \{ \pm 1\}$$ χ : cl ( O ) → { ± 1 } , and for each such character and every secret ideal class $$[\mathfrak {a}]$$ [ a ] connecting two public elliptic curves E and $$E' = [\mathfrak {a}] \star E$$ E ′ = [ a ] ⋆ E , we show how to compute $$\chi ([\mathfrak {a}])$$ χ ( [ a ] ) given only E and $$E'$$ E ′ , i.e., without knowledge of $$[\mathfrak {a}]$$ [ a ] . In practice, this breaks DDH–CGA as soon as the class number is even, which is true for a density 1 subset of all imaginary quadratic orders. For instance, our attack works very efficiently for all supersingular elliptic curves over $$\mathbb {F}_p$$ F p with $$p \equiv 1 \bmod 4$$ p ≡ 1 mod 4 . Our method relies on computing Tate pairings and walking down isogeny volcanoes. We also show that these ideas carry over, at least partly, to abelian varieties of arbitrary dimension. This is an extended version of the paper that was presented at Crypto 2020.

This paper introduces a new key space for CSIDH and a new algorithm for constant-time evaluation of the CSIDH group action. The key space is not useful with previous algorithms, and the algorithm is not useful with previous key spaces, but combining the new key space with the new algorithm produces speed records for constant-time CSIDH. For example, for CSIDH-512 with a 256-bit key space, the best previous constant-time results used 789000 multiplications and more than 200 million Skylake cycles; this paper uses 438006 multiplications and 125.53 million cycles.

In this paper, we use genus theory to analyze the hardness of the decisional Diffie--Hellman problem (DDH) for ideal class groups of imaginary quadratic orders, acting on sets of elliptic curves through isogenies; such actions are used in the Couveignes--Rostovtsev--Stolbunov protocol and in CSIDH. Concretely, genus theory equips every imaginary quadratic order $\mathcal{O}$ with a set of assigned characters $\chi : \text{cl}(\mathcal{O}) \to \{ \pm 1 \}$, and for each such character and every secret ideal class $[\mathfrak{a}]$ connecting two public elliptic curves $E$ and $E' = [\mathfrak{a}] \star E$, we show how to compute $\chi([\mathfrak{a}])$ given only $E$ and $E'$, i.e., without knowledge of $[\mathfrak{a}]$. In practice, this breaks DDH as soon as the class number is even, which is true for a density $1$ subset of all imaginary quadratic orders. For instance, our attack works very efficiently for all supersingular elliptic curves over $\mathbb{F}_p$ with $p \equiv 1 \bmod 4$. Our method relies on computing Tate pairings and walking down isogeny volcanoes.