Single-Trace Side-Channel Attacks on ω-Small Polynomial Sampling: With Applications to NTRU, NTRU Prime, and CRYSTALS-DILITHIUM

Emre Karabulut, Erdem Alkim, Aydin Aysu

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's SampleSparse (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

Abstract

This paper proposes a new single-trace side-channel attack on lattice-based post-quantum protocols. We target the ω-small polynomial sampling of NTRU, NTRU Prime, and CRYSTALS-DILITHIUM algorithm implementations (which are NIST Round-3 finalist and alternative candidates), and we demonstrate the vulnerabilities of their sub-routines to a power-based side-channel attack. Specifically, we reveal that the sorting implementation in NTRU/NTRU Prime and the shuffling in CRYSTALS-DILITHIUM's ω-small polynomial sampling process leaks information about the ‘-1’’0’, or ’+1' assignments made to the coefficients. We further demonstrate that these assignments can be found within a single power measurement and that revealing them allows secret and session key recovery for NTRU/NTRU Prime, while reducing the challenge polynomial's entropy for CRYSTALS-DILITHIUM. We execute our proposed attacks on an ARM Cortex-M4 microcontroller running the reference software submissions from NIST Round-3 software packages. The results show that our attacks can extract coefficients with a success rate of 99.78% for NTRU and NTRU Prime, reducing the search space to 241 or below. For CRYSTALS-DILITHIUM, our attack recovers the coefficients’ signs with over 99.99% success, reducing rejected challenge polynomials’ entropy between 39 to 60 bits. Our work informs the proposers about the single-trace vulnerabilities of their software and urges them to develop single-trace resilient software for low-cost microcontrollers.
BibTeX
@article{karabulut2022single,
  author = {Emre Karabulut and Erdem Alkim and Aydin Aysu},
  title = {{Single-Trace Side-Channel Attacks on ω-Small Polynomial Sampling: With Applications to NTRU, NTRU Prime, and CRYSTALS-DILITHIUM}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2022},
  url = {https://openreview.net/forum?id=Z9weFnrYUm},
}

Loading related content...

Figure