Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information | IACR Transactions on Cryptographic Hardware and Embedded Systems

<!DOCTYPE html> <html lang="en" xml:lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title> Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information | IACR Transactions on Cryptographic Hardware and Embedded Systems </title> <meta name="generator" content="Open Journal Systems 3.4.0.5"> <link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" /> <meta name="DC.Creator.PersonalName" content="Marcus Brinkmann"/> <meta name="DC.Creator.PersonalName" content="Chitchanok Chuengsatiansup"/> <meta name="DC.Creator.PersonalName" content="Alexander May"/> <meta name="DC.Creator.PersonalName" content="Julian Nowakowski"/> <meta name="DC.Creator.PersonalName" content="Yuval Yarom"/> <meta name="DC.Date.created" scheme="ISO8601" content="2025-03-04"/> <meta name="DC.Date.dateSubmitted" scheme="ISO8601" content="2025-03-03"/> <meta name="DC.Date.issued" scheme="ISO8601" content="2025-03-04"/> <meta name="DC.Date.modified" scheme="ISO8601" content="2025-03-04"/> <meta name="DC.Description" xml:lang="en" content="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."/> <meta name="DC.Format" scheme="IMT" content="application/pdf"/> <meta name="DC.Identifier" content="12043"/> <meta name="DC.Identifier.pageNumber" content="94-125"/> <meta name="DC.Identifier.DOI" content="10.46586/tches.v2025.i2.94-125"/> <meta name="DC.Identifier.URI" content="https://tches.iacr.org/index.php/TCHES/article/view/12043"/> <meta name="DC.Language" scheme="ISO639-1" content="en"/> <meta name="DC.Rights" content="Copyright (c) 2025 Marcus Brinkmann, Chitchanok Chuengsatiansup, Alexander May, Julian Nowakowski, Yuval Yarom"/> <meta name="DC.Rights" content="https://creativecommons.org/licenses/by/4.0"/> <meta name="DC.Source" content="IACR Transactions on Cryptographic Hardware and Embedded Systems"/> <meta name="DC.Source.ISSN" content="2569-2925"/> <meta name="DC.Source.Issue" content="2"/> <meta name="DC.Source.Volume" content="2025"/> <meta name="DC.Source.URI" content="https://tches.iacr.org/index.php/TCHES"/> <meta name="DC.Subject" xml:lang="en" content="McEliece"/> <meta name="DC.Subject" xml:lang="en" content="Gaussian elimination"/> <meta name="DC.Subject" xml:lang="en" content="Side-channel leakage"/> <meta name="DC.Subject" xml:lang="en" content="Key recovery with hints"/> <meta name="DC.Title" content="Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information"/> <meta name="DC.Type" content="Text.Serial.Journal"/> <meta name="DC.Type.articleType" content="Articles"/> <meta name="gs_meta_revision" content="1.1"/> <meta name="citation_journal_title" content="IACR Transactions on Cryptographic Hardware and Embedded Systems"/> <meta name="citation_journal_abbrev" content="TCHES"/> <meta name="citation_issn" content="2569-2925"/> <meta name="citation_author" content="Marcus Brinkmann"/> <meta name="citation_author_institution" content="Ruhr University Bochum, Bochum, Germany"/> <meta name="citation_author" content="Chitchanok Chuengsatiansup"/> <meta name="citation_author_institution" content="The University of Klagenfurt, Klagenfurt, Austria"/> <meta name="citation_author" content="Alexander May"/> <meta name="citation_author_institution" content="Ruhr University Bochum, Bochum, Germany"/> <meta name="citation_author" content="Julian Nowakowski"/> <meta name="citation_author_institution" content="Ruhr University Bochum, Bochum, Germany"/> <meta name="citation_author" content="Yuval Yarom"/> <meta name="citation_author_institution" content="Ruhr University Bochum, Bochum, Germany"/> <meta name="citation_title" content="Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information"/> <meta name="citation_language" content="en"/> <meta name="citation_date" content="2025/03/04"/> <meta name="citation_volume" content="2025"/> <meta name="citation_issue" content="2"/> <meta name="citation_firstpage" content="94"/> <meta name="citation_lastpage" content="125"/> <meta name="citation_doi" content="10.46586/tches.v2025.i2.94-125"/> <meta name="citation_abstract_html_url" content="https://tches.iacr.org/index.php/TCHES/article/view/12043"/> <meta name="citation_abstract" xml:lang="en" content="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."/> <meta name="citation_keywords" xml:lang="en" content="McEliece"/> <meta name="citation_keywords" xml:lang="en" content="Gaussian elimination"/> <meta name="citation_keywords" xml:lang="en" content="Side-channel leakage"/> <meta name="citation_keywords" xml:lang="en" content="Key recovery with hints"/> <meta name="citation_pdf_url" content="https://tches.iacr.org/index.php/TCHES/article/download/12043/11887"/> <link rel="stylesheet" href="https://tches.iacr.org/index.php/TCHES/$$$call$$$/page/page/css?name=stylesheet" type="text/css" /><link rel="stylesheet" href="https://tches.iacr.org/index.php/TCHES/$$$call$$$/page/page/css?name=font" type="text/css" /><link rel="stylesheet" href="https://tches.iacr.org/lib/pkp/styles/fontawesome/fontawesome.css?v=3.4.0.5" type="text/css" /><link rel="stylesheet" href="https://tches.iacr.org/plugins/generic/citationStyleLanguage/css/citationStyleLanguagePlugin.css?v=3.4.0.5" type="text/css" /> </head> <body class="pkp_page_article pkp_op_view has_site_logo" dir="ltr"> <div class="pkp_structure_page"> <header class="pkp_structure_head" id="headerNavigationContainer" role="banner"> <nav class="cmp_skip_to_content" aria-label="Jump to content links"> <a href="#pkp_content_main">Skip to main content</a> <a href="#siteNav">Skip to main navigation menu</a> <a href="#pkp_content_footer">Skip to site footer</a> </nav> <div class="pkp_head_wrapper"> <div class="pkp_site_name_wrapper"> <button class="pkp_site_nav_toggle"> <span>Open Menu</span> </button> <div class="pkp_site_name"> <a href=" https://tches.iacr.org/index.php/TCHES/index " class="is_img"> <img src="https://tches.iacr.org/public/journals/7/pageHeaderLogoImage_en_US.png" width="200" height="38" alt="Ruhr-Universität Bochum" /> </a> </div> </div> <nav class="pkp_site_nav_menu" aria-label="Site Navigation"> <a id="siteNav"></a> <div class="pkp_navigation_primary_row"> <div class="pkp_navigation_primary_wrapper"> <ul id="navigationPrimary" class="pkp_navigation_primary pkp_nav_list"> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/index"> Home </a> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/issue/current"> Current </a> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/issue/archive"> Archives </a> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/submissions1"> Submissions </a> <ul> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/cfp"> Call for Papers </a> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/submission"> Paper Submission </a> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/camera-ready"> Camera-ready Submission </a> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/ethics"> Publication Ethics </a> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/retractions"> Retraction Policy </a> </li> </ul> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/faq"> FAQ </a> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/editorial"> Editorial Board </a> </li> <li class=""> <a href="https://tches.iacr.org/index.php/TCHES/contact"> Contact </a> </li> <li class=""> <a href="https://ches.iacr.org/"> CHES </a> </li> </ul> <div class="pkp_navigation_search_wrapper"> <a href="https://tches.iacr.org/index.php/TCHES/search" class="pkp_search pkp_search_desktop"> <span class="fa fa-search" aria-hidden="true"></span> Search </a> </div> </div> </div> <div class="pkp_navigation_user_wrapper" id="navigationUserWrapper"> <ul id="navigationUser" class="pkp_navigation_user pkp_nav_list"> <li class="profile"> <a href="https://tches.iacr.org/index.php/TCHES/login"> Login </a> </li> </ul> </div> </nav> </div> </header> <div class="pkp_structure_content has_sidebar"> <div class="pkp_structure_main" role="main"> <a id="pkp_content_main"></a> <div class="page page_article"> <nav class="cmp_breadcrumbs" role="navigation" aria-label="You are here:"> <ol> <li> <a href="https://tches.iacr.org/index.php/TCHES/index"> Home </a> <span class="separator">/</span> </li> <li> <a href="https://tches.iacr.org/index.php/TCHES/issue/archive"> Archives </a> <span class="separator">/</span> </li> <li> <a href="https://tches.iacr.org/index.php/TCHES/issue/view/378"> Vol. 2025 No. 2 </a> <span class="separator">/</span> </li> <li class="current" aria-current="page"> <span aria-current="page"> Articles </span> </li> </ol> </nav> <article class="obj_article_details"> <h1 class="page_title"> Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information </h1> <div class="row"> <div class="main_entry"> <section class="item authors"> <h2 class="pkp_screen_reader">Authors</h2> <ul class="authors"> <li> <span class="name"> Marcus Brinkmann </span> <span class="affiliation"> Ruhr University Bochum, Bochum, Germany </span> <span class="orcid"> <a href="https://orcid.org/0000-0001-5649-6357" target="_blank"> https://orcid.org/0000-0001-5649-6357 </a> </span> </li> <li> <span class="name"> Chitchanok Chuengsatiansup </span> <span class="affiliation"> The University of Klagenfurt, Klagenfurt, Austria </span> </li> <li> <span class="name"> Alexander May </span> <span class="affiliation"> Ruhr University Bochum, Bochum, Germany </span> </li> <li> <span class="name"> Julian Nowakowski </span> <span class="affiliation"> Ruhr University Bochum, Bochum, Germany </span> </li> <li> <span class="name"> Yuval Yarom </span> <span class="affiliation"> Ruhr University Bochum, Bochum, Germany </span> </li> </ul> </section> <section class="item doi"> <h2 class="label"> DOI: </h2> <span class="value"> <a href="https://doi.org/10.46586/tches.v2025.i2.94-125"> https://doi.org/10.46586/tches.v2025.i2.94-125 </a> </span> </section> <section class="item keywords"> <h2 class="label"> Keywords: </h2> <span class="value"> McEliece, Gaussian elimination, Side-channel leakage, Key recovery with hints </span> </section> <section class="item abstract"> <h2 class="label">Abstract</h2> <p>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.<br>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 <em>r</em> ≈ 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 <em>r</em> . We demonstrate our attack on the constant-time reference implementation of Classic McEliece in a single-trace setting, using an STM32L592 ARM processor.<br>Our result stresses the necessity of properly protecting highly structured code-based schemes such as McEliece against side-channel leakage.</p> </section> </div> <div class="entry_details"> <div class="item galleys"> <h2 class="pkp_screen_reader"> Downloads </h2> <ul class="value galleys_links"> <li> <a class="obj_galley_link pdf" href="https://tches.iacr.org/index.php/TCHES/article/view/12043/11887"> PDF </a> </li> </ul> </div> <div class="item published"> <section class="sub_item"> <h2 class="label"> Published </h2> <div class="value"> <span>2025-03-04</span> </div> </section> </div> <div class="item issue"> <section class="sub_item"> <h2 class="label"> Issue </h2> <div class="value"> <a class="title" href="https://tches.iacr.org/index.php/TCHES/issue/view/378"> Vol. 2025 No. 2 </a> </div> </section> <section class="sub_item"> <h2 class="label"> Section </h2> <div class="value"> Articles </div> </section> </div> <div class="item copyright"> <h2 class="label"> License </h2> <p>Copyright (c) 2025 Marcus Brinkmann, Chitchanok Chuengsatiansup, Alexander May, Julian Nowakowski, Yuval Yarom</p> <a rel="license" href="https://creativecommons.org/licenses/by/4.0/"><img alt="Creative Commons License" src="//i.creativecommons.org/l/by/4.0/88x31.png" /></a><p>This work is licensed under a <a rel="license" href="https://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>.</p> </div> <div class="item citation"> <section class="sub_item citation_display"> <h2 class="label"> How to Cite </h2> <div class="value"> <div id="citationOutput" role="region" aria-live="polite"> <div class="csl-bib-body"> <div class="csl-entry">Brinkmann, M., Chuengsatiansup, C., May, A., Nowakowski, J., & Yarom, Y. (2025). Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information. <i>IACR Transactions on Cryptographic Hardware and Embedded Systems</i>, <i>2025</i>(2), 94-125. <a href="https://doi.org/10.46586/tches.v2025.i2.94-125">https://doi.org/10.46586/tches.v2025.i2.94-125</a></div> </div> </div> <div class="citation_formats"> <button class="citation_formats_button label" aria-controls="cslCitationFormats" aria-expanded="false" data-csl-dropdown="true"> More Citation Formats </button> <div id="cslCitationFormats" class="citation_formats_list" aria-hidden="true"> <ul class="citation_formats_styles"> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/acm-sig-proceedings?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/acm-sig-proceedings?submissionId=12043&publicationId=5594&issueId=378&return=json" > ACM </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/acs-nano?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/acs-nano?submissionId=12043&publicationId=5594&issueId=378&return=json" > ACS </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/apa?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/apa?submissionId=12043&publicationId=5594&issueId=378&return=json" > APA </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/associacao-brasileira-de-normas-tecnicas?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/associacao-brasileira-de-normas-tecnicas?submissionId=12043&publicationId=5594&issueId=378&return=json" > ABNT </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/chicago-author-date?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/chicago-author-date?submissionId=12043&publicationId=5594&issueId=378&return=json" > Chicago </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/harvard-cite-them-right?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/harvard-cite-them-right?submissionId=12043&publicationId=5594&issueId=378&return=json" > Harvard </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/ieee?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/ieee?submissionId=12043&publicationId=5594&issueId=378&return=json" > IEEE </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/modern-language-association?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/modern-language-association?submissionId=12043&publicationId=5594&issueId=378&return=json" > MLA </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/turabian-fullnote-bibliography?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/turabian-fullnote-bibliography?submissionId=12043&publicationId=5594&issueId=378&return=json" > Turabian </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/vancouver?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/vancouver?submissionId=12043&publicationId=5594&issueId=378&return=json" > Vancouver </a> </li> <li> <a aria-controls="citationOutput" href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/ama?submissionId=12043&publicationId=5594&issueId=378" data-load-citation data-json-href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/get/ama?submissionId=12043&publicationId=5594&issueId=378&return=json" > AMA </a> </li> </ul> <div class="label"> Download Citation </div> <ul class="citation_formats_styles"> <li> <a href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/download/ris?submissionId=12043&publicationId=5594&issueId=378"> <span class="fa fa-download"></span> Endnote/Zotero/Mendeley (RIS) </a> </li> <li> <a href="https://tches.iacr.org/index.php/TCHES/citationstylelanguage/download/bibtex?submissionId=12043&publicationId=5594&issueId=378"> <span class="fa fa-download"></span> BibTeX </a> </li> </ul> </div> </div> </div> </section> </div> </div> </div> </article> </div> </div> <div class="pkp_structure_sidebar left" role="complementary"> <div class="pkp_block block_custom" id="customblock-iacr-logo"> <h2 class="title pkp_screen_reader">iacr-logo</h2> <div class="content"> <p><a title="IACR logo" href="https://www.iacr.org"><img src="/public/site/images/jwloka/iacrlogo_trans.png" width="100" height="100"></a></p> </div> </div> </div> </div> <div class="pkp_structure_footer_wrapper" role="contentinfo"> <a id="pkp_content_footer"></a> <div class="pkp_structure_footer"> <div class="pkp_footer_content"> <p><a title="Imprint" href="/index.php/TCHES/impressum">Imprint</a> | <a title="Personal Data Notice" href="https://ojs.ub.rub.de/index.php/index/PDN">Personal Data Notice</a></p> </div> <div class="pkp_brand_footer"> <a href="https://tches.iacr.org/index.php/TCHES/about/aboutThisPublishingSystem"> <img alt="More information about the publishing system, Platform and Workflow by OJS/PKP." src="https://tches.iacr.org/templates/images/ojs_brand.png"> </a> </div> </div> </div> </div> <script src="https://tches.iacr.org/lib/pkp/lib/vendor/components/jquery/jquery.min.js?v=3.4.0.5" type="text/javascript"></script><script src="https://tches.iacr.org/lib/pkp/lib/vendor/components/jqueryui/jquery-ui.min.js?v=3.4.0.5" type="text/javascript"></script><script src="https://tches.iacr.org/plugins/themes/default/js/lib/popper/popper.js?v=3.4.0.5" type="text/javascript"></script><script src="https://tches.iacr.org/plugins/themes/default/js/lib/bootstrap/util.js?v=3.4.0.5" type="text/javascript"></script><script src="https://tches.iacr.org/plugins/themes/default/js/lib/bootstrap/dropdown.js?v=3.4.0.5" type="text/javascript"></script><script src="https://tches.iacr.org/plugins/themes/default/js/main.js?v=3.4.0.5" type="text/javascript"></script><script src="https://tches.iacr.org/plugins/generic/citationStyleLanguage/js/articleCitation.js?v=3.4.0.5" type="text/javascript"></script> </body> </html>

CINXE.COM

Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information | IACR Transactions on Cryptographic Hardware and Embedded Systems