Abstract
Classic McEliece is a leading candidate in the NIST post-quantum cryptography standardization process. While its security is theoretically grounded in the hardness of the Syndrome Decoding (SD) problem, its physical implementations remain susceptible to side-channel analysis. This paper introduces a practical template attack on an ARM Cortex-M4 processor that leaks the Hamming weights of the secret error vector. By integrating these weights into modified Information Set Decoding (ISD) algorithms, the authors demonstrate a dramatic reduction in the computational complexity required to recover secret keys, effectively breaking standard security instances in seconds.
Introduction
The security of code-based cryptosystems like Classic McEliece depends on the difficulty of finding a sparse error vector $\mathbf{e}$ given a parity-check matrix $\mathbf{H}$ and a syndrome $\mathbf{s} = \mathbf{He}$. While this problem is computationally intensive for both classical and quantum adversaries, side-channel attacks (SCA) exploit physical leakages—such as power consumption—to gain information about internal computations. This research bridges the gap between theoretical weight-leakage attacks and real-world exploitation by weaponizing noisy side-channel data through algorithmic optimization.
Methodology: Template-Based Syndrome Decoding
The attack follows a multi-stage pipeline combining physical profiling with algorithmic refinement.
1. Side-Channel Profiling and Classification
Using ChipWhisperer equipment, the researchers performed a template attack on an ARM Cortex-M4. By profiling the power signatures of 32-bit blocks during Hamming weight computations, they built a classifier capable of guessing the weights of secret error vector blocks with approximately 97% accuracy.
2. Algorithmic Integration
The core innovation lies in the "Template ISD" method, which adapts standard algorithms like Prange and Dumer to utilize the leaked weight information:
- Dimension Reduction: Blocks identified as having zero weight are removed, significantly shrinking the search space.
- Parity Constraints: The leaked weight provides a sum of bits (weight mod 2), yielding new linear equations for the system.
- Biased Permutations: The "TemplatePerm" strategy biases random permutations to favor blocks with higher leaked weights, increasing the likelihood of selecting a valid information set.
3. Handling Noise
To account for the 3% error rate in weight classification, the authors developed a preprocessing algorithm using Maximum-A-Posteriori (MAP) estimation. This allows the attack to remain robust; if the side-channel data is perfect, the solution is nearly instantaneous, but if it is noisy, the algorithm gracefully degrades toward a standard classical ISD attack.
Key Results and Security Impact
The practical implications of this attack are severe. For a challenge instance with $n=2197$ (traditionally requiring ~88 bits of security), the secret error vector was recovered in just 10 seconds using a standard server.
As shown in the table below, the security degradation for standard Classic McEliece parameter sets is substantial. For the $n=3488$ set, the security level drops from 151 bits to 68 bits when using the "Template Dumer" variant.
Discussion and Insights
A critical insight of this work is that even imperfect side-channel information is highly valuable. Zero-weight blocks provide immediate dimension reduction, while the parity of a block remains a robust hint even if the exact weight is misclassified. The attack demonstrates that side-channel leakage should be treated as a probabilistic "hint" rather than an absolute truth, making the exploitation resilient to real-world measurement noise.
Conclusion and Future Work
This research highlights a significant vulnerability in unprotected implementations of Classic McEliece. While the attack was demonstrated on a target without side-channel countermeasures, it underscores the necessity of incorporating masking or shuffling techniques. Future work will explore bit-level leakage—identifying specific set bits rather than just block weights—which could potentially lead to even more efficient decoding attacks.
Summary updated