Fifteenth Algorithmic Number Theory Symposium, ANTS-XV,
University of Bristol
August 8 - 12, 2022
Accepted posters ANTS XV
- Cathal O'Sullivan, Jonathan P. Sorenson and Aryn Stahl. An Algorithm to Find Sums of Consecutive Powers of Primes. ( abstract , arXiv )
- Chloe Makdad and Jonathan P. Sorenson. An Algorithm for Ennola's Second Theorem and Counting Smooth Numbers in Practice. ( abstract , arXiv )
-
Jana Sotáková.
Disorientation attacks on CSIDH.
We study a new class of fault-injection attacks against the CSIDH family of cryptographic group actions. In CSIDH, one considers the action of a certain class group cl(O) on a certain set of supersingular elliptic curves. This action is typically only computed for ideals of smooth norm, via a sequence of small-degree isogenies (call these steps). The secret information is how many times we perform each of these steps.
We consider injecting a fault (error) in a specific subroutine of the group evaluation, effectively flipping the direction of some isogeny steps. With this error, the result is a different supersingular elliptic curve, a `faulty curve'. The rest of the computation is not affected, and the faulty curve cannot easily be discovered from inspecting the result: in the end, we computed the group action by a slightly different element. More specifically, inside the isogeny graph, the difference between the correct result and such a faulty curve is precisely (twice) the steps that were flipped, which leaks information on the secret.
The practical details of this attack are implementation specific, but we develop a general algorithm that recovers information on the secret key from only a modest number of successful faults and computational resources. We argue that our attack is inherent to the way we compute isogenies. Therefore, almost all implementations in the CSIDH family are vulnerable to this attack and need to be strengthened, so we propose lightweight countermeasures. This is joint work with Gustavo Banegas, Juliane Krämer, Tanja Lange, Michael Meyer, Lorenz Panny, Krijn Reijnders, and Monika Trimoska.