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 · Designs Codes and Cryptography · 2025
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 $$\textbf{e}\in {{\mathbb {F}}}_2^n$$ e ∈ F 2 n . With these weights at hand, we optimize Information Set Decoding algorithms. Technically, we demonstrate 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 $$\textbf{e}\in {{\mathbb {F}}}_2^n$$ e ∈ F 2 n in dimension $$n=2197$$ 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$$ n = 3488 to a security drop of 89 bits.