Paper 2022/824

Fiddling the Twiddle Constants - Fault Injection Analysis of the Number Theoretic Transform

Prasanna Ravi, Temasek Laboratories and School of Computer Science and Engineering, Nanyang Technological University, Singapore
Bolin Yang
Shivam Bhasin, Temasek Laboratories, Nanyang Technological University, Singapore
Fan Zhang, Zhejiang University, China
Anupam Chattopadhyay, Temasek Laboratories and School of Computer Science and Engineering, Nanyang Technological University, Singapore
Abstract

In this work, we present the first fault injection analysis of the Number Theoretic Transform (NTT). The NTT is an integral computation unit, widely used for polynomial multiplication in several structured lattice-based key encapsulation mechanisms (KEMs) and digital signature schemes. We identify a critical single fault vulnerability in the NTT, which severely reduces the entropy of its output. This in turn enables us to perform a wide-range of attacks applicable to lattice-based KEMs as well as signature schemes. In particular, we demonstrate novel key recovery and message recovery attacks targeting the key generation and encryption procedure of Kyber KEM. We also propose novel existential forgery attacks targeting deterministic and probabilistic signing procedure of Dilithium, followed by a novel verification bypass attack targeting its verification procedure. All proposed exploits are demonstrated with high success rate using electromagnetic fault injection on state-of-the-art implementations of Kyber and Dilithium, from the open-source pqm4 library on the ARM Cortex-M4 microcontroller.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Number Theoretic Transform Lattice-based Cryptography Electromagnetic Fault Injection Kyber Dilithium
Contact author(s)
prasanna ravi @ ntu edu sg
yangbolin @ zju edu cn
sbhasin @ ntu edu sg
fanzhang @ zju edu cn
anupam @ ntu edu sg
History
2022-06-23: approved
2022-06-23: received
See all versions
Short URL
https://ia.cr/2022/824
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/824,
      author = {Prasanna Ravi and Bolin Yang and Shivam Bhasin and Fan Zhang and Anupam Chattopadhyay},
      title = {Fiddling the Twiddle Constants - Fault Injection Analysis of the Number Theoretic Transform},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/824},
      year = {2022},
      url = {https://eprint.iacr.org/2022/824}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.