Resistance of SNOW-V against Fast Correlation Attacks

Abstract

SNOW-V is a new member in the SNOW family of stream ciphers, hoping to be competitive in the 5G mobile communication system. In this paper, we study the resistance of SNOW-V against bitwise fast correlation attacks by constructing bitwise linear approximations. First, we propose and summarize some efficient algorithms using the slice-like techniques to compute the bitwise linear approximations of certain types of composition functions composed of basic operations like ⊞, ⊕, Permutation, and S-box, which have been widely used in word-oriented stream ciphers such as SNOW-like ciphers. Then, using these algorithms, we find a number of stronger linear approximations for the FSM of the two variants of SNOW-V given in the design document, i.e., SNOW-V _σ0 and SNOW-V_{⊞8, ⊞8}. For SNOW-V _σ0, where there is no byte-wise permutation, we find some bitwise linear approximations of the FSM with the SEI (Squared Euclidean Imbalance) around 2^−37.34 and mount a bitwise fast correlation attack with the time complexity 2^251.93 and memory complexity 2²⁴⁴, given 2^103.83 keystream outputs, which improves greatly the results in the design document. For SNOW-V_{⊞8, ⊞8}, where both of the two 32-bit adders in the FSM are replaced by 8-bit adders, we find our best bitwise linear approximations of the FSM with the SEI 2^−174.14, while the best byte-wise linear approximation in the design document of SNOW-V has the SEI 2−214.80. Finally, we study the security of a closer variant of SNOW-V, denoted by SNOW-V_{⊞32, ⊞8}, where only the 32-bit adder used for updating the first register is replaced by the 8-bit adder, while everything else remains identical. For SNOW-V_{⊞32, ⊞8}, we derive many mask tuples yielding the bitwise linear approximations of the FSM with the SEI larger than 2⁻¹⁸⁴. Using these linear approximations, we mount a fast correlation attack with the time complexity 2^377.01 and a memory complexity 2³⁶³, given 2^253.73 keystream outputs. Note that neither of our attack threatens the security of SNOW-V. We hope our research could further help in understanding bitwise linear approximation attacks and also the structure of SNOW-like stream ciphers.