### Message-recovery Laser Fault Injection Attack on the Classic McEliece Cryptosystem

Pierre-Louis Cayrel, Brice Colombier, Vlad-Florin Dragoi, Alexandre Menu, and Lilian Bossuet

##### Abstract

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, \textit{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 \textit{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.

Available format(s)
Category
Implementation
Publication info
Published by the IACR in EUROCRYPT 2021
Keywords
code-based cryptographysyndrome decoding problemlaser fault injection
Contact author(s)
pierre louis cayrel @ univ-st-etienne fr
b colombier @ univ-st-etienne fr
vlad dragoi @ uav ro
History
2021-02-26: revised
See all versions
Short URL
https://ia.cr/2020/900

CC BY

BibTeX

@misc{cryptoeprint:2020/900,
author = {Pierre-Louis Cayrel and Brice Colombier and Vlad-Florin Dragoi and Alexandre Menu and Lilian Bossuet},
title = {Message-recovery Laser Fault Injection Attack on the Classic McEliece Cryptosystem},
howpublished = {Cryptology ePrint Archive, Paper 2020/900},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/900}},
url = {https://eprint.iacr.org/2020/900}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.