Paper 2021/1607 Original: eprint.iacr.org/2021/1607 ↗

Efficient and Extensive Search Linear Approximations with High for Precise Correlations of Full SNOW-V

Abstract

SNOW-V is a stream cipher recently designed for 5G communication system. In this paper, we propose two efficient algorithms to evaluate the precise correlation of SNOW-V's two main nonlinear components with linear hull effects fully considered. Based on these algorithms, we could efficiently and extensively search much more linear masks than before. The ideas of these algorithms can be generalized to other similar nonlinear components in symmetric cipher. We apply our algorithms to full SNOW-V to search different types of linear approximations with high correlations. Our results depict more linear approximations with higher correlations than those proposed for full SNOW-V and SNOW-$\text{V}_{\boxplus_{32},\boxplus_8}$ recently. The best linear approximation we found has absolute correlation $2^{-47.567}$. There are at least 8, 135 and 1092 linear approximations with absolute correlation greater than $2^{-47.851}$, $2^{-49}$ and $2^{-50}$ respectively, which would derive a fast correlation attack with time/memory/data complexities $2^{240.86}$, $2^{240.37}$ and $2^{236.87}$. It is better than all the previous results of fast correlation attack against full SNOW-V. Moreover, we propose some properties for linear trails with 3 active S-boxes, which give a theoretical explanation that automatic search method lacks of. Our work provides a more comprehensive description for the linear approximation properties of full SNOW-V.