Pairwise and Parallel: Enhancing the Key Mismatch Attacks on Kyber and Beyond
Open Access
- 1 July 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 548-559
Abstract
Misuse resilience is an important research topic in the NIST PQC standardization process. Key mismatch attacks are a major type of misuse attack. In key mismatch attacks, the adversary aims to recover the reused secret key by sending special 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. The strategy is to recover partial information about multiple coefficient-pairs of the secret key in a parallel way per query. We realize the multi-value key mismatch oracle in a 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 of 232. 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 of Kyber1024 with a lattice reduction cost of 232. Moreover, our proposed pairwise-parallel attack method can be applied to improve the PC oracle-based SCA against CCA-secure Kyber, reducing the number of queries/traces by 16.67%. Futhermore, the proposed attacks can be applied to Saber and other lattice-based KEMs.Keywords
Funding Information
- National Key R&D Program of China (2022YFB3103800)
- National Natural Science Foundation of China (U1936209, 62002353, 62202231, 62202230)
- China Post- doctoral Science Foundation (2021M701726)
- Jiangsu Funding Program for Excellent Postdoctoral Talent (2022ZB270)
This publication has 20 references indexed in Scilit:
- Status report on the third round of the NIST Post-Quantum Cryptography Standardization process2022
- Timing Attacks on Error Correcting Codes in Post-Quantum Schemes2019
- A Complete and Optimized Key Mismatch Attack on NIST Candidate NewHope2019
- Misuse Attacks on Post-quantum Cryptosystems2019
- Assessment of the Key-Reuse Resilience of NewHope2019
- Algorithms for quantum computation: discrete logarithms and factoring2002
- Secure Integration of Asymmetric and Symmetric Encryption Schemes1999
- A modification to the half-interval search (binary search) method1976
- Nearly optimal binary search treesActa Informatica, 1975
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952