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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-03-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/10290 |
| _version_ | 1827996736923107328 |
|---|---|
| author | Prasanna Ravi Bolin Yang Shivam Bhasin Fan Zhang Anupam Chattopadhyay |
| author_facet | Prasanna Ravi Bolin Yang Shivam Bhasin Fan Zhang Anupam Chattopadhyay |
| author_sort | Prasanna Ravi |
| collection | DOAJ |
| 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.
|
| first_indexed | 2024-04-10T05:17:46Z |
| format | Article |
| id | doaj.art-11cbe31452464388b85a8163aa565391 |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-10T05:17:46Z |
| publishDate | 2023-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-11cbe31452464388b85a8163aa5653912023-03-08T15:37:30ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252023-03-012023210.46586/tches.v2023.i2.447-481Fiddling the Twiddle Constants - Fault Injection Analysis of the Number Theoretic TransformPrasanna Ravi0Bolin Yang1Shivam Bhasin2Fan Zhang3Anupam Chattopadhyay4Temasek Laboratories, Nanyang Technological University, Singapore; School of Computer Science and Engineering, Nanyang Technological University, SingaporeZhejiang University, Hangzhou, China; Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Hangzhou, ChinaTemasek Laboratories, Nanyang Technological University, SingaporeZhejiang University, Hangzhou, China; Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Hangzhou, China; ZJU-Hangzhou Global Scientific and Technological Innovation Center, Hangzhou, China; Jiaxing Research Institute, Zhejiang University, Jiaxing, ChinaTemasek Laboratories, Nanyang Technological University, Singapore; School of Computer Science and Engineering, Nanyang Technological University, Singapore 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. https://tches.iacr.org/index.php/TCHES/article/view/10290Lattice-based cryptographyElectromagnetic Fault-Injection attackNumber Theoretic TransformLearning With ErrorKyberDilithium |
| spellingShingle | Prasanna Ravi Bolin Yang Shivam Bhasin Fan Zhang Anupam Chattopadhyay Fiddling the Twiddle Constants - Fault Injection Analysis of the Number Theoretic Transform Transactions on Cryptographic Hardware and Embedded Systems Lattice-based cryptography Electromagnetic Fault-Injection attack Number Theoretic Transform Learning With Error Kyber Dilithium |
| title | 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_short | 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 |
| topic | Lattice-based cryptography Electromagnetic Fault-Injection attack Number Theoretic Transform Learning With Error Kyber Dilithium |
| url | https://tches.iacr.org/index.php/TCHES/article/view/10290 |
| work_keys_str_mv | AT prasannaravi fiddlingthetwiddleconstantsfaultinjectionanalysisofthenumbertheoretictransform AT bolinyang fiddlingthetwiddleconstantsfaultinjectionanalysisofthenumbertheoretictransform AT shivambhasin fiddlingthetwiddleconstantsfaultinjectionanalysisofthenumbertheoretictransform AT fanzhang fiddlingthetwiddleconstantsfaultinjectionanalysisofthenumbertheoretictransform AT anupamchattopadhyay fiddlingthetwiddleconstantsfaultinjectionanalysisofthenumbertheoretictransform |