Lattice Reduction Meets Key-Mismatch: New Misuse Attack on Lattice-Based NIST Candidate KEMs

Ruiqi Mi; Haodong Jiang; Zhenfeng Zhang

Paper 2022/1064

Lattice Reduction Meets Key-Mismatch: New Misuse Attack on Lattice-Based NIST Candidate KEMs

Ruiqi Mi

, University of Chinese Academy of Sciences

Haodong Jiang, Trusted Computing and Information Assurance Laboratory

Zhenfeng Zhang, Trusted Computing and Information Assurance Laboratory

Abstract

Resistance to key misuse attacks is a vital property for key encapsulation mechanisms（KEMs）in NIST-PQC standardization process. In key mismatch attack, the adversary recovers reused secret key with the help of an oracle $O$ that indicates whether the shared key matches or not. Key mismatch attack is more powerful when fewer oracle queries are required. A series of works tried to reduce query times, Qin et al. [AISACRYPT 2021] gave a systematic approach to finding lower bound of oracle queries for a category of KEMs, including NIST’s third-round candidate Kyber and Saber. In this paper, we found the aforementioned bound can be bypassed by combining Qin et al. (AISACRYPT 2021)’s key mismatch attack with a standard lattice attack. In particular, we explicitly build the relationship between the number of queries to the oracle and the bit security of the lattice-based KEMs. Our attack is inspired by the fact that each oracle query reveals partial information of reused secrets, and affects the mean and the covariance parameter of secrets, making the attack on lattice easier. In addition, We quantify such effect in theory and estimate the security loss for all NIST second-round candidate KEMs.Specifically, Our improved attack reduces the number of queries for Kyber512 by 34% from 1312 queries with bit security 107 to 865 with bit security 32. For Kyber768 and Kyber1024, our improved attack reduces the number of queries by 29% and 27% with bit security is 32.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Lattice-based cryptography KEM Key Misuse Attacks LWE LWR Kyber Saber Frodo Newhope
Contact author(s): ruiqi2017 @ iscas ac cn
haodong2020 @ iscas ac cn
zhenfeng @ iscas ac cn
History: 2022-08-17: approved; 2022-08-16: received; See all versions
Short URL: https://ia.cr/2022/1064
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1064,
      author = {Ruiqi Mi and Haodong Jiang and Zhenfeng Zhang},
      title = {Lattice Reduction Meets Key-Mismatch: New Misuse Attack on Lattice-Based {NIST} Candidate {KEMs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1064},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1064}
}