Paper 2024/070

Hints from Hertz: Dynamic Frequency Scaling Side-Channel Analysis of Number Theoretic Transform in Lattice-Based KEMs

Tianrun Yu, China University of Geosciences, Wuhan
Chi Cheng, China University of Geosciences, Wuhan
Zilong Yang, China University of Geosciences, Wuhan
Yingchen Wang, University of Texas at Austin
Yanbin Pan, Academy of Mathematics and Systems Science, Chinese Academy of Sciences
Jian Weng, Jinan University

Number Theoretic Transform (NTT) has been widely used in accelerating computations in lattice-based cryptography. However, attackers can potentially launch power analysis targeting NTT because it is usually the most time-consuming part of the implementation. This extended time frame provides a natural window of opportunity for attackers. In this paper, we investigate the first CPU frequency leakage (Hertzbleed-like) attacks against NTT in lattice-based KEMs. Our key observation is that different inputs to NTT incur different Hamming weights in its output and intermediate layers. By measuring the CPU frequency during the execution of NTT, we propose a simple yet effective attack idea to find the input to NTT that triggers NTT processing data with significantly low Hamming weight. We further apply our attack idea to real-world applications that are built upon NTT: CPA-secure Kyber without Compression and Decompression functions, and CCA-secure NTTRU. This leads us to extract information or frequency Hints about the secret key. Integrating these Hints into the LWE-estimator framework, we estimate a minimum of $35\%$ security loss caused by the leakage. The frequency and timing measurements on the Reference and AVX2 implementations of NTT in both Kyber and NTTRU align well with our theoretical analysis, confirming the existence of frequency side-channel leakage in NTT. It is important to emphasize that our observation is not limited to a specific implementation but rather the algorithm on which NTT is based. Therefore, our results call for more attention to the analysis of power leakage against NTT in lattice-based cryptography.

Available format(s)
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in TCHES 2024
Lattice-based cryptographySide-channel attacksHertzbleed attackPQCKyberNumber Theoretic Transform
Contact author(s)
yutianrun @ cug edu cn
chengchi @ cug edu cn
yingchen @ cs utexas edu
2024-06-10: revised
2024-01-17: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Tianrun Yu and Chi Cheng and Zilong Yang and Yingchen Wang and Yanbin Pan and Jian Weng},
      title = {Hints from Hertz: Dynamic Frequency Scaling Side-Channel Analysis of Number Theoretic Transform in Lattice-Based {KEMs}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/070},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.