
-
Previous Article
The conorm code of an AG-code
- AMC Home
- This Issue
-
Next Article
Reversible $ G $-codes over the ring $ {\mathcal{F}}_{j,k} $ with applications to DNA codes
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 |
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.
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.
|
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. |
[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.
|


Instance | 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 | 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 |
Number of repetition of each request | |||||
Percentage of failed attacks |
Number of repetition of each request | |||||
Percentage of failed attacks |
Complexity upper bound | Requests | |||||
Oracle $\textsf{Init}$ ( |
||||||
First iteration | ||||||
Second iteration - phase 1 | ||||||
Second iteration - phase 2 | ||||||
Total |
Complexity upper bound | Requests | |||||
Oracle $\textsf{Init}$ ( |
||||||
First iteration | ||||||
Second iteration - phase 1 | ||||||
Second iteration - phase 2 | ||||||
Total |
HQC.$\textsf{Decaps}$ | Overhead | ||
Original BCH | Constant time BCH | ||
HQC-128-1 | |||
HQC-192-1 | |||
HQC-192-2 | |||
HQC-256-1 | |||
HQC-256-2 | |||
HQC-256-3 |
HQC.$\textsf{Decaps}$ | Overhead | ||
Original BCH | Constant time BCH | ||
HQC-128-1 | |||
HQC-192-1 | |||
HQC-192-2 | |||
HQC-256-1 | |||
HQC-256-2 | |||
HQC-256-3 |
BCH code |
Number of errors to be decoded | |
[ |
||
[ |
||
[ |
||
[ |
||
[ |
||
[ |
BCH code |
Number of errors to be decoded | |
[ |
||
[ |
||
[ |
||
[ |
||
[ |
||
[ |
BCH code |
Number of errors to be decoded | |
[ |
||
[ |
||
[ |
||
[ |
||
[ |
||
[ |
BCH code |
Number of errors to be decoded | |
[ |
||
[ |
||
[ |
||
[ |
||
[ |
||
[ |
BCH code |
Running time (in CPU cycles) | ||||
LuT | Syndromes | ELP | Roots | Total | |
|
0 | 34240 | 30089 | 26778 | 91873 |
|
0 | 34646 | 33359 | 27086 | 95861 |
|
82491 | 291827 | 2145899 | 187004 | 2711521 |
|
124587 | 278191 | 23216 | 186407 | 616569 |
|
245850 | 789651 | 166062 | 552630 | 1760773 |
|
503337 | 2531258 | 17361393 | 1786677 | 22217535 |
BCH code |
Running time (in CPU cycles) | ||||
LuT | Syndromes | ELP | Roots | Total | |
|
0 | 34240 | 30089 | 26778 | 91873 |
|
0 | 34646 | 33359 | 27086 | 95861 |
|
82491 | 291827 | 2145899 | 187004 | 2711521 |
|
124587 | 278191 | 23216 | 186407 | 616569 |
|
245850 | 789651 | 166062 | 552630 | 1760773 |
|
503337 | 2531258 | 17361393 | 1786677 | 22217535 |
BCH code |
Running time (in CPU cycles) | ||||
LuT | Syndromes | ELP | Roots | Total | |
|
0 | 42799 | 50735 | 34017 | 128226 |
|
0 | 43560 | 55562 | 34404 | 134157 |
|
96997 | 474817 | 4585893 | 321102 | 5482880 |
|
134176 | 443016 | 61288 | 311542 | 953739 |
|
260450 | 1501411 | 474177 | 1106680 | 3352090 |
|
484200 | 2143567 | 14832791 | 1514189 | 18996691 |
BCH code |
Running time (in CPU cycles) | ||||
LuT | Syndromes | ELP | Roots | Total | |
|
0 | 42799 | 50735 | 34017 | 128226 |
|
0 | 43560 | 55562 | 34404 | 134157 |
|
96997 | 474817 | 4585893 | 321102 | 5482880 |
|
134176 | 443016 | 61288 | 311542 | 953739 |
|
260450 | 1501411 | 474177 | 1106680 | 3352090 |
|
484200 | 2143567 | 14832791 | 1514189 | 18996691 |
[1] |
Angelot Behajaina. On BCH split metacyclic codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021045 |
[2] |
Chandan Dey, Sumit Kumar Pandey, Tapabrata Roy, Santanu Sarkar. Differential faultt attack on DEFAULT. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022035 |
[3] |
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 |
[4] |
Xinmei Huang, Qin Yue, Yansheng Wu, Xiaoping Shi. Ternary Primitive LCD BCH codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021014 |
[5] |
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 |
[6] |
Yacine Chitour, Benedetto Piccoli. Traffic circles and timing of traffic lights for cars flow. Discrete and Continuous Dynamical Systems - B, 2005, 5 (3) : 599-630. doi: 10.3934/dcdsb.2005.5.599 |
[7] |
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 |
[8] |
Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 |
[9] |
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 and Continuous Dynamical Systems - B, 2013, 18 (1) : 173-183. doi: 10.3934/dcdsb.2013.18.173 |
[10] |
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 |
[11] |
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 |
[12] |
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 |
[13] |
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 |
[14] |
Violetta Weger, Karan Khathuria, Anna-Lena Horlemann, Massimo Battaglioni, Paolo Santini, Edoardo Persichetti. On the hardness of the Lee syndrome decoding problem. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022029 |
[15] |
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 |
[16] |
Per Danzl, Ali Nabi, Jeff Moehlis. Charge-balanced spike timing control for phase models of spiking neurons. Discrete and Continuous Dynamical Systems, 2010, 28 (4) : 1413-1435. doi: 10.3934/dcds.2010.28.1413 |
[17] |
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 |
[18] |
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 and Continuous Dynamical Systems - S, 2021, 14 (7) : 2163-2181. doi: 10.3934/dcdss.2021055 |
[19] |
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 |
[20] |
Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]