Implementation attacks on post-quantum lattice-based cryptography

• Main Author: Ravi, Prasanna
• Other Authors: Anupam Chattopadhyay
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Computer science and engineering::Data::Data encryption
• Online Access: https://hdl.handle.net/10356/168674
• Institution: Nanyang Technological University

The impending threat of large scale quantum computers to traditional RSA and ECC-based public-key cryptographic schemes prompted NIST to initiate a global level standardization process for quantum-attack resistant cryptography, which is popularly known as Post-Quantum Cryptography (PQC). The NIST PQC process mainly focussed on standardization of Public Key Encryption (PKE) schemes, Key Encapsulation Mechanisms (KEM) and Digital Signature (DS) schemes. The process which started in 2017, is currently at the end of the third round when the first set of algorithms to be standardized were announced. NIST selected one (1) Public Key Encryption (PKE) and Key Encapsulation Mechanism (KEM) and three (3) Digital Signature (DS) schemes as the first standards for PQC. There are different categories of PQC, which base their security guarantees on different types of hard problems in mathematics. However, schemes which derive their security from problems based on geometric structures called as lattices have formed the majority category, with with maximum representation throughout the entire duration of the NIST PQC standardization process. This category of PQC is known as lattice-based cryptography. Three (3) out of the four (4) selected candidates for standardization belong to this category, owing to their good balance of security and efficiency. Thus, lattice-based cryptography becomes the main focus of our research. Among the various parameters that were used as criteria for standardization, such as theoretical post-quantum (PQ) security guarantees, implementation cost and performance, resistance against physical attacks such as Side-Channel Analysis (SCA) and Fault Injection Analysis (FIA) emerged as an important criteria for standardization in the final round of the NIST PQC process. This is especially critical given its potential wide-scale adoption in a wide-range of devices, and particularly in embedded devices to which an attacker can obtain unimpeded physical access to the device. In this respect, the main goal of our research is \emph{to advance the understanding of Side-Channel Analysis (SCA) and Fault-Injection Analysis (FIA) of lattice-based cryptography}. We lay particular focus on candidates for PKE, KEM and DS schemes that have been competing in the NIST PQC standardization process. This thesis is broadly divided into two parts - (1) Side-Channel Analysis (SCA) and (2) Fault-Injection Analysis (FIA). Side-Channel Analysis (SCA): In the first part of the thesis (Chapters 3-8), we focus exclusively on SCA of lattice-based cryptography. In this respect, we demonstrate that lattice-based PKE/KEMs contain inherent algorithmic features that make them susceptible to very simple side-channel attacks in a chosen-ciphertext setting. We demonstrate that an attacker can craft chosen-ciphertexts to magnify leakage about the secret key, to realize a side-channel based oracle which can be exploited to perform key recovery with very minimal knowledge about the implementation/target device. Moreover, we demonstrate that leakage from several operations can be easily exploited for key recovery and our attacks apply in a generic manner to six (6) LWE/LWR-based PKE/KEMs. We refer to these attacks as Side-Channel assisted Chosen Ciphertext attacks, and in short known as SCA assisted CCA. Fault-Injection Analysis (FIA): In the second part of the thesis (Chapters 9-12), we shift our focus to FIA of lattice-based schemes. We demonstrate that implementations of several lattice-based PKE/KEMs contain critical vulnerabilities that make them easily susceptible to fault-injection attacks. We show that algorithmic design choices as well as implementation techniques to achieve performance, can lead to single point of failures, that can be exploited for efficient FIA in both lattice-based PKE/KEMs as well as DS schemes. In a nutshell, our works have shown that side-channel attacks and fault-injection attacks form a potent and realistic threat against lattice-based schemes. We have identified that lattice-based schemes possess inherent algorithmic properties, that can be exploited by a side-channel or fault-injection attacker for practical attacks. Thus, our work stresses the need towards more research on development of efficient and secure countermeasures for practical and real-world security of lattice-based schemes.