# 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 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:
 [1] C. Aguilar-Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, E. Persichetti and G. Zémor, Hamming Quasi-Cyclic (HQC), 2017. Google Scholar [2] C. Aguilar-Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit and G. Zémor, Rank Quasi-Cyclic (RQC), 2017. Google Scholar [3] C. Aguilar-Melchor, O. Blazy, J.-C. Deneuville, P. Gaborit and G. Zémor, Efficient encryption from random quasi-cyclic codes, IEEE Transactions on Information Theory, 64 (2018), 3927-3943.  doi: 10.1109/TIT.2018.2804444.  Google Scholar [4] S. Bettaieb, L. Bidoux, P. Gaborit and E. Marcatel, Preventing timing attacks against RQC using constant time decoding of Gabidulin codes, in International Conference on Post-Quantum Cryptography, Springer, (2019), 371–386. doi: 10.1007/978-3-030-25510-7_20.  Google Scholar [5] E. R. Berlekamp, Non-binary BCH Decoding, Technical report, North Carolina State University. Dept. of Statistics, 1966. Google Scholar [6] D. J. Bernstein, T. Chou and P. Schwabe, Mcbits: Fast constant-time code-based cryptography, in International Workshop on Cryptographic Hardware and Embedded Systems, Springer, (2013), 250–272. doi: 10.1007/978-3-642-40349-1_15.  Google Scholar [7] D. J. Bernstein and B-Y. Yang, Fast constant-time gcd computation and modular inversion, in IACR Transactions on Cryptographic Hardware and Embedded Systems, (2019), 340–398. doi: 10.46586/tches.v2019.i3.340-398.  Google Scholar [8] T. Chou, McBits revisited, in International Conference on Cryptographic Hardware and Embedded Systems, Springer, (2017), 213–231. doi: 10.1007/978-3-319-66787-4_11.  Google Scholar [9] R. Chandra. Bose and D. K. Ray-Chaudhuri, On a class of error correcting binary group codes, Information and Control, 3 (1960), 68-79.  doi: 10.1016/S0019-9958(60)90287-4.  Google Scholar [10] J.-P. D'Anvers, F. Vercauteren and Ingrid Verbauwhede, On the impact of decryption failures on the security of LWE/LWR based schemes, IACR Cryptology ePrint Archive, (2018), 1089. Google Scholar [11] È. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21 (1985), 3-16.   Google Scholar [12] S. Gao and T. Mateer, Additive fast fourier transforms over finite fields, IEEE Transactions on Information Theory, 56 (2010), 6265-6272.  doi: 10.1109/TIT.2010.2079016.  Google Scholar [13] A. Hocquenghem, Codes correcteurs d'erreurs, Chiffres, 2 (1959), 147-156.   Google Scholar [14] D. Hofheinz, K. Hövelmanns and E. Kiltz, A modular analysis of the Fujisaki-Okamoto transformation, in Theory of Cryptography Conference, Springer, (2017), 341–371.  Google Scholar [15] L. L. Joiner and J. J. Komo, Decoding binary BCH codes, in Southeastcon '95, 1995. doi: 10.1109/SECON.1995.513059.  Google Scholar [16] S. Lin and D. J. Costello, in Error control coding, Prentice Hall Englewood Cliffs, (2004)., Google Scholar [17] X. Lu, Y. Liu, Z. Zhang, D. Jia, H. Xue, J. He, B. Li, K. Wang, Z. Liu and H. Yang, LAC: Practical Ring-LWE based Public-Key Encryption with Byte-Level Modulus, IACR Cryptology ePrint Archive, (2018), 1009. Google Scholar [18] M. Walters and S. Sinha Roy, Constant-time BCH Error-Correcting Code, in 2020 IEEE International Symposium on Circuits and Systems (ISCAS), Sevilla, (2020), 1–5. doi: 10.1109/ISCAS45731.2020.9180846.  Google Scholar [19] Y. Xu, Implementation of Berlekamp-Massey algorithm without inversion, IEE Proceedings I-Communications, Speech and Vision, 138 (1991), 138-140.   Google Scholar

show all references

