Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information
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...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2025-03-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/12043 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850252216798019584 |
|---|---|
| author | Marcus Brinkmann Chitchanok Chuengsatiansup Alexander May Julian Nowakowski Yuval Yarom |
| author_facet | Marcus Brinkmann Chitchanok Chuengsatiansup Alexander May Julian Nowakowski Yuval Yarom |
| author_sort | Marcus Brinkmann |
| collection | DOAJ |
| description |
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 highly critical with respect to side-channel leakage. We assume leakage of the elementary row operations during Gaussian elimination, motivated by McEliece implementations in the cryptographic libraries Classic McEliece and Botan.
We propose a novel decoding 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 is flipped with probability as high as r ≈ 0.4, we succeed 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 r . We demonstrate our attack on the constant-time reference implementation of Classic McEliece in a single-trace setting, using an STM32L592 ARM processor.
Our result stresses the necessity of properly protecting highly structured code-based schemes such as McEliece against side-channel leakage.
|
| format | Article |
| id | doaj-art-6fbb80c435a74aada91a7bece212df05 |
| institution | OA Journals |
| issn | 2569-2925 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj-art-6fbb80c435a74aada91a7bece212df052025-08-20T01:57:43ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252025-03-012025210.46586/tches.v2025.i2.94-125Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel InformationMarcus Brinkmann0https://orcid.org/0000-0001-5649-6357Chitchanok Chuengsatiansup1Alexander May2Julian Nowakowski3Yuval Yarom4Ruhr University Bochum, Bochum, GermanyThe University of Klagenfurt, Klagenfurt, AustriaRuhr University Bochum, Bochum, GermanyRuhr University Bochum, Bochum, GermanyRuhr University Bochum, Bochum, Germany 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 highly critical with respect to side-channel leakage. We assume leakage of the elementary row operations during Gaussian elimination, motivated by McEliece implementations in the cryptographic libraries Classic McEliece and Botan. We propose a novel decoding 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 is flipped with probability as high as r ≈ 0.4, we succeed 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 r . We demonstrate our attack on the constant-time reference implementation of Classic McEliece in a single-trace setting, using an STM32L592 ARM processor. Our result stresses the necessity of properly protecting highly structured code-based schemes such as McEliece against side-channel leakage. https://tches.iacr.org/index.php/TCHES/article/view/12043McElieceGaussian eliminationSide-channel leakageKey recovery with hints |
| spellingShingle | Marcus Brinkmann Chitchanok Chuengsatiansup Alexander May Julian Nowakowski Yuval Yarom Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information Transactions on Cryptographic Hardware and Embedded Systems McEliece Gaussian elimination Side-channel leakage Key recovery with hints |
| title | Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information |
| title_full | Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information |
| title_fullStr | Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information |
| title_full_unstemmed | Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information |
| title_short | Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information |
| title_sort | leaky mceliece secret key recovery from highly erroneous side channel information |
| topic | McEliece Gaussian elimination Side-channel leakage Key recovery with hints |
| url | https://tches.iacr.org/index.php/TCHES/article/view/12043 |
| work_keys_str_mv | AT marcusbrinkmann leakymceliecesecretkeyrecoveryfromhighlyerroneoussidechannelinformation AT chitchanokchuengsatiansup leakymceliecesecretkeyrecoveryfromhighlyerroneoussidechannelinformation AT alexandermay leakymceliecesecretkeyrecoveryfromhighlyerroneoussidechannelinformation AT juliannowakowski leakymceliecesecretkeyrecoveryfromhighlyerroneoussidechannelinformation AT yuvalyarom leakymceliecesecretkeyrecoveryfromhighlyerroneoussidechannelinformation |