Full Key-Recovery Cubic-Time Template Attack on Classic McEliece Decapsulation
Classic McEliece is one of the three code-based candidates in the fourth round of the NIST post-quantum cryptography standardization process in the Key Encapsulation Mechanism category. As such, its decapsulation algorithm is used to recover the session key associated with a ciphertext using the pr...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2024-12-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/TCHES/article/view/11933 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850264003683549184 |
|---|---|
| author | Vlad-Florin Drăgoi Brice Colombier Nicolas Vallet Pierre-Louis Cayrel Vincent Grosso |
| author_facet | Vlad-Florin Drăgoi Brice Colombier Nicolas Vallet Pierre-Louis Cayrel Vincent Grosso |
| author_sort | Vlad-Florin Drăgoi |
| collection | DOAJ |
| description |
Classic McEliece is one of the three code-based candidates in the fourth round of the NIST post-quantum cryptography standardization process in the Key Encapsulation Mechanism category. As such, its decapsulation algorithm is used to recover the session key associated with a ciphertext using the private key. In this article, we propose a new side-channel attack on the syndrome computation in the decapsulation algorithm that recovers the private key, which consists of the private Goppa polynomial g and the permuted support L. The attack relies on both practical aspects and theoretical contributions, namely that the side-channel distinguisher can accurately discriminate elements of the permuted support L, while relying only on a standard noisy Hamming weight leakage assumption and that there exists a cubic-time algorithm that uses this information to recover the private Goppa polynomial g. Compared with previous work targeting the Classic McEliece private key, this drastically improves both on the assumptions made in the attacker model and on the overall efficiency of the key-recovery algorithm. We have carried out the attack in practice on a microcontroller target running the reference implementation of Classic McEliece, and make the full attack source code available.
|
| format | Article |
| id | doaj-art-d14d03b0b71b4e1a8499f46308d66b62 |
| institution | OA Journals |
| issn | 2569-2925 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj-art-d14d03b0b71b4e1a8499f46308d66b622025-08-20T01:54:50ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252024-12-012025110.46586/tches.v2025.i1.367-391Full Key-Recovery Cubic-Time Template Attack on Classic McEliece DecapsulationVlad-Florin Drăgoi0Brice Colombier1Nicolas Vallet2Pierre-Louis Cayrel3Vincent Grosso4Faculty of Exact Sciences, Aurel Vlaicu University, Arad, Romania; LITIS, University of Rouen Normandie, Saint-Etienne du Rouvray, FranceUniversité Jean Monnet Saint-Etienne, CNRS, Institut d Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT-ETIENNE, FranceUniversité Jean Monnet Saint-Etienne, CNRS, Institut d Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT-ETIENNE, FranceUniversité Jean Monnet Saint-Etienne, CNRS, Institut d Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT-ETIENNE, FranceUniversité Jean Monnet Saint-Etienne, CNRS, Institut d Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT-ETIENNE, France Classic McEliece is one of the three code-based candidates in the fourth round of the NIST post-quantum cryptography standardization process in the Key Encapsulation Mechanism category. As such, its decapsulation algorithm is used to recover the session key associated with a ciphertext using the private key. In this article, we propose a new side-channel attack on the syndrome computation in the decapsulation algorithm that recovers the private key, which consists of the private Goppa polynomial g and the permuted support L. The attack relies on both practical aspects and theoretical contributions, namely that the side-channel distinguisher can accurately discriminate elements of the permuted support L, while relying only on a standard noisy Hamming weight leakage assumption and that there exists a cubic-time algorithm that uses this information to recover the private Goppa polynomial g. Compared with previous work targeting the Classic McEliece private key, this drastically improves both on the assumptions made in the attacker model and on the overall efficiency of the key-recovery algorithm. We have carried out the attack in practice on a microcontroller target running the reference implementation of Classic McEliece, and make the full attack source code available. https://tosc.iacr.org/index.php/TCHES/article/view/11933Post-quantum cryptographyCode-based cryptographyClassic McElieceSide-channel attacks |
| spellingShingle | Vlad-Florin Drăgoi Brice Colombier Nicolas Vallet Pierre-Louis Cayrel Vincent Grosso Full Key-Recovery Cubic-Time Template Attack on Classic McEliece Decapsulation Transactions on Cryptographic Hardware and Embedded Systems Post-quantum cryptography Code-based cryptography Classic McEliece Side-channel attacks |
| title | Full Key-Recovery Cubic-Time Template Attack on Classic McEliece Decapsulation |
| title_full | Full Key-Recovery Cubic-Time Template Attack on Classic McEliece Decapsulation |
| title_fullStr | Full Key-Recovery Cubic-Time Template Attack on Classic McEliece Decapsulation |
| title_full_unstemmed | Full Key-Recovery Cubic-Time Template Attack on Classic McEliece Decapsulation |
| title_short | Full Key-Recovery Cubic-Time Template Attack on Classic McEliece Decapsulation |
| title_sort | full key recovery cubic time template attack on classic mceliece decapsulation |
| topic | Post-quantum cryptography Code-based cryptography Classic McEliece Side-channel attacks |
| url | https://tosc.iacr.org/index.php/TCHES/article/view/11933 |
| work_keys_str_mv | AT vladflorindragoi fullkeyrecoverycubictimetemplateattackonclassicmceliecedecapsulation AT bricecolombier fullkeyrecoverycubictimetemplateattackonclassicmceliecedecapsulation AT nicolasvallet fullkeyrecoverycubictimetemplateattackonclassicmceliecedecapsulation AT pierrelouiscayrel fullkeyrecoverycubictimetemplateattackonclassicmceliecedecapsulation AT vincentgrosso fullkeyrecoverycubictimetemplateattackonclassicmceliecedecapsulation |