##### References:
 [1] C. Aguilar-Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, E. Persichetti and G. Zémor, Hamming Quasi-Cyclic (HQC), 2017. Google Scholar [2] C. Aguilar-Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit and G. Zémor, Rank Quasi-Cyclic (RQC), 2017. Google Scholar [3] C. Aguilar-Melchor, O. Blazy, J.-C. Deneuville, P. Gaborit and G. Zémor, Efficient encryption from random quasi-cyclic codes, IEEE Transactions on Information Theory, 64 (2018), 3927-3943.  doi: 10.1109/TIT.2018.2804444.  Google Scholar [4] S. Bettaieb, L. Bidoux, P. Gaborit and E. Marcatel, Preventing timing attacks against RQC using constant time decoding of Gabidulin codes, in International Conference on Post-Quantum Cryptography, Springer, (2019), 371–386. doi: 10.1007/978-3-030-25510-7_20.  Google Scholar [5] E. R. Berlekamp, Non-binary BCH Decoding, Technical report, North Carolina State University. Dept. of Statistics, 1966. Google Scholar [6] D. J. Bernstein, T. Chou and P. Schwabe, Mcbits: Fast constant-time code-based cryptography, in International Workshop on Cryptographic Hardware and Embedded Systems, Springer, (2013), 250–272. doi: 10.1007/978-3-642-40349-1_15.  Google Scholar [7] D. J. Bernstein and B-Y. Yang, Fast constant-time gcd computation and modular inversion, in IACR Transactions on Cryptographic Hardware and Embedded Systems, (2019), 340–398. doi: 10.46586/tches.v2019.i3.340-398.  Google Scholar [8] T. Chou, McBits revisited, in International Conference on Cryptographic Hardware and Embedded Systems, Springer, (2017), 213–231. doi: 10.1007/978-3-319-66787-4_11.  Google Scholar [9] R. Chandra. Bose and D. K. Ray-Chaudhuri, On a class of error correcting binary group codes, Information and Control, 3 (1960), 68-79.  doi: 10.1016/S0019-9958(60)90287-4.  Google Scholar [10] J.-P. D'Anvers, F. Vercauteren and Ingrid Verbauwhede, On the impact of decryption failures on the security of LWE/LWR based schemes, IACR Cryptology ePrint Archive, (2018), 1089. Google Scholar [11] È. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21 (1985), 3-16.   Google Scholar [12] S. Gao and T. Mateer, Additive fast fourier transforms over finite fields, IEEE Transactions on Information Theory, 56 (2010), 6265-6272.  doi: 10.1109/TIT.2010.2079016.  Google Scholar [13] A. Hocquenghem, Codes correcteurs d'erreurs, Chiffres, 2 (1959), 147-156.   Google Scholar [14] D. Hofheinz, K. Hövelmanns and E. Kiltz, A modular analysis of the Fujisaki-Okamoto transformation, in Theory of Cryptography Conference, Springer, (2017), 341–371.  Google Scholar [15] L. L. Joiner and J. J. Komo, Decoding binary BCH codes, in Southeastcon '95, 1995. doi: 10.1109/SECON.1995.513059.  Google Scholar [16] S. Lin and D. J. Costello, in Error control coding, Prentice Hall Englewood Cliffs, (2004)., Google Scholar [17] X. Lu, Y. Liu, Z. Zhang, D. Jia, H. Xue, J. He, B. Li, K. Wang, Z. Liu and H. Yang, LAC: Practical Ring-LWE based Public-Key Encryption with Byte-Level Modulus, IACR Cryptology ePrint Archive, (2018), 1009. Google Scholar [18] M. Walters and S. Sinha Roy, Constant-time BCH Error-Correcting Code, in 2020 IEEE International Symposium on Circuits and Systems (ISCAS), Sevilla, (2020), 1–5. doi: 10.1109/ISCAS45731.2020.9180846.  Google Scholar [19] Y. Xu, Implementation of Berlekamp-Massey algorithm without inversion, IEE Proceedings I-Communications, Speech and Vision, 138 (1991), 138-140.   Google Scholar
]">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
 [1] José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018 [2] Xinmei Huang, Qin Yue, Yansheng Wu, Xiaoping Shi. Ternary Primitive LCD BCH codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021014 [3] Edoardo Beretta, Dimitri Breda. An SEIR epidemic model with constant latency time and infectious period. Mathematical Biosciences & Engineering, 2011, 8 (4) : 931-952. doi: 10.3934/mbe.2011.8.931 [4] Yacine Chitour, Benedetto Piccoli. Traffic circles and timing of traffic lights for cars flow. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 599-630. doi: 10.3934/dcdsb.2005.5.599 [5] Haode Yan, Hao Liu, Chengju Li, Shudi Yang. Parameters of LCD BCH codes with two lengths. Advances in Mathematics of Communications, 2018, 12 (3) : 579-594. doi: 10.3934/amc.2018034 [6] Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 [7] Yoshiaki Muroya, Yoichi Enatsu, Huaixing Li. A note on the global stability of an SEIR epidemic model with constant latency time and infectious period. Discrete & Continuous Dynamical Systems - B, 2013, 18 (1) : 173-183. doi: 10.3934/dcdsb.2013.18.173 [8] Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052 [9] Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443 [10] Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505 [11] Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433 [12] Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83 [13] Per Danzl, Ali Nabi, Jeff Moehlis. Charge-balanced spike timing control for phase models of spiking neurons. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1413-1435. doi: 10.3934/dcds.2010.28.1413 [14] Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169 [15] Anouar El Harrak, Amal Bergam, Tri Nguyen-Huu, Pierre Auger, Rachid Mchich. Application of aggregation of variables methods to a class of two-time reaction-diffusion-chemotaxis models of spatially structured populations with constant diffusion. Discrete & Continuous Dynamical Systems - S, 2021, 14 (7) : 2163-2181. doi: 10.3934/dcdss.2021055 [16] Jingni Guo, Junxiang Xu, Zhenggang He, Wei Liao. Research on cascading failure modes and attack strategies of multimodal transport network. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2020159 [17] Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2020, 14 (4) : 573-577. doi: 10.3934/amc.2020030 [18] 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 [19] Jintai Ding, Joshua Deaton, Kurt Schmidt. Giophantus distinguishing attack is a low dimensional learning with errors problem. Advances in Mathematics of Communications, 2020, 14 (1) : 171-175. doi: 10.3934/amc.2020014 [20] Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385

2020 Impact Factor: 0.935