×

Message-recovery laser fault injection attack on the classic McEliece cryptosystem. (English) Zbl 1479.94141

Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2021. 40th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, October 17–21, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 12697, 438-467 (2021).
Summary: Code-based public-key cryptosystems are promising candidates for standardization as quantum-resistant public-key cryptographic algorithms. Their security is based on the hardness of the syndrome decoding problem. Computing the syndrome in a finite field, usually \(\mathbb{F}_2 \), guarantees the security of the constructions. We show in this article that the problem becomes considerably easier to solve if the syndrome is computed in \(\mathbb{N}\) instead. By means of laser fault injection, we illustrate how to compute the matrix-vector product in \(\mathbb{N}\) by corrupting specific instructions, and validate it experimentally. To solve the syndrome decoding problem in \(\mathbb{N} \), we propose a reduction to an integer linear programming problem. We leverage the computational efficiency of linear programming solvers to obtain real-time message recovery attacks against the code-based proposal to the NIST Post-Quantum Cryptography standardization challenge. We perform our attacks in the worst-case scenario, i.e. considering random binary codes, and retrieve the initial message within minutes on a desktop computer.
Our attack targets the reference implementation of the Niederreiter cryptosystem in the NIST PQC competition finalist Classic McEliece and is practically feasible for all proposed parameters sets of this submission. For example, for the 256-bit security parameters sets, we successfully recover the message in a couple of seconds on a desktop computer Finally, we highlight the fact that the attack is still possible if only a fraction of the syndrome entries are faulty. This makes the attack feasible even though the fault injection does not have perfect repeatability and reduces the computational complexity of the attack, making it even more practical overall.
For the entire collection see [Zbl 1475.94011].

MSC:

94A60 Cryptography
81P94 Quantum cryptography (quantum-theoretic aspects)
90C05 Linear programming
90C10 Integer programming

Software:

