Exploring Side-Channel Protections in Hardware Implementations of PQC ML-KEM Verification

Technical Summary: Exploring Side-Channel Protections in Hardware Implementations of PQC ML-KEM Verification

Problem Statement
As the Module-Lattice-based Key-Encapsulation Mechanism (ML-KEM), standardized by NIST and based on the CRYSTALS-Kyber algorithm, is adopted for post-quantum cryptography, its resilience against physical side-channel attacks has become critical. While previous research has extensively documented vulnerabilities in software and microcontroller implementations—specifically regarding the Fujisaki-Okamoto (FO) verification step during decapsulation—the security of hardware-accelerated, FPGA-based implementations remains largely unexplored.

The FO verification step compares a locally re-encrypted ciphertext with the original input. If they mismatch, the algorithm outputs random bytes to ensure IND-CCA2 security. However, this step is vulnerable to side-channel analysis (SCA) where an attacker crafts slightly malformed ciphertexts. By analyzing power or electromagnetic (EM) emanations during the comparison, an attacker can distinguish between "decapsulation success" (minimal difference) and "decapsulation failure" (significant difference). This classification allows the construction of a system of inequalities solvable via belief propagation to recover the long-term secret key. While countermeasures such as hash-based comparisons and higher-order masking have been proposed for serial platforms, their efficacy in the context of the high parallelism and spatial distribution inherent to FPGA architectures is unknown.

Methodology
The authors conducted a systematic evaluation of three distinct ML-KEM verification implementations across two hardware platforms:

1. Platforms: A RISCURE Pinata board featuring an ARM Cortex-M4 microcontroller (168 MHz) representing the NIST baseline, and a SAKURA-G FPGA board with a Xilinx Spartan-6 chip. Power traces were captured at 1 GS/s using a Teledyne LeCroy oscilloscope.
2. Implementations Evaluated:
   • Unprotected: A baseline implementation performing direct byte-wise XOR/AND comparison. On the FPGA, this was implemented with variable parallelism (32-bit, 128-bit, and 512-bit widths) to study the impact of parallelization.
   • Hash-Based (First-Order): A countermeasure hashing ciphertexts with SHAKE-128 (SHA-3) before comparison. The FPGA implementation utilized row-by-row parallelization and experimented with randomized row processing orders to introduce temporal entropy.
   • Higher-Order Masked: A masked verification algorithm based on Galois Field (GF) arithmetic, designed to split data into randomized shares (4-share and 6-share configurations). The FPGA version was pipeline-optimized, parallelizing across the configurable number of shares.
3. Analysis: The authors preprocessed 8,000 traces per class, aligning them to account for clock drift. They utilized T-testing to identify leakage points, calculated Signal-to-Noise Ratios (SNR), and employed clustering-based machine learning classifiers to determine the accuracy of distinguishing between success and failure cases. Classification accuracies below 80% were considered unsuccessful for key recovery.

Key Contributions

• First Systematic FPGA Analysis: This work is among the first to systematically investigate the side-channel security of the FO verification step specifically within FPGA-accelerated environments, contrasting them with established microcontroller baselines.
• Parallelism vs. Leakage Correlation: The study demonstrates that while FPGAs offer significant throughput improvements, the parallelization strategies used to achieve this performance often exacerbate side-channel leakage rather than mitigating it.
• Evaluation of Countermeasures on Hardware: The paper rigorously tests whether standard software countermeasures (hashing and masking) translate effectively to hardware, revealing specific failure modes in parallelized architectures.

Experimental Results

• Unprotected Implementations:
  • The microcontroller achieved a classification accuracy of 94.8% (SNR 2.40).
  • The FPGA's 32-bit parallel implementation had lower accuracy (62.9%, SNR 0.95), insufficient for key recovery.
  • However, increasing FPGA parallelism to 128-bit and 512-bit drastically increased leakage, achieving classification accuracies of 99.1% and 100.0% respectively (SNRs of 3.83 and 8.33). The wider combinational logic resulted in clearer, more distinguishable signals, with the 512-bit FPGA showing a ~530x throughput speedup over the microcontroller but with significantly higher vulnerability.
• Hash-Based Implementation:
  • Despite using SHAKE-128, the FPGA implementation remained vulnerable. The T-tests revealed that the Rho/Pi subfunction in the early rounds of the Keccak permutation retained structural dependence on input data.
  • Classification accuracy reached 94.7%.
  • Randomized row scheduling failed to obscure the leakage; the distinct power signatures of the five permutation segments allowed attackers to fingerprint the execution order with 99.9% accuracy, effectively neutralizing the randomization.
• Higher-Order Masked Implementation:
  • While the microcontroller implementation was secure against t-probing, the FPGA implementation leaked information due to hardware-level effects.
  • Parallel processing of masked shares reduced the effective masking order. The 4-share and 6-share FPGA implementations achieved classification accuracies of 97.9% and 98.5%, respectively—higher than the 95.0% accuracy reported for similar attacks on microcontrollers.
  • The increased parallelism caused instantaneous activity to correlate more strongly with underlying bit differences, undermining the theoretical security of the masking scheme.

Significance and Claims
The paper concludes that the transition from serial (microcontroller) to parallel (FPGA) execution fundamentally alters the side-channel threat landscape for ML-KEM. The authors assert that:

1. Performance-Security Trade-off: In FPGA environments, the pursuit of higher performance through parallelism directly correlates with stronger side-channel leakage, making high-throughput configurations more vulnerable than their serial counterparts.
2. Insufficiency of Ported Countermeasures: Countermeasures designed for serial execution, such as hash-based comparisons and higher-order masking, are insufficient when naively parallelized on FPGAs. The hardware-level effects (e.g., spatial distribution of logic, simultaneous switching) create new leakage mechanisms that bypass these protections.
3. Need for Bespoke Hardware Solutions: Securing PQC algorithms in performance-constrained and parallelized hardware requires "bespoke solutions" that explicitly account for the leakage models specific to parallel execution, rather than relying on adaptations of software-centric security strategies.

The authors emphasize that while their results are based on a Spartan-6 FPGA, the principles likely apply to newer, smaller-process-node FPGAs which may offer even greater parallelism and thus potentially greater leakage. They call for a reassessment of "secure-by-design" implementations for post-quantum algorithms to bridge the gap between theoretical security and practical hardware deployment.