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...
Saved in:
Main Authors: | , , , , |
---|---|
Other Authors: | |
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 |