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
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 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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
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
History
2023-10-09: approved
2023-10-07: received
See all versions
Short URL
https://ia.cr/2023/1536
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1536,
      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},
      url = {https://eprint.iacr.org/2023/1536}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.