Correlation Attacks on SNOW-V-Like Stream Ciphers Based on a Heuristic MILP Model

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
$_{\boxplus _{32},\boxplus _{8}}$
, SNOW-Vi
$_{\boxplus _{16},\boxplus _{16}}$
and SNOW-Vi
$_{\sigma _{0}}$
ciphers 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.796}$
improves the absolute correlation
$2^{-47.76}$
proposed at EUROCRYPT 2022 by Shi et al. and the absolute correlation
$2^{-47.567}$
proposed at DCC 2022 by Zhou et al. Thus, a correlation attack with time/data/memory complexity of
$2^{243.79}/2^{235.08}/2^{235.08}$
is 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
$_{\boxplus _{32},\boxplus _{8}}$
and SNOW-Vi
$_{\sigma _{0}}$
, we give the best state recovery attacks so far. The current best state recovery attacks of SNOW-Vi
$_{\boxplus _{32},\boxplus _{8}}$
and SNOW-Vi
$_{\sigma _{0}}$
can be reduced by a factor of 264 and 262, respectively. We also give the first attack on SNOW-Vi
$_{\boxplus _{16},\boxplus _{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.