Paper 2020/1006

An Analysis of Fault Attacks on CSIDH

Jason LeGrow and Aaron Hutchinson

Abstract

CSIDH is an isogeny-based post-quantum key establishment protocol proposed in 2018. In this work, we analyze attacking implementations of CSIDH which use dummy isogeny operations using fault injections from a mathematical perspective. We detail an attack by which the private key can be learned by the attacker up to sign with absolute certainty using $\sum \lceil \log_2(b_i) + 1 \rceil$ fault attacks on pairwise distinct group action evaluations under the same private key under ideal conditions using a binary search approach, where $\vec{b}$ is the bound vector defining the keyspace. As a countermeasure to this attack, we propose randomly mixing the real degree $\ell_j$ isogenies together with the dummy ones by means of a binary decision vector. To evaluate the efficacy of this countermeasure, we formulate a probability-based attack on this randomized scheme using a maximum likelihood approach and simulate the attack using 6 bound vectors used in previous CSIDH implementations. We found that the number of attacks required under our model to reach just 1% certainty about the key increased by a factor between 8--12 over the standard approach in the setting of signed private keys and a factor between 28--45 using non-negative private keys, depending on $\vec{b}$. We derive theoretical upper bounds on the number of attacks required to reach a specified certainty threshold about the key under our model. Based on our data and the minimal additional overhead required, we recommend all future implementations of CSIDH to employ a randomized decision vector approach. Finally since our model assumes fault attacks provide no information on the sign of the key, we use a technique based on Gray codes to optimize the standard meet-in-the-middle attack for learning the sign of the key values once their magnitudes have been learned through fault attacks. We estimate that, on average, this optimized technique uses approximately 88% fewer field-multiplication-equivalent operations over the standard approach.