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

DOI:

https://doi.org/10.46586/tches.v2022.i4.800-827

Keywords:

Code-based cryptography, NIST post-quantum standardization, sidechannel attacks, Classic McEliece

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.

Downloads

Published

2022-08-31

Issue

Section

Articles

How to Cite

A Key-Recovery Side-Channel Attack on Classic McEliece Implementations. (2022). IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(4), 800-827. https://doi.org/10.46586/tches.v2022.i4.800-827