Zero-Value Filtering for Accelerating Non-Profiled Side-Channel Attack on Incomplete NTT based Implementations of Lattice-based Cryptography

Tolun Tosun; Erkay Savas

Paper 2023/1046

Zero-Value Filtering for Accelerating Non-Profiled Side-Channel Attack on Incomplete NTT based Implementations of Lattice-based Cryptography

Tolun Tosun

, Sabancı University, Analog Devices

Erkay Savas

, Sabancı University

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 cryptography side-channel attack correlation power analysis multivariate mutual information analysis dilithium kyber
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},
      note = {\url{https://eprint.iacr.org/2023/1046}},
      url = {https://eprint.iacr.org/2023/1046}
}