Fault attack reveals secret keys in deterministic CSIDH cryptography
From if to Oops: Turning a conditional into a key-recovery oracle
Cryptography and Security
Summary
Deterministic CSIDH cryptography removes randomness to improve security, but this paper shows that it creates a new weakness. The researchers found a way to repeatedly disrupt a specific operation in the encryption process to learn secret keys one bit at a time. By observing if the output changes, they can recover the entire key efficiently. This attack works because the secret-dependent steps always happen at the same point, allowing targeted faults. They also suggest that adding randomness back can protect against this attack.
What this means in practice
- •For cryptographic engineers: Test implementations of deterministic CSIDH for susceptibility to fault attacks that recover secret keys via targeted instruction skipping.
- •For security auditors: Evaluate cryptographic products relying on deterministic isogeny-based schemes to ensure they include randomization countermeasures against fault attacks.
Authors
Gustavo Banegas, Nia Dimitrova, Monika Trimoska
Abstract
Deterministic variants of CSIDH remove randomness from the group action, either through implementation techniques or, as in Houben's deterministic CSIDH and OSIDH-LD, by design. Since earlier fault attacks on CSIDH mostly target random point sampling, determinism seems to close that avenue. We show that it opens another: every secret-dependent step occurs at a fixed, public point of every execution, so an attacker can fault the same step repeatedly. Our attack forces the mask that selects which of two lanes computes the next isogeny to zero, for example by skipping one instruction. Whether the output changes reveals whether a secret exponent reaches a chosen threshold, and a binary search over these thresholds recovers the full key with one fault per execution: at most 297 oracle queries for OSIDH-LD and 222 for deterministic CSIDH with CSIDH-512-sized keys. We recover full OSIDH-LD keys in a software fault simulation of the reference implementation, and show on a ChipWhisperer-Lite that the targeted instruction is skipped with probability at least 0.94 at an isolated fault position. Finally, we argue that fault resistance requires giving up determinism, and propose countermeasures relying on randomization.