McEliece
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albrecht, M.R., et al.: Classic McEliece, submission to the NIST post quantum standardization process (November 2017)
[2] Andersen, E.D., Andersen, K.D.: The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm. In: Frenk, H., Roos, K., Terlaky, T., Zhang, S. (eds.) High performance optimization, vol. 33, pp. 197-232. Springer, Boston (2000) doi:10.1007/978-1-4757-3216-0_8 · Zbl 1028.90022
[3] Aragon, N., et al.: BIKE: Bit Flipping Key Encapsulation, submission to the NIST post quantum standardization process (December 2017)
[4] Aragon, N., et al.: Rollo (merger of Rank-Ouroboros, LAKE and LOCKER). Second round submission to the NIST post-quantum cryptography call (2020)
[5] Baldi, M.; Barenghi, A.; Chiaraluce, F.; Pelosi, G.; Santini, P.; Lange, T.; Steinwandt, R., LEDAkem: a post-quantum key encapsulation mechanism based on QC-LDPC codes, Post-Quantum Cryptography, 3-24 (2018), Cham: Springer, Cham · Zbl 1425.94046 · doi:10.1007/978-3-319-79063-3_1
[6] Barenghi, A., Bertoni, G.M., Breveglieri, L., Pellicioli, M., Pelosi, G.: Fault attack on AES with single-bit induced faults. In: International Conference on Information Assurance and Security, pp. 167-172. Atlanta, IEEE (August 2010)
[7] Becker, A.; Joux, A.; May, A.; Meurer, A.; Pointcheval, D.; Johansson, T., Decoding random binary linear codes in \(2^{n/20}\): how 1+1=0 improves information set decoding, Advances in Cryptology, 520-536 (2012), Heidelberg: Springer, Heidelberg · Zbl 1291.94206 · doi:10.1007/978-3-642-29011-4_31
[8] Berlekamp, E.R., McEliece, R.J., van Tilborg, H.C.A.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theor. 24(3), 384-386 (1978) · Zbl 0377.94018
[9] Bernstein, D.J.: Post-quantum cryptography. In: van Tilborg, H.C.A., Jajodia, S. (eds.) Encyclopedia of Cryptography and Security, 2nd edn., pp. 949-950. Springer, New York (2011). doi:10.1007/978-1-4419-5906-5_386
[10] Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Organisation, Athena Scientific Optimization and Computation Series, vol. 6. Athena Scientific, Belmont (1997)
[11] Borghoff, J.: Mixed-integer linear programming in the analysis of trivium and ktantan. IACR Cryptology ePrint Archive 2012, 676 (2012). http://eprint.iacr.org/2012/676
[12] Borghoff, J.; Knudsen, LR; Stolpe, M.; Parker, MG, Bivium as a mixed-integer linear programming problem, Cryptography and Coding, 133-152 (2009), Heidelberg: Springer, Heidelberg · Zbl 1234.94031 · doi:10.1007/978-3-642-10868-6_9
[13] Bukasa, S.K., Lashermes, R., Lanet, J., Legay, A.: Let’s shock our IoT’s heart: ARMv7-M under (fault) attacks. In: Doerr, S., Fischer, M., Schrittwieser, S., Herrmann, D. (eds.) International Conference on Availability, Reliability and Security, pp. 33:1-33:6. ACM, Hamburg, Germany (August 2018)
[14] Colombier, B., Menu, A., Dutertre, J.M., Moëllic, P.A., Rigaud, J.B., Danger, J.L.: Laser-induced single-bit faults in flash memory: Instructions corruption on a 32-bit microcontroller. In: IEEE International Symposium on Hardware Oriented Security and Trust, pp. 1-10. McLean, VA, USA (May 2019)
[15] Dantzig, GB, Maximization of a linear function of variables subject to linear inequalities, Activity Anal. Prod. Allocation, 13, 339-347 (1951) · Zbl 0045.09802
[16] Diffie, W.; Hellman, ME, New directions in cryptography, IEEE Trans. Inf. Theory, 22, 6, 644-654 (1976) · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638
[17] Dragoi, VF; Cayrel, PL; Colombier, B.; Bucerzan, D.; Hoara, S., Solving a modified syndrome decoding problem using integer programming, Int. J. Comput. Commun. Control, 15, 5, 1-9 (2020) · doi:10.15837/ijccc.2020.5.3920
[18] Dutertre, J-M; Riom, T.; Potin, O.; Rigaud, J-B; Askarov, A.; Hansen, RR; Rafnsson, W., Experimental analysis of the laser-induced instruction skip fault model, Secure IT Systems, 221-237 (2019), Cham: Springer, Cham · doi:10.1007/978-3-030-35055-0_14
[19] Feldman, J.: Decoding error-correcting codes via linear programming. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, USA (2003)
[20] Feldman, J.; Wainwright, MJ; Karger, DR, Using linear programming to decode binary linear codes, IEEE Trans. Inf. Theory, 51, 3, 954-972 (2005) · Zbl 1234.94086 · doi:10.1109/TIT.2004.842696
[21] Giraud, C.; Dobbertin, H.; Rijmen, V.; Sowa, A., DFA on AES, Advanced Encryption Standard, 27-41 (2005), Heidelberg: Springer, Heidelberg · Zbl 1117.94319 · doi:10.1007/11506447_4
[22] Helmling, M.; Ruzika, S.; Tanatmis, A., Mathematical programming decoding of binary linear codes: theory and algorithms, IEEE Trans. Inf. Theory, 58, 7, 4753-4769 (2012) · Zbl 1365.94592 · doi:10.1109/TIT.2012.2191697
[23] Johnson, EL; Nemhauser, GL; Savelsbergh, MWP, Progress in linear programming-based algorithms for integer programming: an exposition, INFORMS J. Comput., 12, 1, 2-23 (2000) · Zbl 1052.90048 · doi:10.1287/ijoc.12.1.2.11900
[24] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 4, 373-396 (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150
[25] Klee, V.; Minty, GJ, How good is the simplex algorithm, Inequalities, 3, 3, 159-175 (1972) · Zbl 0297.90047
[26] Koblitz, N., Elliptic curve cryptosystems, Math. Comput., 48, 177, 203-209 (1987) · Zbl 0622.94015 · doi:10.1090/S0025-5718-1987-0866109-5
[27] Lahr, N.; Niederhagen, R.; Petri, R.; Samardjiska, S.; Moriai, S.; Wang, H., Side channel information set decoding using iterative chunking, Advances in Cryptology - ASIACRYPT 2020, 881-910 (2020), Cham: Springer, Cham · Zbl 1511.94123 · doi:10.1007/978-3-030-64837-4_29
[28] Lee, PJ; Brickell, EF; Barstow, D.; Barstow, D., An observation on the security of McEliece’s public-key cryptosystem, Advances in Cryptology, 275-280 (1988), Heidelberg: Springer, Heidelberg · Zbl 0655.94006 · doi:10.1007/3-540-45961-8_25
[29] Lee, Y.T., Sidford, A.: Efficient inverse maintenance and faster algorithms for linear programming. In: Guruswami, V. (ed.) IEEE Annual Symposium on Foundations of Computer Science, pp. 230-249. IEEE Computer Society, Berkeley, CA, USA (October 2015)
[30] Leon, JS, A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Trans. Inf. Theory, 34, 5, 1354-1359 (1988) · Zbl 0666.94017 · doi:10.1109/18.21270
[31] Liao, H., Gebotys, C.H.: Methodology for EM fault injection: charge-based fault model. In: Teich, J., Fummi, F. (eds.) Design, Automation & Test in Europe Conference & Exhibition, pp. 256-259. IEEE, Florence, Italy (March 2019)
[32] Luppold, A., Oehlert, D., Falk, H.: Evaluating the performance of solvers for integer-linear programming. Technical Report, Hamburg University of Technology (2018). doi:10.15480/882.1839, https://tore.tuhh.de/handle/11420/1842
[33] MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes, vol. 16. Elsevier, New York (1977) · Zbl 0369.94008
[34] May, A.; Meurer, A.; Thomae, E.; Lee, DH; Wang, X., Decoding random linear codes in \(\tilde{\cal{O}}(2^{0.054n})\), Advances in Cryptology - ASIACRYPT 2011, 107-124 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94055 · doi:10.1007/978-3-642-25385-0_6
[35] May, A.; Ozerov, I.; Oswald, E.; Fischlin, M., On computing nearest neighbors with applications to decoding of binary linear codes, Advances in Cryptology - EUROCRYPT 2015, 203-228 (2015), Heidelberg: Springer, Heidelberg · Zbl 1365.94597 · doi:10.1007/978-3-662-46800-5_9
[36] McEliece, R.J.: A public-key system based on algebraic. Coding Theory 4244, 114-116 (1978)
[37] Megiddo, N., On finding primal- and dual-optimal bases, INFORMS J. Comput., 3, 1, 63-65 (1991) · Zbl 0755.90056 · doi:10.1287/ijoc.3.1.63
[38] Menu, A., Dutertre, J., Rigaud, J., Colombier, B., Moëllic, P., Danger, J.: Single-bit laser fault model in NOR flash memories: analysis and exploitation. In: Workshop on Fault Detection and Tolerance in Cryptography, pp. 41-48. IEEE, Milan, Italy (September 2020)
[39] Miller, VS; Williams, HC, Use of elliptic curves in cryptography, Advances in Cryptology, 417-426 (1986), Heidelberg: Springer, Heidelberg · Zbl 0589.94005 · doi:10.1007/3-540-39799-X_31
[40] Moro, N., Dehbaoui, A., Heydemann, K., Robisson, B., Encrenaz, E.: Electromagnetic fault injection: Towards a fault model on a 32-bit microcontroller. In: Fischer, W., Schmidt, J. (eds.) Workshop on Fault Diagnosis and Tolerance in Cryptography, pp. 77-88. IEEE Computer Society, Los Alamitos, CA, USA (August 2013)
[41] Mouha, N.; Wang, Q.; Gu, D.; Preneel, B.; Wu, C-K; Yung, M.; Lin, D., Differential and linear cryptanalysis using mixed-integer linear programming, Information Security and Cryptology, 57-76 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94118 · doi:10.1007/978-3-642-34704-7_5
[42] Niederreiter, H., Knapsack-type cryptosystems and algebraic coding theory, Prob. Control Inf. Theory, 15, 2, 159-166 (1986) · Zbl 0611.94007
[43] Prange, E., The use of information sets in decoding cyclic codes, IRE Trans. Inf. Theory, 8, 5, 5-9 (1962) · doi:10.1109/TIT.1962.1057777
[44] Rivest, RL; Shamir, A.; Adleman, LM, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21, 2, 120-126 (1978) · Zbl 0368.94005 · doi:10.1145/359340.359342
[45] Rivière, L., Najm, Z., Rauzy, P., Danger, J., Bringer, J., Sauvage, L.: High precision fault injections on the instruction cache of armv7-m architectures. In: IEEE International Symposium on Hardware Oriented Security and Trust. pp. 62-67. IEEE Computer Society, Washington, DC, USA (May 2015)
[46] Roth, J.; Karatsiolis, E.; Krämer, J.; Liardet, P-Y; Mentens, N., Classic McEliece implementation with low memory footprint, Smart Card Research and Advanced Applications, 34-49 (2021), Cham: Springer, Cham · doi:10.1007/978-3-030-68487-7_3
[47] Shor, PW, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 5, 1484-1509 (1997) · Zbl 1005.11065 · doi:10.1137/S0097539795293172
[48] Stern, J.; Cohen, G.; Wolfmann, J., A method for finding codewords of small weight, Coding Theory and Applications, 106-113 (1989), Heidelberg: Springer, Heidelberg · Zbl 0678.94006 · doi:10.1007/BFb0019850
[49] Taghavi, MH; Shokrollahi, A.; Siegel, PH, Efficient implementation of linear programming decoding, IEEE Trans. Inf. Theory, 57, 9, 5960-5982 (2011) · Zbl 1365.94604 · doi:10.1109/TIT.2011.2161920
[50] Tanatmis, A.; Ruzika, S.; Hamacher, HW; Punekar, M.; Kienle, F.; Wehn, N., A separation algorithm for improved lp-decoding of linear block codes, IEEE Trans. Inf. Theory, 56, 7, 3277-3289 (2010) · Zbl 1366.94763 · doi:10.1109/TIT.2010.2048489
[51] Vaidya, P.M.: Speeding-up linear programming using fast matrix multiplication (extended abstract). In: Annual Symposium on Foundations of Computer Science, pp. 332-337. IEEE Computer Society, Research Triangle Park, North Carolina, USA (October 1989)
[52] Virtanen, P., et al.: SciPy 1.0: fundamental algorithms for scientific computing in python. Nature Methods 17(3), 261-272 (2020)
[53] Vontobel, P.O.: Interior-point algorithms for linear-programming decoding. In: Information Theory and Applications Workshop, pp. 433-437. IEEE, San Diego, CA, USA (January 2008)
[54] Wadayama, T.: An LP decoding algorithm based on primal path-following interior point method. In: International Symposium on Information Theory, pp. 389-393. IEEE, Seoul, Korea (June 2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.