Paper 2023/546

Horizontal Correlation Attack on Classic McEliece

Brice Colombier, Laboratoire Hubert Curien
Vincent Grosso, Laboratoire Hubert Curien
Pierre-Louis Cayrel, Laboratoire Hubert Curien
Vlad-Florin Drăgoi, Aurel Vlaicu University of Arad
Abstract

As the technical feasibility of a quantum computer becomes more and more likely, post-quantum cryptography algorithms are receiving particular attention in recent years. Among them, code-based cryptosystems were first considered unsuited for hardware and embedded software implementations because of their very large key sizes. However, recent work has shown that such implementations are practical, which also makes them susceptible to physical attacks. In this article, we propose a horizontal correlation attack on the Classic McEliece cryptosystem, more precisely on the matrix-vector multiplication over $\mathbb{F}_2$ that computes the shared key in the encapsulation process. The attack is applicable in the broader context of Niederreiter-like code-based cryptosystems and is independent of the code structure, i.e. it does not need to exploit any particular structure in the parity check matrix. Instead, we take advantage of the constant time property of the matrix-vector multiplication over $\mathbb{F}_2$. We extend the feasibility of the basic attack by leveraging information-set decoding methods and carry it out successfully on the reference embedded software implementation. Interestingly, we highlight that implementation choices, like the word size or the compilation options, play a crucial role in the attack success, and even contradict the theoretical analysis.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Post-quantum cryptographySide-channel attacksClassic McEliece
Contact author(s)
b colombier @ univ-st-etienne fr
vincent grosso @ univ-st-etienne fr
pierre louis cayrel @ univ-st-etienne fr
vlad dragoi @ uav ro
History
2023-04-17: approved
2023-04-17: received
See all versions
Short URL
https://ia.cr/2023/546
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2023/546,
      author = {Brice Colombier and Vincent Grosso and Pierre-Louis Cayrel and Vlad-Florin Drăgoi},
      title = {Horizontal Correlation Attack on Classic {McEliece}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/546},
      year = {2023},
      url = {https://eprint.iacr.org/2023/546}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.