International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Prasanna Ravi , Temasek Laboratories, Nanyang Technological University, Singapore; School of Computer Science and Engineering, Nanyang Technological University, Singapore
Bolin Yang , Zhejiang University, Hangzhou, China; Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Hangzhou, China
Shivam Bhasin , Temasek Laboratories, Nanyang Technological University, Singapore
Fan Zhang
Anupam Chattopadhyay , Temasek Laboratories, Nanyang Technological University, Singapore; School of Computer Science and Engineering, Nanyang Technological University, Singapore
Download:
DOI: 10.46586/tches.v2023.i2.447-481
URL: https://tches.iacr.org/index.php/TCHES/article/view/10290
Search ePrint
Search Google
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 optimized implementations of Kyber and Dilithium, from the open-source pqm4 library on the ARM Cortex-M4 microcontroller. We also demonstrate that our proposed attacks are capable of bypassing concrete countermeasures against existing fault attacks on lattice-based KEMs and signature schemes. We believe our work motivates the need for more research towards development of countermeasures for the NTT against fault injection attacks.
BibTeX
@article{tches-2023-33044,
  title={Fiddling the Twiddle Constants - Fault Injection Analysis of the Number Theoretic Transform},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2023, Issue 2},
  pages={447-481},
  url={https://tches.iacr.org/index.php/TCHES/article/view/10290},
  doi={10.46586/tches.v2023.i2.447-481},
  author={Prasanna Ravi and Bolin Yang and Shivam Bhasin and Fan Zhang and Anupam Chattopadhyay},
  year=2023
}