Paper 2023/1046
Zero-Value Filtering for Accelerating Non-Profiled Side-Channel Attack on Incomplete NTT based Implementations of Lattice-based Cryptography
Abstract
Lattice-based cryptographic schemes such as Crystals-Kyber and Dilithium are post-quantum algorithms selected to be standardized by NIST as they are considered to be secure against quantum computing attacks. The multiplication in polynomial rings is the most time-consuming operation in many lattice-based cryptographic schemes, which is also subject to side-channel attacks. While NTT-based polynomial multiplication is almost a norm in a wide range of implementations, a relatively new method, incomplete NTT is preferred to accelerate lattice-based cryptography, especially on some computing platforms that feature special instructions. In this paper, we present a novel, efficient and non-profiled power/EM side-channel attack targeting polynomial multiplication based on the incomplete NTT algorithm. We apply the attack on the Crystals-Dilithium signature algorithm and Crystals-Kyber KEM. We demonstrate that the method accelerates attack run-time when compared to the existing approaches. While a conventional non-profiled side-channel attack tests a much larger hypothesis set because it needs to predict two coefficients of secret polynomials together, we propose a much faster zero-value filtering attack (ZV-FA), which reduces the size of the hypothesis set by targeting the coefficients individually. We also propose an effective and efficient validation and correction technique employing the inverse NTT to estimate and modify the mispredicted coefficients. Our experimental results show that we can achieve a speed-up of 1915x over brute-force.
Note: Accepted for publication.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY
- DOI
- 10.1109/TIFS.2024.3359890
- Keywords
- post-quantum cryptographyside-channel attackcorrelation power analysismultivariate mutual information analysisdilithiumkyber
- Contact author(s)
-
toluntosun @ sabanciuniv edu
erkays @ sabanciuniv edu - History
- 2024-02-06: last of 2 revisions
- 2023-07-04: received
- See all versions
- Short URL
- https://ia.cr/2023/1046
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1046, author = {Tolun Tosun and Erkay Savas}, title = {Zero-Value Filtering for Accelerating Non-Profiled Side-Channel Attack on Incomplete {NTT} based Implementations of Lattice-based Cryptography}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1046}, year = {2023}, doi = {10.1109/TIFS.2024.3359890}, url = {https://eprint.iacr.org/2023/1046} }