Correlation Attacks on SNOW-V-Like Stream Ciphers Based on a Heuristic MILP Model
Sudong Ma, Chenhui Jin, Zhen Yu Shi, Ting Cui, Jie Guan · IEEE Transactions on Information Theory · 2023
SNOW-V and SNOW-Vi are two new LFSR-based stream ciphers of the SNOW family designed for the 5G mobile communication system. Correlation attack is a well-known cryptanalysis tool for LFSR-based stream ciphers. The first step of a correlation attack is to establish a linear approximation of the cipher with high correlation. The process can be modeled and solved by automatic techniques. How to efficiently model the 8-bit S-box and how to give an effective search strategy are two challenges to automatically search for linear approximations of SNOW-V-like ciphers. For the first problem, we propose a divide-and-conquer dimension reduction method for modeling large S-boxes with Mixed Integer Linear Programming (MILP). It can transform the problem of modeling a high-dimensional set into sub-problems of modeling some low-dimensional sets. For the second problem, we propose an efficient heuristic MILP search algorithm for SNOW-V-like ciphers, which is applied to searching for the linear approximations of SNOW-V, SNOW-Vi, SNOW-Vi⊞32,⊞8, SNOW-Vi⊞16,⊞16and SNOW-Viσ0ciphers with high absolute correlations. Then we get the best absolute correlations of these ciphers at present, where the linear approximation of SNOW-Vi with the absolute correlation 2-45.796improves the absolute correlation 2-47.76proposed at EUROCRYPT 2022 by Shi et al. and the absolute correlation 2-47.567proposed at DCC 2022 by Zhou et al. Thus, a correlation attack with time/data/memory complexity of 2243.79/2235.08/2235.08is got. It is also the best state recovery attack at present. Thirdly, to simplify the search algorithm of the linear approximations of SNOW-V, we give two sufficient conditions under which a linear approximation of SNOW-Vi is also a linear approximation of SNOW-V. It can be proved that the correlation attack on SNOW-V has the same attack complexity as SNOW-Vi. Finally, for SNOW-Vi⊞32,⊞8and SNOW-Viσ0, we give the best state recovery attacks so far. The current best state recovery attacks of SNOW-Vi⊞32,⊞8and SNOW-Viσ0can be reduced by a factor of 264and 262, respectively. We also give the first attack on SNOW-Vi⊞16,⊞16. We emphasize that the new heuristic MILP model can be applied to the security evaluation of correlation attacks on the LFSR-based stream cipher structures. In addition, note that the existing fast correlation attacks, including our attacks do not threaten the security of SNOW-V-like ciphers because of the design constraint that the maximum length of keystream for a single pair of key and IV vectors is 264.