Prasanna Ravi

The threat of practical quantum attacks has catapulted viable alternatives like Post-Quantum Cryptography (PQC) into prominence. The adoption and integration of standardized PQC primitives across the entire digital stack are promoted by various standardization bodies, governments, and major corporate houses. A serious challenge in quantum migration is to ensure that there is no hidden backdoor in the PQC implementations of a hybrid cryptosystem (support for both pre-quantum and post-quantum algorithms), which are often procured from a third-party vendor. In this manuscript, we investigate the possibility of a Kleptographic backdoor on the NIST-recommended key-encapsulation mechanism CRYSTALS-Kyber. The modified Kyber Key-Generation() algorithm achieves indistinguishable decryption failure probability compared to the original CRYSTALS-Kyber. The Kleptographic module is also implemented in FPGA, embedded inside the CRYSTALS-Kyber accelerator with a very low area overhead (283 LUTs or 2% of total area), and thus can easily pass performance and functionality tests.

In this work, we present a systematic study of Side-Channel Attacks (SCA) and Fault Injection Attacks (FIA) on structured lattice-based schemes, with main focus on Kyber Key Encapsulation Mechanism (KEM) and Dilithium signature scheme, which are leading candidates in the NIST standardization process for Post-Quantum Cryptography (PQC). Through our study, we attempt to understand the underlying similarities and differences between the existing attacks while classifying them into different categories. Given the wide variety of reported attacks, simultaneous protection against all the attacks requires to implement customized protections/countermeasures for both Kyber and Dilithium. We therefore present a range of customized countermeasures, capable of providing defenses/mitigations against existing SCA/FIA, and incorporate several SCA and FIA countermeasures within a single design of Kyber and Dilithium. Among the several countermeasures discussed in this work, we present novel countermeasures that offer simultaneous protection against several SCA- and FIA-based chosen-ciphertext attacks for Kyber KEM. We implement the presented countermeasures within two well-known public software libraries for PQC: (1) pqm4 library for the ARM Cortex-M4-based microcontroller and (2) liboqs library for the Raspberry Pi 3 Model B Plus based on the ARM Cortex-A53 processor. Our performance evaluation reveals that the presented custom countermeasures incur reasonable performance overheads on both the evaluated embedded platforms. We therefore believe our work argues for usage of custom countermeasures within real-world implementations of lattice-based schemes, either in a standalone manner or as reinforcements to generic countermeasures such as masking.

In an effort to circumvent the high cost of standard countermeasures against side-channel attacks in post-quantum cryptography, some works have developed low-cost detection-based countermeasures. These countermeasures try to detect maliciously generated input ciphertexts and react to them by discarding the ciphertext or secret key. In this work, we take a look at two previously proposed low-cost countermeasures: the ciphertext sanity check and the decapsulation failure check, and demonstrate successful attacks on these schemes. We show that the first countermeasure can be broken with little to no overhead, while the second countermeasure requires a more elaborate attack strategy that relies on valid chosen ciphertexts. Thus, in this work, we propose the first chosen-ciphertext based side-channel attack that only relies on valid ciphertexts for key recovery. As part of this attack, a third contribution of our paper is an improved solver that retrieves the secret key from linear inequalities constructed using side-channel leakage from the decryption procedure. Our solver is an improvement over the state-of-the-art Belief Propagation solvers by Pessl and Prokop, and later Delvaux. Our method is simpler, easier to understand and has lower computational complexity, while needing less than half the inequalities compared to previous methods.

In this work, we propose generic and novel adaptations to the binary Plaintext-Checking (PC) oracle based side-channel attacks for Kyber KEM. These attacks operate in a chosen-ciphertext setting, and are fairly generic and easy to mount on a given target, as the attacker requires very minimal information about the target device. However, these attacks have an inherent disadvantage of requiring a few thousand traces to perform full key recovery. This is due to the fact that these attacks typically work by recovering a single bit of information about the secret key per query/trace. In this respect, we propose novel parallel PC oracle based side-channel attacks, which are capable of recovering a generic P number of bits of information about the secret key in a single query/trace. We propose novel techniques to build chosen-ciphertexts so as to efficiently realize a parallel PC oracle for Kyber KEM. We also build a multi-class classifier, which is capable of realizing a practical side-channel based parallel PC oracle with very high success rate. We experimentally validated the proposed attacks (upto P = 10) on the fastest implementation of unprotected Kyber KEM in the pqm4 library. Our experiments yielded improvements in the range of 2.89× and 7.65× in the number of queries, compared to state-of-the-art binary PC oracle attacks, while arbitrarily higher improvements are possible for a motivated attacker, given the generic nature of the proposed attacks. We further conduct a thorough study on applicability to different scenarios, based on the presence/absence of a clone device, and also partial key recovery. Finally, we also show that the proposed attacks are able to achieve the lowest number of queries for key recovery, even for implementations protected with low-cost countermeasures such as shuffling. Our work therefore, concretely demonstrates the power of PC oracle attacks on Kyber KEM, thereby stressing the need for concrete countermeasures such as masking for Kyber and other lattice-based KEMs.

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.

In this work, we propose generic and practical side-channel attacks for message recovery in post-quantum lattice-based public key encryption (PKE) and key encapsulation mechanisms (KEM). The targeted schemes are based on the well known Learning With Errors (LWE) and Learning With Rounding (LWR) problem and include three finalists and six semi-finalist candidates of the ongoing NIST’s standardization process for post-quantum cryptography. Notably, we propose to exploit inherent ciphertext malleability properties of LWE/LWR-based PKEs as a powerful tool for side-channel assisted message recovery attacks. The use of ciphertext malleability widens the scope of previous attacks with the ability to target multiple operations for message recovery. Moreover, our attacks are adaptable to different implementation variants and are also applicable to implementations protected with concrete shuffling and masking side-channel countermeasures. Our work mainly highlights the presence of inherent algorithmic properties in LWE/LWR-based schemes that can aid side-channel attacks for message recovery, thereby stressing on the need for strong side-channel countermeasures against message recovery for LWE/LWR-based schemes.

Public-key cryptography is an indispensable component used in almost all of our present-day digital infrastructure. However, most if not all of it is predominantly built upon hardness guarantees of number theoretic problems that can be broken by large-scale quantum computers in the future. Sensing the imminent threat from continued advances in quantum computing, NIST has recently initiated a global-level standardization process for quantum resistant public-key cryptographic primitives such as public-key encryption, digital signatures, and key encapsulation mechanisms. While the process received proposals from various categories of post-quantum cryptography, lattice-based cryptography features most prominently among all the submissions. Lattice-based cryptography offers a very attractive alternative to traditional public-key cryptography mainly due to the variety of lattice-based schemes offering varying flavors of security and efficiency guarantees. In this article, we survey the evolution of lattice-based key-sharing schemes (public-key encryption and key encapsulation schemes) and cover various aspects ranging from theoretical security guarantees, general algorithmic frameworks, practical implementation aspects, and physical attack security, with special focus on lattice-based key-sharing schemes competing in the NIST’s standardization process.