Paper 2022/494

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

Emre Karabulut, Erdem Alkim, and Aydin Aysu

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 finalists 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 2^41 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. 2021 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)
DOI
10.1109/HOST49136.2021.9702284
Keywords
Side-channel attacksPost-quantum cryptographyNTRUCRYSTALS-DILITHIUM
Contact author(s)
ekarabu @ ncsu edu
History
2022-04-23: received
Short URL
https://ia.cr/2022/494
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/494,
      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}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/494},
      year = {2022},
      doi = {10.1109/HOST49136.2021.9702284},
      url = {https://eprint.iacr.org/2022/494}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.