Theoretical Linear Cryptanalysis of the 5G Standard Candidate SNOW 5G

Abstract

In this paper, we perform linear cryptanalysis of the stream cipher SNOW 5G, which is recommended by the international standardization group (SAGE) as one standard algorithm for 5G confidentiality and integrity protection over the wireless channel. SNOW 5G can be regarded as one member of the SNOW-V family, as it is modified from SNOW-Vi by SAGE with a slight improvement. As an overall contribution, we provide a comprehensive and elaborate theoretical analysis of linear approximations of SNOW 5G and provide the best public cryptanalysis result by far. Specifically, we first theoretically analyze the formats of linear masks of SNOW5G that can introduce high correlations, and then search for high-quality linear masks using a divide-and-conquer method based on the different cases of a critical intermediate linear mask. We find a linear approximation of SNOW 5G with correlation −2^−67.67 and further launch a correlation attack against it with complexity 2^279.8, improving the existing best correlation attack by a factor of 2^32.4. Our results are mainly from theoretical analysis, which involve little computation overhead and help to better understand the security of SNOW 5G.