TL;DR
This paper introduces the first single-trace side-channel attack targeting the "ω-small polynomial sampling" subroutine, a crucial component in several post-quantum cryptography schemes like NTRU, NTRU Prime, and CRYSTALS-DILITHIUM. The attack successfully extracts secret information from these algorithms using just one power measurement, posing a significant threat to their security.
What Problem Does This Paper Address?
The race to develop quantum-resistant cryptography has led to the NIST post-quantum standardization process, with lattice-based cryptosystems emerging as strong contenders. While theoretical security and performance have been primary evaluation criteria, side-channel vulnerabilities (like power consumption analysis) are critical for real-world security, especially for low-cost embedded devices. Existing side-channel attacks on lattice cryptography have focused on various subroutines, but the "ω-small polynomial sampling" process, used in key generation, encapsulation, and signing, remained largely unexplored. This paper addresses this gap by demonstrating that this specific subroutine, despite its seemingly minor role, harbors vulnerabilities exploitable by single-trace attacks, which are particularly dangerous as they bypass common countermeasures.
Methods
The core of the paper is a novel single-trace side-channel attack that targets the implementation of the "ω-small polynomial sampling" subroutine. The authors employ a template-based side-channel attack methodology. This involves:
- Profiling: Capturing multiple power traces from an identical device running the target algorithm with known inputs.
- POI Identification: Using techniques like Sum-of-Squared-Differences (SOSD) to pinpoint specific time intervals (Points of Interest - POIs) within the power traces that exhibit significant variations correlated with the secret data.
- Template Building: Constructing statistical models (Gaussian templates) based on the power consumption at the identified POIs for different possible secret values.
- Attack Execution: Using a single, unseen power trace and comparing its POI measurements against the pre-built templates to predict the secret value.
The authors specifically analyze two sampling algorithms: SamplePerm() used in NTRU/NTRU Prime and SampleSparse() used in CRYSTALS-DILITHIUM. They identify vulnerabilities in the sorting and shuffling operations within these algorithms, respectively, which leak information about coefficient assignments (-1, 0, or +1).
Datasets
The authors evaluated their attacks on the reference software implementations of NTRU-HPS, NTRU Prime, and CRYSTALS-DILITHIUM, obtained from the NIST Round-3 submission packages. The experiments were conducted on an ARM Cortex-M4 microcontroller. The "datasets" in this context are the power traces captured from the device during the execution of these specific cryptographic algorithms. No new benchmark datasets were introduced; rather, the authors leveraged existing implementations.
Key Insights and Ideas
- "Small" doesn't mean "Secure": The paper highlights that even seemingly minor subroutines like "ω-small polynomial sampling" can be critical security weak points in post-quantum cryptography.
- Single-Trace is a Game Changer: The success of a single-trace attack is particularly alarming because it bypasses many common countermeasures designed to thwart multi-trace attacks (e.g., masking).
- Orthogonal Vulnerability: The identified leakage is distinct from previously known side-channel vulnerabilities in lattice cryptography, meaning existing defenses might not protect against this specific attack.
- Implementation Matters: The specific implementation details of sorting (
SamplePerm) and shuffling (SampleSparse) are crucial. The authors show that subtle differences in how these operations are coded can lead to varying degrees of leakage. - NTRU/NTRU Prime More Vulnerable: The attack on NTRU/NTRU Prime's
SamplePerm(specifically its sorting component) is more effective, allowing for full secret/session key recovery. CRYSTALS-DILITHIUM'sSampleSparse(shuffling) leaks less information, primarily revealing coefficient signs, which reduces entropy but doesn't directly lead to full key recovery in a single trace.
Key Results
- NTRU/NTRU Prime: The attack achieved a success rate of 99.78% in recovering coefficients. This significantly reduces the brute-force search space for the secret key to 2<sup>41</sup> or below.
- CRYSTALS-DILITHIUM: The attack successfully recovered the signs of coefficients with a success rate of over 99.99%. This reduces the entropy of rejected challenge polynomials by 39 to 60 bits.
- The attacks were successfully demonstrated on an off-the-shelf ARM Cortex-M4 microcontroller.
Limitations and Future Work
- Cross-Device Attacks: The current attack is primarily demonstrated on an identical device. The authors acknowledge that cross-device attacks (where the attacker doesn't have an identical device for profiling) remain an open problem for single-trace side-channels in post-quantum cryptography.
- Template Attack Limitations: Template attacks themselves have limitations, including the time required to build profiles and potential issues with cross-device compatibility.
- Future Work: The authors emphasize the need for developers to incorporate defenses against single-trace side-channel attacks, suggesting methods like shuffling, randomization, or differential circuit styles. They also call for more research into single-trace side-channel aware software development for post-quantum cryptosystems.
Summary updated