# American Institute of Mathematical Sciences

doi: 10.3934/amc.2020126

## 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 Published  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:
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
 [1] Lisa Hernandez Lucas. Properties of sets of Subspaces with Constant Intersection Dimension. Advances in Mathematics of Communications, 2021, 15 (1) : 191-206. doi: 10.3934/amc.2020052 [2] Jintai Ding, Zheng Zhang, Joshua Deaton. The singularity attack to the multivariate signature scheme HIMQ-3. Advances in Mathematics of Communications, 2021, 15 (1) : 65-72. doi: 10.3934/amc.2020043 [3] Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020120 [4] Sören Bartels, Jakob Keck. Adaptive time stepping in elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 71-88. doi: 10.3934/dcdss.2020323 [5] Simone Göttlich, Elisa Iacomini, Thomas Jung. Properties of the LWR model with time delay. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020032 [6] Emre Esentürk, Juan Velazquez. Large time behavior of exchange-driven growth. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 747-775. doi: 10.3934/dcds.2020299 [7] Xu Zhang, Chuang Zheng, Enrique Zuazua. Time discrete wave equations: Boundary observability and control. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 571-604. doi: 10.3934/dcds.2009.23.571 [8] Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170 [9] Qiwei Wu, Liping Luan. Large-time behavior of solutions to unipolar Euler-Poisson equations with time-dependent damping. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021003 [10] Olivier Ley, Erwin Topp, Miguel Yangari. Some results for the large time behavior of Hamilton-Jacobi equations with Caputo time derivative. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021007 [11] Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046 [12] Serena Dipierro, Benedetta Pellacci, Enrico Valdinoci, Gianmaria Verzini. Time-fractional equations with reaction terms: Fundamental solutions and asymptotics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 257-275. doi: 10.3934/dcds.2020137 [13] Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336 [14] Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339 [15] Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444 [16] Veena Goswami, Gopinath Panda. Optimal customer behavior in observable and unobservable discrete-time queues. Journal of Industrial & Management Optimization, 2021, 17 (1) : 299-316. doi: 10.3934/jimo.2019112 [17] Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113 [18] Zhimin Li, Tailei Zhang, Xiuqing Li. Threshold dynamics of stochastic models with time delays: A case study for Yunnan, China. Electronic Research Archive, 2021, 29 (1) : 1661-1679. doi: 10.3934/era.2020085 [19] Rong Wang, Yihong Du. Long-time dynamics of a diffusive epidemic model with free boundaries. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020360 [20] Dong-Ho Tsai, Chia-Hsing Nien. On space-time periodic solutions of the one-dimensional heat equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3997-4017. doi: 10.3934/dcds.2020037

2019 Impact Factor: 0.734