Paper 2021/544

New improved attacks on SNOW-V

Jing Yang and Thomas Johansson and Alexander Maximov

Abstract

In this paper, we investigate the security of SNOW-V, the new member of the SNOW family proposed in response to the new requirements of confidentiality and integrity protection in 5G. Specifically, we demonstrate two guess-and-determine (GnD) attacks against the full SNOW-V with complexities $2^{384}$ and $2^{378}$ using seven and eight keystream words, respectively, and one distinguishing attack against a reduced variant with complexity $2^{303}$. Our guess-and-determine attacks use enumeration with recursion to explore valid guessing paths, and try to truncate as many guessing paths as possible on early stages of the recursion by carefully designing the order of guessing, and fully exploiting the equation constraints. In our first GnD attack, we guess three 128-bit state variables, and determine the other three using three consecutive keystream words. We use a fourth keystream word to efficiently enumerate solutions of the last state variable and the next three for verification of the correct guess. The second GnD attack is similar but exploits one more keystream word as a side information to truncate more guessing paths. In our distinguishing attack, we consider a reduced version where all 32-bit adders are replaced with exclusive-OR and find a 16-bit linear approximation with the SEI bias $2^{-303}$ using three consecutive keystream words. The main advantage of our distinguishing attack is that we can cancel out the contribution from the linear part locally, without a need to combine keystream words very far away, which is typically required in a classical distinguishing attack against stream ciphers. Thus we are able to give a distinguishing attack requiring $2^{303}$ samples, while these samples can be collected from multiple short keystreams under different (Key, IV) pairs. These attacks do not threaten SNOW-V, but provide more in-depth details for understanding its security and give new ideas for cryptanalysis of other ciphers.