A practicable timing attack against HQC and its countermeasure

Guillaume Wafo-Tapa; Slim Bettaieb; Loïc Bidoux; Philippe Gaborit; Etienne Marcatel

doi:10.3934/amc.2020126

Article Contents

2022, Volume 16, Issue 3: 621-642. Doi: 10.3934/amc.2020126

This issue Previous Article On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators Next Article On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $

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: July 31, 2019

Revised: December 31, 2019

Early access: December 2020

Published: August 2022

Abstract Full Text(HTML) Figure(3) / Table(8) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 11T71, 94B35; Secondary: 94B05.

Citation:

Full Text(HTML)

Figure 1. Description of $\textsf{HQC.PKE}$ [1]

Download: Full-size image PowerPoint slide

Figure 2. Decoding execution times (in CPU cycles) of various BCH codes for different error weights with field mutliplication implemented by lookup tables (variant 1)

Download: Full-size image PowerPoint slide

Figure 3. Decoding execution times (in CPU cycles) of various BCH codes for different error weights with field multiplication implemented via $\textsf{pclmulqdq}$ instruction (variant 2)

Download: Full-size image PowerPoint slide

Table 1. 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

| Show Table

DownLoad: CSV

Table 2. 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\% $

| Show Table

DownLoad: CSV

Table 3. 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 $

| Show Table

DownLoad: CSV

Table 4. 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	Overhead
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\% $

| Show Table

DownLoad: CSV

Table 5. 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
BCH code $ [n, k, d] $ (variant 1)	$ 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 $

| Show Table

DownLoad: CSV

Table 6. 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
BCH code $ [n, k, d] $ (variant 2)	$ 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 $

| Show Table

DownLoad: CSV

Table 7. Decoding of some BCH codes with multiplication by tables

BCH code $ [n, k, d] $	Running time (in CPU cycles)
BCH code $ [n, k, d] $	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

| Show Table

DownLoad: CSV

Table 8. Decoding of some BCH codes with multiplication by $\textsf{pclmulqdq}$

BCH code $ [n, k, d] $	Running time (in CPU cycles)
BCH code $ [n, k, d] $	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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[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.
[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.
[5]	E. R. Berlekamp, Non-binary BCH Decoding, Technical report, North Carolina State University. Dept. of Statistics, 1966.
[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.
[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.
[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.
[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.
[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.
[11]	È. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21 (1985), 3-16.
[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.
[13]	A. Hocquenghem, Codes correcteurs d'erreurs, Chiffres, 2 (1959), 147-156.
[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.
[15]	L. L. Joiner and J. J. Komo, Decoding binary BCH codes, in Southeastcon '95, 1995. doi: 10.1109/SECON.1995.513059.
[16]	S. Lin and D. J. Costello, in Error control coding, Prentice Hall Englewood Cliffs, (2004).,
[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.
[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.
[19]	Y. Xu, Implementation of Berlekamp-Massey algorithm without inversion, IEE Proceedings I-Communications, Speech and Vision, 138 (1991), 138-140.