Key Recovery Attack on CRYSTALS-Kyber and Saber KEMs in Key Reuse Scenario

Crystals-Kyber, a key encapsulation mechanism (KEM) whose security is based on the Module-LWE problem, has recently been selected by NIST as part of its post-quantum cryptography initiative. At ASIACRYPT 2021, Qin et al. gave a method to evaluate the number of forged ciphertexts to recover a reused private key. For CPA-secure Kyber KEM, key mismatch attack is applied to get the first position of the decrypted message. However, for CCA-secure KEM, the Fujisaki-Okamoto transformation is used to detect the forged ciphertexts, thus, side channel techniques are necessary to get the first position of the decrypted message. Once the first position is obtained, the reused private key can be recovered. Using Qin et al.’s method the adversary should forge ciphertexts for several times, but the number of forged ciphertexts does not reach the Huffman bound. In this paper, we propose a generalized key mismatch attack based on dynamic chunking approach for CPA-secure Kyber KEM, and a new key recovery attack based on linear programming for CCA-secure Kyber KEM, where the number of forged ciphertexts reaches the Huffman bound. Meanwhile, the two approaches can also be applied to Saber KEM, which is the third round candidate scheme.