Physical attacks on CCA-Secure Lattice-based KEM SABER

Abstract

Nowadays the security of most used public-key algorithms are based on the hardness of one of the following problems : 1. The integer factorization, 2. The elliptic-curve discrete logarithm problem. But these problems can be solved by Shor's algorithm [38] and Proos.Zalka's algorithm [31] on a powerful quantum computer. The relief is that yet there is no quantum computer available. But from the continuous improvement of computer science, we can say that the quantum computer is coming within a few decades. Then to secure the communication, we need many cryptographic schemes, which are quantum secure. That is are not attacked by a powerful quantum computer. For this reason, post-quantum cryptographic schemes are needed. The lattice-based public-key cryptographic schemes Saber[15], Kyber[7], NTRU are secure against attacks from a quantum computer. These schemes are selected in the 3rd round by NIST in the Post Quantum Cryptography standardization program. The security of Saber is based on the Module Learning with Rounding (MLWR) problem [15], which is assumed to be computationally hard problem[2]. Saber.PKE is an IND-CPA secure scheme and can be transformed to a secure against chosenciphertext attacks( IND CCA-secure) by applying well known CCA conversions such as the Fujisaki Okamoto transform[19] . Now the remaining important task is to check the security of implementation of the scheme SABER. Because a perfectly secure scheme is broken if not implemented correctly. For example: RSA is a public-key encryption[17] whose security is based on the hardness of the prime factorization of a large number. We assume that the factorization of a large integer is a hard problem. Till now, there is no e cient factorizing method. But at the RSA Data Security and CRYPTO conferences in 1996, Kocher presented the "Timing Attack" on RSA . To secure a cryptographic scheme, we have to protect it from any possible attacks. Now for the protection, rst of all, we have to analyze the algorithm. And if we see that the scheme is mathematically secure, then we have to analyze the implemented scheme and nd all such i possible points, where we can inject a fault. Then we have to see that whether the injected fault leak some information about the secret. If some information leaks after injecting a fault in the implementation, then we have to put a countermeasure to prevent this fault attack. In this project, rst, we inject a fault in the decapsulation of the CCA secure scheme SABER. After that, we query the decapsulation oracle with constructed dummy ciphertexts ( which may not be valid ciphertext ), then using attack models, we recover the whole secret. To recover the secret, we need to query atmost 3072 number of constructed ciphertext to the decapsulation oracle for the parameter set (n = 256; l = 3; q = 213; p = 210; = 8) of SABER.