@article{Gong_Zhang_2021, title={Resistance of SNOW-V against Fast Correlation Attacks}, volume={2021}, url={https://tosc.iacr.org/index.php/ToSC/article/view/8843}, DOI={10.46586/tosc.v2021.i1.378-410}, abstractNote={<p>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 <em>bitwise</em> 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 ⊞, ⊕, <em>Permutation</em>, and <em>S-box</em>, 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<sub> σ0</sub> and SNOW-V<sub>⊞8, ⊞8</sub>. For SNOW-V<sub> σ0</sub>, where there is no byte-wise permutation, we find some bitwise linear approximations of the FSM with the SEI (Squared Euclidean Imbalance) around 2<sup>−37.34</sup> and mount a bitwise fast correlation attack with the time complexity 2<sup>251.93</sup> and memory complexity 2<sup>244</sup>, given 2<sup>103.83</sup> keystream outputs, which improves greatly the results in the design document. For SNOW-V<sub>⊞8, ⊞8</sub>, 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<sup>−174.14</sup>, 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<sub>⊞32, ⊞8</sub>, 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<sub>⊞32, ⊞8</sub>, we derive many mask tuples yielding the bitwise linear approximations of the FSM with the SEI larger than 2<sup>−184</sup>. Using these linear approximations, we mount a fast correlation attack with the time complexity 2<sup>377.01</sup> and a memory complexity 2<sup>363</sup>, given 2<sup>253.73</sup> 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.</p>}, number={1}, journal={IACR Transactions on Symmetric Cryptology}, author={Gong, Xinxin and Zhang, Bin}, year={2021}, month={Mar.}, pages={378-410} }