Paper 2021/123

A Systematic Approach and Analysis of Key Mismatch Attacks on CPA-Secure Lattice-Based NIST Candidate KEMs

Yue Qin and Chi Cheng and Xiaohan Zhang and Yanbin Pan and Lei Hu and Jintai Ding

Abstract

Most submitted lattice-based key encapsulation mechanisms (KEMs) on the second or third round list of the NIST standardization follow a similar structure: First a CPA secure scheme is constructed, which is then converted to a CCA secure one. The research of the key reuse attacks against the CPA secure ones is important in two folds: First, it is an important part of the cryptographic assessment of the ongoing NIST standardization. Secondly, it helps the design of CCA-secure authenticated key exchange directly from LWE, without FO transform. There have been a number of key mismatch attacks on these CPA secure versions when the public key is reused. However, a unified method to evaluate their resilience under key mismatch attacks is still missing. Since the key index of the efficiency of these attacks is the number of queries (matches and mismatches) needed to successfully mount such an attack, in this paper, we propose and develop a systematic approach to find the lower bounds on the minimum average number of queries needed for such attacks. Our basic idea is to transform the problem of finding the lower bound of queries into finding an optimal binary recovery tree (BRT), where the computations of the lower bounds become essentially the computations of certain Shannon entropy. The approach means that one cannot find a better attack with fewer queries than this lower bound. The introduction of the optimal BRT approach enables us to understand why, for some schemes, there is a big gap between the theoretical bounds and practical attacks, in terms of the number of queries needed. This further leads us to improve the existing attacks. Especially, we can reduce the needed queries against Frodo640 by 71.99% , LAC256 by 82.81%, and Newhope1024 by 97.44%.