Fiddling the twiddle constants - fault injection analysis of the number theoretic transform

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Ravi, Prasanna, Yang, Bolin, Bhasin, Shivam, Zhang, Fan, Chattopadhyay, Anupam
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2023
Subjects:
Online Access:https://hdl.handle.net/10356/169827
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-169827
record_format dspace
spelling sg-ntu-dr.10356-1698272023-08-11T15:35:32Z Fiddling the twiddle constants - fault injection analysis of the number theoretic transform Ravi, Prasanna Yang, Bolin Bhasin, Shivam Zhang, Fan Chattopadhyay, Anupam School of Computer Science and Engineering Engineering::Computer science and engineering Dilithium Electromagnetic Fault-Injection Attack 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. National Research Foundation (NRF) Published version This work was supported in part by National Key R&D Program of China (2020AAA0107700), by National Natural Science Foundation of China (62227805, 62072398), by AlibabaZhejiang University Joint Institute of Frontier Technologies, by Leading Innovative and Entrepreneur Team Introduction Program of Zhejiang (2018R01005), and by Research Institute of Cyberspace Governance in Zhejiang University, by National Key Laboratory of Science and Technology on Information System Security (6142111210301), by State Key Laboratory of Mathematical Engineering and Advanced Computing, and by Open Foundation of Henan Key Laboratory of Cyberspace Situation Awareness (HNTS2022001). The authors would also like to acknowledge the financial support received from the Singapore National Research Foundation under the SoCure NRF2018NCR-NCR002-0001 grant (www.green-ic.org/socure) for carrying out this research. 2023-08-07T06:55:20Z 2023-08-07T06:55:20Z 2023 Journal Article Ravi, P., Yang, B., Bhasin, S., Zhang, F. & Chattopadhyay, A. (2023). Fiddling the twiddle constants - fault injection analysis of the number theoretic transform. IACR Transactions On Cryptographic Hardware and Embedded Systems, 2023(2), 447-481. https://dx.doi.org/10.46586/tches.v2023.i2.447-481 2569-2925 https://hdl.handle.net/10356/169827 10.46586/tches.v2023.i2.447-481 2-s2.0-85150012404 2 2023 447 481 en NRF2018NCR-NCR002-0001 IACR Transactions on Cryptographic Hardware and Embedded Systems © 2023 Prasanna Ravi, Bolin Yang, Shivam Bhasin, Fan Zhang, Anupam Chattopadhyay. This work is licensed under a Creative Commons Attribution 4.0 International License. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Engineering::Computer science and engineering
Dilithium
Electromagnetic Fault-Injection Attack
spellingShingle Engineering::Computer science and engineering
Dilithium
Electromagnetic Fault-Injection Attack
Ravi, Prasanna
Yang, Bolin
Bhasin, Shivam
Zhang, Fan
Chattopadhyay, Anupam
Fiddling the twiddle constants - fault injection analysis of the number theoretic transform
description 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.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Ravi, Prasanna
Yang, Bolin
Bhasin, Shivam
Zhang, Fan
Chattopadhyay, Anupam
format Article
author Ravi, Prasanna
Yang, Bolin
Bhasin, Shivam
Zhang, Fan
Chattopadhyay, Anupam
author_sort Ravi, Prasanna
title Fiddling the twiddle constants - fault injection analysis of the number theoretic transform
title_short Fiddling the twiddle constants - fault injection analysis of the number theoretic transform
title_full Fiddling the twiddle constants - fault injection analysis of the number theoretic transform
title_fullStr Fiddling the twiddle constants - fault injection analysis of the number theoretic transform
title_full_unstemmed Fiddling the twiddle constants - fault injection analysis of the number theoretic transform
title_sort fiddling the twiddle constants - fault injection analysis of the number theoretic transform
publishDate 2023
url https://hdl.handle.net/10356/169827
_version_ 1779156598013296640