# American Institute of Mathematical Sciences

doi: 10.3934/amc.2020126
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## A practicable timing attack against HQC and its countermeasure

 1 Worldline, ZI Rue de la pointe, 59113 Seclin, France 2 University of Limoges, XLIM-DMI, 123, Av. Albert Thomas, 87060 Limoges, France 3 Atos Trustway, Avenue Jean Jaurès, 78340 Les Clayes-sous-Bois, University of Grenoble Alpes, CNRS, IF, 38000 Grenoble, France

Received  August 2019 Revised  January 2020 Early access December 2020

In this paper, we present a practicable chosen ciphertext timing attack retrieving the secret key of HQC. The attack exploits a correlation between the weight of the error to be decoded and the running time of the decoding algorithm of BCH codes. For the 128-bit security parameters of HQC, the attack runs in less than a minute on a desktop computer using roughly 6000 decoding requests and has a success probability of approximately 93 percent. To prevent this attack, we provide an implementation of a constant time algorithm for the decoding of BCH codes. Our implementation of the countermeasure achieves a constant time execution of the decoding process without a significant performance penalty.

Citation: Guillaume Wafo-Tapa, Slim Bettaieb, Loïc Bidoux, Philippe Gaborit, Etienne Marcatel. A practicable timing attack against HQC and its countermeasure. Advances in Mathematics of Communications, doi: 10.3934/amc.2020126
##### References:

show all references

##### References:
]">Figure 1.  Description of $\textsf{HQC.PKE}$ [1]
Decoding execution times (in CPU cycles) of various BCH codes for different error weights with field mutliplication implemented by lookup tables (variant 1)
Decoding execution times (in CPU cycles) of various BCH codes for different error weights with field multiplication implemented via $\textsf{pclmulqdq}$ instruction (variant 2)
Parameter sets for HQC [1]
 Instance $n_1$ $n_2$ $n$ $k$ $t$ $w$ $w_\mathbf{r} = w_\mathbf{e}$ security HQC-128-1 796 31 24, 677 256 60 67 77 128 HQC-192-1 766 57 43, 669 256 57 101 117 192 HQC-192-2 766 61 46, 747 256 57 101 117 192 HQC-256-1 766 83 63, 587 256 57 133 153 256 HQC-256-2 796 85 67, 699 256 60 133 153 256 HQC-256-3 796 89 70, 853 256 60 133 153 256
 Instance $n_1$ $n_2$ $n$ $k$ $t$ $w$ $w_\mathbf{r} = w_\mathbf{e}$ security HQC-128-1 796 31 24, 677 256 60 67 77 128 HQC-192-1 766 57 43, 669 256 57 101 117 192 HQC-192-2 766 61 46, 747 256 57 101 117 192 HQC-256-1 766 83 63, 587 256 57 133 153 256 HQC-256-2 796 85 67, 699 256 60 133 153 256 HQC-256-3 796 89 70, 853 256 60 133 153 256
The percentage of failed attacks against HQC-128-1 in function of the number of repeated requests to $\mathcal{O}^{HQC}_{\text{Time}}$ for $p = 100$ for $1000$ attacks
 Number of repetition of each request $1$ $3$ $5$ $7$ $9$ Percentage of failed attacks $100\%$ $99, 8\%$ $49, 7\%$ $8, 3\%$ $7, 6\%$
 Number of repetition of each request $1$ $3$ $5$ $7$ $9$ Percentage of failed attacks $100\%$ $99, 8\%$ $49, 7\%$ $8, 3\%$ $7, 6\%$
Attack complexity and bandwidth cost against HQC
 Complexity upper bound Requests $128-1$ $192-2$ $256-3$ $128-1$ $192-2$ $256-3$ Oracle $\textsf{Init}$ ($p=1$) $2^{25}$ $2^{26}$ $2^{27}$ $2$ $2$ $2$ First iteration $2^{35}$ $2^{36}$ $2^{37}$ $1793$ $1936$ $2257$ Second iteration - phase 1 $2^{31}$ $2^{34}$ $2^{35}$ $198$ $350$ $528$ Second iteration - phase 2 $2^{35}$ $2^{37}$ $2^{38}$ $3448$ $3564$ $3844$ Total $2^{36}$ $2^{38}$ $2^{39}$ $5441$ $5852$ $6631$
 Complexity upper bound Requests $128-1$ $192-2$ $256-3$ $128-1$ $192-2$ $256-3$ Oracle $\textsf{Init}$ ($p=1$) $2^{25}$ $2^{26}$ $2^{27}$ $2$ $2$ $2$ First iteration $2^{35}$ $2^{36}$ $2^{37}$ $1793$ $1936$ $2257$ Second iteration - phase 1 $2^{31}$ $2^{34}$ $2^{35}$ $198$ $350$ $528$ Second iteration - phase 2 $2^{35}$ $2^{37}$ $2^{38}$ $3448$ $3564$ $3844$ Total $2^{36}$ $2^{38}$ $2^{39}$ $5441$ $5852$ $6631$
