Welcome to the resource topic for 2020/1006
Title:
An Analysis of Fault Attacks on CSIDH
Authors: Jason LeGrow, 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.
ePrint: https://eprint.iacr.org/2020/1006
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .