Paper 2023/1536

Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information

Marcus Brinkmann, Ruhr University Bochum
Chitchanok Chuengsatiansup, University of Melbourne
Alexander May, Ruhr University Bochum
Julian Nowakowski, Ruhr University Bochum
Yuval Yarom, Ruhr University Bochum

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 a highly critical operation with respect to side-channel leakage. We assume leakage of the elementary row operations during Gaussian elimination, motivated by actual implementations of McEliece in real world cryptographic libraries (Classic McEliece and Botan). We propose a novel 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 can be flipped with probability as high as $\tau \approx 0.4$, our algorithm still succeeds 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 $\tau$. Technically, we introduce a novel cryptanalytic decoding technique that exploits the high redundancy exhibited in the McEliece secret key. This allows our decoding routine to succeed in reconstructing each column of the secret key successively. Our result stresses the necessity to well protect highly structured code-based schemes such as McEliece against side-channel leakage.

Available format(s)
Attacks and cryptanalysis
Publication info
McElieceGaussian eliminationSide-channel leakageKey recovery with hints
Contact author(s)
marcus brinkmann @ rub de
c chuengsatiansup @ unimelb edu au
alex may @ rub de
julian nowakowski @ rub de
yuval yarom @ rub de
2023-10-09: approved
2023-10-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marcus Brinkmann and Chitchanok Chuengsatiansup and Alexander May and Julian Nowakowski and Yuval Yarom},
      title = {Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1536},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.