Paper 2019/1343

An Efficient Key Mismatch Attack on the NIST Second Round Candidate Kyber

Yue Qin, Chi Cheng, and Jintai Ding

Abstract

Kyber is a KEM based their security on the Modular Learning with Errors problem and was selected in the second round of NIST Post-quantum standardization process. Before we put Kyber into practical application, it is very important to assess its security in hard practical conditions especially when the Fujisaki-Okamoto transformations are neglected. In this paper, we propose an efficient key mismatch attacks on Kyber, which can recover one participant's secret key if the public key is reused. We first define the oracles in which the adversary is able to launch the attacks. Then, we show that by accessing the oracle multiple times, the adversary is able to recover the coefficients in the secret key. Furthermore, we propose two strategies to reduce the queries and time in recovering the secret key. It turns out that it is actually much easier to use key mismatch attacks to break Kyber than NewHope, another NIST second round candidate, due to their different design structures. Our implementations have demonstrated the efficiency of the proposed attacks and verified our findings. Another interesting observation from the attack is that in the most powerful Kyber-1024, it is easier to recover each coefficient compared with that in Kyber-512 and Kyber-768. Specifically, for Kyber-512 on average we recover each coefficient with $2.7$ queries, while in Kyber-1024 and 768, we only need $2.4$ queries. This demonstrates further that implementations of LWE based schemes in practice is very delicate.