CryptoDB
Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information
| Authors: | |
|---|---|
| Download: | |
| Abstract: | The McEliece cryptosystem is a strong contender for post-quantum schemes, including key encapsulation for confidentiality of key exchanges in network protocols. A McEliece secret key is a structured parity check matrix that is transformed via Gaussian elimination into an unstructured public key. We show that this transformation is highly critical with respect to side-channel leakage. We assume leakage of the elementary row operations during Gaussian elimination, motivated by McEliece implementations in the cryptographic libraries Classic McEliece and Botan.We propose a novel decoding algorithm to reconstruct a secret key from its public key with information from a Gaussian transformation leak. Even if the obtained side-channel leakage is extremely noisy, i.e., each bit is flipped with probability as high as r ≈ 0.4, we succeed to recover the secret key in a matter of minutes for all proposed (Classic) McEliece instantiations. Remarkably, for high-security McEliece parameters, our attack is more powerful in the sense that it can tolerate even larger r . We demonstrate our attack on the constant-time reference implementation of Classic McEliece in a single-trace setting, using an STM32L592 ARM processor.Our result stresses the necessity of properly protecting highly structured code-based schemes such as McEliece against side-channel leakage. |
BibTeX
@article{tches-2025-35223,
title={Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information},
journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
publisher={Ruhr-Universität Bochum},
volume={2025},
pages={94-125},
url={https://tches.iacr.org/index.php/TCHES/article/view/12043},
doi={10.46586/tches.v2025.i2.94-125},
author={Marcus Brinkmann and Chitchanok Chuengsatiansup and Alexander May and Julian Nowakowski and Yuval Yarom},
year=2025
}