Paper 2020/900
Message-recovery Laser Fault Injection Attack on Code-based Cryptosystems
Pierre-Louis Cayrel and Brice Colombier and Vlad-Florin Dragoi and Alexandre Menu and Lilian Bossuet
Abstract
Code-based public-key cryptosystems are promising candidates for standardisation 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 force 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 all the code-based proposals to the NIST Post-Quantum Cryptography standardisation challenge. We perform our attacks on worst-case scenarios, i.e. random binary codes, and retrieve the initial message within minutes on a desktop computer. When considering parameters of the code-based submissions to the NIST PQC standardisation challenge, all of them can be attacked in less than three minutes.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- 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
- 2020-07-18: received
- See all versions
- Short URL
- https://ia.cr/2020/900
- License
-
CC BY