Running time (CPU cycles) and overhead when original or constant time BCH decoding is used in the decapsulation step of HQC
 HQC.$\textsf{Decaps}$ Overhead Original BCH Constant time BCH HQC-128-1 $507285$ $563414$ $11.06\%$ HQC-192-1 $947552$ $995272$ $5.05\%$ HQC-192-2 $992057$ $1047054$ $5.54\%$ HQC-256-1 $1490993$ $1538824$ $3.21\%$ HQC-256-2 $1562207$ $1616673$ $3.49\%$ HQC-256-3 $1617269$ $1675195$ $3.58\%$
 HQC.$\textsf{Decaps}$ Overhead Original BCH Constant time BCH HQC-128-1 $507285$ $563414$ $11.06\%$ HQC-192-1 $947552$ $995272$ $5.05\%$ HQC-192-2 $992057$ $1047054$ $5.54\%$ HQC-256-1 $1490993$ $1538824$ $3.21\%$ HQC-256-2 $1562207$ $1616673$ $3.49\%$ HQC-256-3 $1617269$ $1675195$ $3.58\%$
The mean of the decoding execution time (in CPU cycles) of various BCH codes for errors of weight 0 and 1 with field multiplication implemented by lookup tables (variant 1)
 BCH code $[n, k, d]$ (variant 1) Number of errors to be decoded $0$ error $1$ error [$766, 256, 115$] $103466$ $103436$ [$796, 256, 121$] $105349$ $105332$ [$4095, 418, 1003$] $2811954$ $2812663$ [$8191, 7580, 95$] $827943$ $828040$ [$16383, 14598, 261$] $2028480$ $2028889$ [$32767, 16412, 2631$] $24529993$ $26599523$
 BCH code $[n, k, d]$ (variant 1) Number of errors to be decoded $0$ error $1$ error [$766, 256, 115$] $103466$ $103436$ [$796, 256, 121$] $105349$ $105332$ [$4095, 418, 1003$] $2811954$ $2812663$ [$8191, 7580, 95$] $827943$ $828040$ [$16383, 14598, 261$] $2028480$ $2028889$ [$32767, 16412, 2631$] $24529993$ $26599523$
The mean of the decoding execution time (in CPU cycles) of various BCH codes for errors of weight $0$ and $1$ with field multiplication implemented via $\textsf{pclmulqdq}$ instruction (variant 2)
 BCH code $[n, k, d]$ (variant 2) Number of errors to be decoded $0$ error $1$ error [$766, 256, 115$] $128391$ [$796, 256, 121$] $133984$ $134056$ [$4095, 418, 1003$] $5110719$ $5110691$ [$8191, 7580, 95$] $1252564$ $1252542$ [$16383, 14598, 261$] $3397224$ $3396703$ [$32767, 16412, 2631$] $19205561$ $19205407$
 BCH code $[n, k, d]$ (variant 2) Number of errors to be decoded $0$ error $1$ error [$766, 256, 115$] $128391$ [$796, 256, 121$] $133984$ $134056$ [$4095, 418, 1003$] $5110719$ $5110691$ [$8191, 7580, 95$] $1252564$ $1252542$ [$16383, 14598, 261$] $3397224$ $3396703$ [$32767, 16412, 2631$] $19205561$ $19205407$
Decoding of some BCH codes with multiplication by tables
 BCH code $[n, k, d]$ Running time (in CPU cycles) LuT Syndromes ELP Roots Total $[766, 256, 115]$ 0 34240 30089 26778 91873 $[796, 256, 121]$ 0 34646 33359 27086 95861 $[4095, 418, 1003]$ 82491 291827 2145899 187004 2711521 $[8191, 7580, 95]$ 124587 278191 23216 186407 616569 $[16383, 14598, 261]$ 245850 789651 166062 552630 1760773 $[32767, 16412, 2631]$ 503337 2531258 17361393 1786677 22217535
 BCH code $[n, k, d]$ Running time (in CPU cycles) LuT Syndromes ELP Roots Total $[766, 256, 115]$ 0 34240 30089 26778 91873 $[796, 256, 121]$ 0 34646 33359 27086 95861 $[4095, 418, 1003]$ 82491 291827 2145899 187004 2711521 $[8191, 7580, 95]$ 124587 278191 23216 186407 616569 $[16383, 14598, 261]$ 245850 789651 166062 552630 1760773 $[32767, 16412, 2631]$ 503337 2531258 17361393 1786677 22217535
Decoding of some BCH codes with multiplication by $\textsf{pclmulqdq}$
 BCH code $[n, k, d]$ Running time (in CPU cycles) LuT Syndromes ELP Roots Total $[766, 256, 115]$ 0 42799 50735 34017 128226 $[796, 256, 121]$ 0 43560 55562 34404 134157 $[4095, 418, 1003]$ 96997 474817 4585893 321102 5482880 $[8191, 7580, 95]$ 134176 443016 61288 311542 953739 $[16383, 14598, 261]$ 260450 1501411 474177 1106680 3352090 $[32767, 16412, 2631]$ 484200 2143567 14832791 1514189 18996691
 BCH code $[n, k, d]$ Running time (in CPU cycles) LuT Syndromes ELP Roots Total $[766, 256, 115]$ 0 42799 50735 34017 128226 $[796, 256, 121]$ 0 43560 55562 34404 134157 $[4095, 418, 1003]$ 96997 474817 4585893 321102 5482880 $[8191, 7580, 95]$ 134176 443016 61288 311542 953739 $[16383, 14598, 261]$ 260450 1501411 474177 1106680 3352090 $[32767, 16412, 2631]$ 484200 2143567 14832791 1514189 18996691

2020 Impact Factor: 0.935