Paper 2022/514

A Key-Recovery Side-Channel Attack on Classic McEliece

Qian Guo, Andreas Johansson, and Thomas Johansson

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 cipher-texts 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. Reiterating 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Code-based cryptographyNIST post-quantum standard- izationside-channel attacksClassic McEliece
Contact author(s)
qian guo @ eit lth se
andreas johansson @ eit lth se
thomas johansson @ eit lth se
History
2022-05-02: received
Short URL
https://ia.cr/2022/514
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/514,
      author = {Qian Guo and Andreas Johansson and Thomas Johansson},
      title = {A Key-Recovery Side-Channel Attack on Classic McEliece},
      howpublished = {Cryptology ePrint Archive, Paper 2022/514},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/514}},
      url = {https://eprint.iacr.org/2022/514}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.