International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Key-Recovery Side-Channel Attack on Classic McEliece Implementations

Authors:
Qian Guo , Dept. of Electrical and Information Technology, Lund University, Lund, Sweden
Andreas Johansson , Dept. of Electrical and Information Technology, Lund University, Lund, Sweden
Thomas Johansson , Dept. of Electrical and Information Technology, Lund University, Lund, Sweden
Download:
DOI: 10.46586/tches.v2022.i4.800-827
URL: https://tches.iacr.org/index.php/TCHES/article/view/9841
Search ePrint
Search Google
Presentation: Slides
Abstract: In this paper, we propose the first key-recovery side-channel attack on Classic McEliece, a KEM finalist in the NIST Post-quantum Cryptography Standardization Project. Our novel idea is to design an attack algorithm where we submit special ciphertexts to the decryption oracle that correspond to cases of single errors. Decoding of such ciphertexts involves only a single entry in a large secret permutation, which is part of the secret key. Through an identified leakage in the additive FFT step used to evaluate the error locator polynomial, a single entry of the secret permutation can be determined. Iterating this for other entries leads to full secret key recovery. The attack is described using power analysis both on the FPGA reference implementation and a software implementation running on an ARM Cortex-M4. We use a machine-learning-based classification algorithm to determine the error locator polynomial from a single trace. The attack is fully implemented and evaluated in the Chipwhisperer framework and is successful in practice. For the smallest parameter set, it is using about 300 traces for partial key recovery and less than 800 traces for full key recovery, in the FPGA case. A similar number of traces are required for a successful attack on the ARM software implementation.
BibTeX
@article{tches-2022-32386,
  title={A Key-Recovery Side-Channel Attack on Classic McEliece Implementations},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 4},
  pages={800-827},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9841},
  doi={10.46586/tches.v2022.i4.800-827},
  author={Qian Guo and Andreas Johansson and Thomas Johansson},
  year=2022
}