Paper 2023/1536
Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information
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
-
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} }