Comparing Large-unit and Bitwise Linear Approximations of SNOW 2.0 and SNOW 3G and Related Attacks

Abstract

In this paper, we study and compare the byte-wise and bitwise linear approximations of SNOW 2.0 and SNOW 3G, and present a fast correlation attack on SNOW 3G by using our newly found bitwise linear approximations. On one side, we reconsider the relation between the large-unit linear approximation and the smallerunit/ bitwise ones derived from the large-unit one, showing that approximations on large-unit alphabets have advantages over all the smaller-unit/bitwise ones in linear attacks. But then on the other side, by comparing the byte-wise and bitwise linear approximations of SNOW 2.0 and SNOW 3G respectively, we have found many concrete examples of 8-bit linear approximations whose certain 1-dimensional/bitwise linear approximations have almost the same SEI (Squared Euclidean Imbalance) as that of the original 8-bit ones. That is, each of these byte-wise linear approximations is dominated by a single bitwise approximation, and thus the whole SEI is not essentially larger than the SEI of the dominating single bitwise approximation. Since correlation attacks can be more efficiently implemented using bitwise approximations rather than large-unit approximations, improvements over the large-unit linear approximation attacks are possible for SNOW 2.0 and SNOW 3G. For SNOW 3G, we make a careful search of the bitwise masks for the linear approximations of the FSM and obtain many mask tuples which yield high correlations. By using these bitwise linear approximations, we mount a fast correlation attack to recover the initial state of the LFSR with the time/memory/data/pre-computation complexities all upper bounded by 2^174.16, improving slightly the previous best one which used an 8-bit (vectorized) linear approximation in a correlation attack with all the complexities upper bounded by 2^176.56. Though not a significant improvement, our research results illustrate that we have an opportunity to achieve improvement over the large-unit attacks by using bitwise linear approximations in a linear approximation attack, and provide a new
insight on the relation between large-unit and bitwise linear approximations.