How to Lose Some Weight - A Practical Template Syndrome Decoding Attack

Sebastian Bitzer; Jeroen Delvaux; Elena Kirshanova; Sebastian Maaßen; Alexander May; Antonia Wachter-Zeh

Paper 2024/621

How to Lose Some Weight - A Practical Template Syndrome Decoding Attack

Sebastian Bitzer

, Technical University of Munich

Jeroen Delvaux

, Technology Innovation Institute

Elena Kirshanova

, Technology Innovation Institute

Sebastian Maaßen, Ruhr University Bochum

Alexander May

, Ruhr University Bochum

Antonia Wachter-Zeh

, Technical University of Munich

Abstract

We study the hardness of the Syndrome Decoding problem, the base of most code-based cryptographic schemes, such as Classic McEliece, in the presence of side-channel information. We use ChipWhisperer equipment to perform a template attack on Classic McEliece running on an ARM Cortex-M4, and accurately classify the Hamming weights of consecutive 32-bit blocks of the secret error vector. With these weights at hand, we optimize Information Set Decoding algorithms. Technically, we show how to speed up information set decoding via a dimension reduction, additional parity-check equations, and an improved information set search, all derived from the Hamming weight information. Consequently, using our template attack, we can practically recover an error vector in dimension n=2197 in a matter of seconds. Without side-channel information, such an instance has a complexity of around 88 bit. We also estimate how our template attack affects the security of the proposed McEliece parameter sets. Roughly speaking, even an error-prone leak of our Hamming weight information leads for n=3488 to a security drop of 89 bits.

Note: An extended abstract accepted at WCC 2024.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Code-based cryptography Side-channel attacks Classic McEliece Information Set Decoding
Contact author(s): sebastian bitzer @ tum de
Jeroen Delvaux @ tii ae
Elena Kirshanova @ tii ae
Sebastian Maassen @ ruhr-uni-bochum de
alex may @ rub de
History: 2024-04-26: approved; 2024-04-22: received; See all versions
Short URL: https://ia.cr/2024/621
License: CC BY

BibTeX

@misc{cryptoeprint:2024/621,
      author = {Sebastian Bitzer and Jeroen Delvaux and Elena Kirshanova and Sebastian Maaßen and Alexander May and Antonia Wachter-Zeh},
      title = {How to Lose Some Weight - A Practical Template Syndrome Decoding Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2024/621},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/621}},
      url = {https://eprint.iacr.org/2024/621}
}