
-
Previous Article
Locally repairable codes with high availability based on generalised quadrangles
- AMC Home
- This Issue
-
Next Article
Additive and linear conjucyclic codes over $ {\mathbb{F}}_4 $
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. 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. |
[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. 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. |
[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. Google Scholar |
[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)., 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. |
[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. |
[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. 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. |
[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. Google Scholar |
[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)., 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. |
[19] |
Y. Xu, Implementation of Berlekamp-Massey algorithm without inversion, IEE Proceedings I-Communications, Speech and Vision, 138 (1991), 138-140. Google Scholar |


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] |
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
Tools
Metrics
Other articles
by authors
[Back to Top]