Paper 2025/2043 Original: eprint.iacr.org/2025/2043 ↗

Key-Recovery Side-Channel Attack on the Berlekamp-Massey Decoding Algorithm in the Classic McEliece KEM

Abstract

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.