TL;DR
This paper introduces a novel single-trace side-channel attack targeting the "ω-small polynomial sampling" routines in leading post-quantum cryptography candidates (NTRU, NTRU Prime, and CRYSTALS-DILITHIUM). The attack exploits power consumption variations during these sampling processes to reveal secret key information, significantly weakening the security of NTRU/NTRU Prime and reducing the complexity for CRYSTALS-DILITHIUM.
What Problem Does This Paper Address?
The transition to post-quantum cryptography (PQC) is crucial as current encryption and signature schemes are vulnerable to quantum computers. NIST has been standardizing PQC algorithms, with lattice-based cryptography being a prominent choice due to its efficiency. While theoretical security and performance have been primary selection criteria, the security of these algorithms against physical attacks, particularly side-channel attacks (SCAs), is equally important for real-world deployment. SCAs exploit physical leakage (like power consumption) to infer secret information. Single-trace SCAs are particularly concerning as they require only one measurement, bypassing many common defenses. This paper addresses a gap in SCA research by focusing on the "ω-small polynomial sampling" sub-routine, a common component in several NIST PQC finalists, which had not been previously analyzed for side-channel vulnerabilities.
Methods
The core of the attack lies in analyzing the power consumption of the device while it executes the ω-small polynomial sampling. The authors propose a template-based single-trace side-channel attack. This involves:
- Identifying Vulnerable Operations: They pinpoint specific operations within the sampling routines (sorting in NTRU/NTRU Prime, shuffling in CRYSTALS-DILITHIUM) that are likely to leak information.
- Power Trace Analysis: They capture power traces of the device performing these operations and use techniques like Sum-of-Squared-Differences (SOSD) to identify "points of interest" (POIs) where power consumption varies significantly based on the secret values being processed.
- Template Building: For each possible secret value (e.g., coefficients being -1, 0, or +1), they build a "template" by averaging power traces corresponding to that value. This template represents the expected power signature for a given secret.
- Single-Trace Attack: During a single execution of the target algorithm, they capture its power trace, isolate the relevant sub-trace around the identified POI, and compare it against the pre-built templates. The template that best matches the observed power trace reveals the secret coefficient.
The specific implementations targeted are:
- NTRU/NTRU Prime: The
SamplePerm()function, which involves sorting operations. The attack targets thecrypto_sort_int32andint32_MINMAXfunctions. - CRYSTALS-DILITHIUM: The
SampleSparse()function, which involves shuffling operations. The attack targets the coefficient assignment step.
Datasets
The experiments were conducted on reference software implementations of NTRU-HPS, NTRU Prime, and CRYSTALS-DILITHIUM, obtained from the NIST Round-3 submission packages. The attacks were executed on an ARM Cortex-M4 microcontroller. For profiling (building templates), the researchers captured 90,000 power traces. For testing the attack's success rate, they used 10,000 power traces for each experiment. No new benchmark datasets were introduced; instead, the attack was performed on the actual implementations of the PQC candidates.
Key Insights and Ideas
- Ubiquitous Vulnerability: The ω-small polynomial sampling, a seemingly innocuous operation, is a significant source of side-channel leakage in multiple PQC candidates. This highlights that even standard cryptographic primitives can harbor vulnerabilities when implemented.
- Orthogonal Leakage: The identified leakage is "orthogonal" to previously known side-channel vulnerabilities in lattice cryptography, meaning existing countermeasures might not protect against this specific attack.
- NTRU/NTRU Prime's Weakness: The sorting mechanism in NTRU/NTRU Prime is particularly vulnerable, allowing for the recovery of coefficients that directly lead to secret and session key recovery.
- CRYSTALS-DILITHIUM's Relative Strength: While CRYSTALS-DILITHIUM's shuffling also leaks information, it primarily reveals the signs of coefficients (-1 or +1), which is less critical than recovering the full coefficient value. This makes it more resilient to this specific attack compared to NTRU/NTRU Prime.
- Practicality on Low-Cost Hardware: The attack is demonstrated on an affordable ARM Cortex-M4 microcontroller, indicating its feasibility on resource-constrained devices where SCAs are often a concern.
Key Results
- NTRU/NTRU Prime: The attack achieved a success rate of 99.78% in recovering coefficients. This significantly reduces the search space for the secret key to 2^41 or below.
- CRYSTALS-DILITHIUM: The attack achieved a success rate of over 99.99% in recovering the signs of coefficients. This reduces the entropy of rejected challenge polynomials by 39 to 60 bits.
Limitations and Future Work
- Cross-Device Attacks: The current attack is demonstrated on a single device. The authors acknowledge that cross-device attacks, where templates are built on one device and applied to another, are more challenging and remain an open problem in single-trace SCA research.
- Template Attack Limitations: Template attacks inherently have limitations regarding processing time for building profiles and potential cross-device transferability.
- Future Work: The authors urge developers to incorporate defenses against single-trace side-channel attacks into their implementations. This could involve shuffling techniques, randomization, or differential circuit styles. They also suggest that further research is needed to explore more robust countermeasures and to address the cross-device SCA challenge. The paper also implies that other implementations of these PQC schemes (e.g., assembly-optimized versions or those in libraries like pqm4) might also be vulnerable.
Summary updated