Punctured Syndrome Decoding Problem Efficient Side-Channel Attacks Against Classic McEliece

Vincent Grosso; Pierre-Louis Cayrel; Brice Colombier; Vlad-Florin Dragoi

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2023/308

Punctured Syndrome Decoding Problem Efficient Side-Channel Attacks Against Classic McEliece

Vincent Grosso

, Université Jean Monnet Saint-Etienne, CNRS, Institut d'Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT-ETIENNE, France

Pierre-Louis Cayrel

, Université Jean Monnet Saint-Etienne, CNRS, Institut d'Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT-ETIENNE, France

Brice Colombier

, Université Jean Monnet Saint-Etienne, CNRS, Institut d'Optique Graduate School, Laboratoire Hubert Curien UMR 5516, F-42023, SAINT-ETIENNE, France

Vlad-Florin Dragoi

, Faculty of Exact Sciences, Aurel Vlaicu University, Arad, Romania; LITIS, University of Rouen Normandie, Saint-Etienne du Rouvray, France

Abstract

Among the fourth round finalists of the NIST post-quantum cryptography standardization process for public-key encryption algorithms and key encapsulation mechanisms, three rely on hard problems from coding theory. Key encapsulation mechanisms are frequently used in hybrid cryptographic systems: a public-key algorithm for key exchange and a secret key algorithm for communication. A major point is thus the initial key exchange that is performed thanks to a key encapsulation mechanism. In this paper, we analyze side-channel vulnerabilities of the key encapsulation mechanism implemented by the Classic McEliece cryptosystem, whose security is based on the syndrome decoding problem. We use side-channel leakages to reduce the complexity of the syndrome decoding problem by reducing the length of the code considered. The columns punctured from the original code reduce the complexity of a hard problem from coding theory. This approach leads to efficient profiled side-channel attacks that recover the session key with high success rates, even in noisy scenarios.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. 14th International Workshop on Constructive Side-Channel Analysis and Secure Design, Cosade 2023, April 3 - 4, 2023, Munich, Germany
Keywords: Post-quantum cryptography Code-based cryptography Side-channel attacks
Contact author(s): vincent grosso @ univ-st-etienne fr
pierre louis cayrel @ univ-st-etienne fr
b colombier @ univ-st-etienne fr
vlad dragoi @ uav ro
History: 2023-03-03: approved; 2023-03-02: received; See all versions
Short URL: https://ia.cr/2023/308
License: CC BY

BibTeX

@misc{cryptoeprint:2023/308,
      author = {Vincent Grosso and Pierre-Louis Cayrel and Brice Colombier and Vlad-Florin Dragoi},
      title = {Punctured Syndrome Decoding Problem Efficient Side-Channel Attacks Against Classic McEliece},
      howpublished = {Cryptology ePrint Archive, Paper 2023/308},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/308}},
      url = {https://eprint.iacr.org/2023/308}
}