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)
- 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
-
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} }