Single trace HQC shared key recovery with SASCA
This paper presents practicable single trace attacks against the Hamming Quasi-Cyclic (HQC) Key Encapsulation Mechanism. These attacks are the first Soft Analytical Side-Channel Attacks (SASCA) against code-based cryptography. We mount SASCA based on Belief Propagation (BP) on several steps of HQC’...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2024-03-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/11421 |
| _version_ | 1797262243164848128 |
|---|---|
| author | Guillaume Goy Julien Maillard Philippe Gaborit Antoine Loiseau |
| author_facet | Guillaume Goy Julien Maillard Philippe Gaborit Antoine Loiseau |
| author_sort | Guillaume Goy |
| collection | DOAJ |
| description |
This paper presents practicable single trace attacks against the Hamming Quasi-Cyclic (HQC) Key Encapsulation Mechanism. These attacks are the first Soft Analytical Side-Channel Attacks (SASCA) against code-based cryptography. We mount SASCA based on Belief Propagation (BP) on several steps of HQC’s decapsulation process. Firstly, we target the Reed-Solomon (RS) decoder involved in the HQC publicly known code. We perform simulated attacks under Hamming weight leakage model, and reach excellent accuracies (superior to 0.9) up to a high noise level (σ = 3), thanks to a re-decoding strategy. In a real case attack scenario, on a STM32F407, this attack leads to a perfect success rate. Secondly, we conduct an analogous attack against the RS encoder used during the re-encryption step required by the Fujisaki-Okamoto-like transform. Both in simulation and practical instances, results are satisfactory and this attack represents a threat to the security of HQC. Finally, we analyze the strength of countermeasures based on masking and shuffling strategies. In line with previous SASCA literature targeting Kyber, we show that masking HQC is a limited countermeasure against BP attacks, as well as shuffling countermeasures adapted from Kyber. We evaluate the “full shuffling” strategy which thwarts our attack by introducing sufficient combinatorial complexity. Eventually, we highlight the difficulty of protecting the current RS encoder with a shuffling strategy. A possible countermeasure would be to consider another encoding algorithm for the scheme to support a full shuffling. Since the encoding subroutine is only a small part of the implementation, it would come at a small cost.
|
| first_indexed | 2024-04-24T23:54:01Z |
| format | Article |
| id | doaj.art-6e6b08fca2c34532a8f959d0315ce8b2 |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-24T23:54:01Z |
| publishDate | 2024-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-6e6b08fca2c34532a8f959d0315ce8b22024-03-14T16:24:49ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252024-03-012024210.46586/tches.v2024.i2.64-87Single trace HQC shared key recovery with SASCAGuillaume Goy0Julien Maillard1Philippe Gaborit2Antoine Loiseau3XLIM, University of Limoges, Limoges, France; Univ. Grenoble Alpes, CEA, Leti, MINATEC Campus, F-38054 Grenoble, FranceXLIM, University of Limoges, Limoges, France; Univ. Grenoble Alpes, CEA, Leti, MINATEC Campus, F-38054 Grenoble, FranceXLIM, University of Limoges, Limoges, FranceUniv. Grenoble Alpes, CEA, Leti, MINATEC Campus, F-38054 Grenoble, France This paper presents practicable single trace attacks against the Hamming Quasi-Cyclic (HQC) Key Encapsulation Mechanism. These attacks are the first Soft Analytical Side-Channel Attacks (SASCA) against code-based cryptography. We mount SASCA based on Belief Propagation (BP) on several steps of HQC’s decapsulation process. Firstly, we target the Reed-Solomon (RS) decoder involved in the HQC publicly known code. We perform simulated attacks under Hamming weight leakage model, and reach excellent accuracies (superior to 0.9) up to a high noise level (σ = 3), thanks to a re-decoding strategy. In a real case attack scenario, on a STM32F407, this attack leads to a perfect success rate. Secondly, we conduct an analogous attack against the RS encoder used during the re-encryption step required by the Fujisaki-Okamoto-like transform. Both in simulation and practical instances, results are satisfactory and this attack represents a threat to the security of HQC. Finally, we analyze the strength of countermeasures based on masking and shuffling strategies. In line with previous SASCA literature targeting Kyber, we show that masking HQC is a limited countermeasure against BP attacks, as well as shuffling countermeasures adapted from Kyber. We evaluate the “full shuffling” strategy which thwarts our attack by introducing sufficient combinatorial complexity. Eventually, we highlight the difficulty of protecting the current RS encoder with a shuffling strategy. A possible countermeasure would be to consider another encoding algorithm for the scheme to support a full shuffling. Since the encoding subroutine is only a small part of the implementation, it would come at a small cost. https://tches.iacr.org/index.php/TCHES/article/view/11421Soft Analytical Side-Channel Attack (SASCA)Belief Propagation (BP)Hamming Quasi-Cyclic (HQC)Post-Quantum Cryptography (PQC)Single TraceShared key recovery |
| spellingShingle | Guillaume Goy Julien Maillard Philippe Gaborit Antoine Loiseau Single trace HQC shared key recovery with SASCA Transactions on Cryptographic Hardware and Embedded Systems Soft Analytical Side-Channel Attack (SASCA) Belief Propagation (BP) Hamming Quasi-Cyclic (HQC) Post-Quantum Cryptography (PQC) Single Trace Shared key recovery |
| title | Single trace HQC shared key recovery with SASCA |
| title_full | Single trace HQC shared key recovery with SASCA |
| title_fullStr | Single trace HQC shared key recovery with SASCA |
| title_full_unstemmed | Single trace HQC shared key recovery with SASCA |
| title_short | Single trace HQC shared key recovery with SASCA |
| title_sort | single trace hqc shared key recovery with sasca |
| topic | Soft Analytical Side-Channel Attack (SASCA) Belief Propagation (BP) Hamming Quasi-Cyclic (HQC) Post-Quantum Cryptography (PQC) Single Trace Shared key recovery |
| url | https://tches.iacr.org/index.php/TCHES/article/view/11421 |
| work_keys_str_mv | AT guillaumegoy singletracehqcsharedkeyrecoverywithsasca AT julienmaillard singletracehqcsharedkeyrecoverywithsasca AT philippegaborit singletracehqcsharedkeyrecoverywithsasca AT antoineloiseau singletracehqcsharedkeyrecoverywithsasca |