Paper 2025/2043
Key-Recovery Side-Channel Attack on the Berlekamp-Massey Decoding Algorithm in the Classic McEliece KEM
, Faculty of Exact Sciences, Aurel Vlaicu University of Arad, Arad, RomaniaAbstract
In this article, we present a side-channel attack on unprotected implementations of the Berlekamp-Massey (BM) algorithm in both the reference implementation and an embedded implementation of the Classic McEliece KEM, where BM is used during decapsulation as part of the decoder implementation. We conduct a chosen cipher-text key recovery attack that exploits the power consumption of the BM, which is highly dependent on the secret Goppa support elements. We exploit the relation between plain-texts of small Hamming weight, secret elements in the Goppa support and power traces using an efficient Template Attack. Our method completely recovers the secret Goppa support for the first parameter set of the Classic McEliece KEM using a single attack trace per secret coefficient. The entire support can be recovered in less than 50 seconds. The remaining part of the secret, the Goppa polynomial, is recovered using Kirshanova and May’s algorithm (“Breaking Goppa with hints”) in less than 1 minute. Our experiments are performed on the reference implementation using the ChipWhisperer-Lite board platform with the ARM Cortex-M4 microcontroller. We also provide further insights into other implementations as well as an overview of possible extensions and limitations of our attack.
Note: This is revision 2 which was accepted at TCHES 2026.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- A minor revision of an IACR publication in TCHES 2026
- Keywords
- Post-quantum cryptographyCode-based cryptographyClassic McElieceSide-channel attacks
- Contact author(s)
-
andrei alexei @ stud acs upb ro
marios choudary @ upb ro
vlad dragoi @ uav ro - History
- 2026-07-06: revised
- 2025-11-05: received
- See all versions
- Short URL
- https://ia.cr/2025/2043
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/2043,
author = {Andrei Alexei and Marios Omar Choudary and Vlad-Florin Dragoi},
title = {Key-Recovery Side-Channel Attack on the Berlekamp-Massey Decoding Algorithm in the Classic {McEliece} {KEM}},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2043},
year = {2025},
url = {https://eprint.iacr.org/2025/2043}
}
