Paper 2023/887

Pairwise and Parallel: Enhancing the Key Mismatch Attacks on Kyber and Beyond

Abstract

Key mismatch attacks resilience is a great concern for KEMs in the NIST PQC standardization process. In key mismatch attacks, the adversary aims to recover the reused key by sending special form of ciphertexts to the target party and observing whether the shared key matches his guesses or not. In this paper, we propose pairwise-parallel key mismatch attacks on Kyber and other lattice-based KEMs. The strategy is to recover partial information about multiple secret key coefficient-pairs in a parallel way per query. We realize the required multi-value key mismatch oracle in a simple key exchange scenario and experimentally validate our proposed attacks. Our attacks greatly reduce the number of queries required to recover the full secret key. Specifically, compared with state-of-the-art key mismatch attacks on CPA-secure Kyber, our attacks reduce the number of queries by 95% with computational complexity $2^{32}$. Then we employ the post-processing with lattice reduction to further minimize the number of queries. The results show we only need 78 queries to recover the full secret key with a lattice reduction cost of $2^{32}$. Moreover, our proposed pairwise-parallel attack method can be directly applied to enhance the PC oracle-based SCA against CCA-secure Kyber, reducing the number of queries/traces by 16.67%.