International Association
for Cryptologic Research

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 2279.8, improving the existing best correlation attack by a factor of 232.4. Our results are mainly from theoretical analysis, which involve little computation overhead and help to better understand the security of SNOW 5G.

In this paper, we revisit the division property based dynamic cube attack on the full Grain-128 presented by Hao et al. at FSE 2020 and demonstrate that their attack on the full Grain-128 is invalid, that is, no key information could be successfully recovered. The theoretical framework for the dynamic cube attack provided by Hao et al. is correct, but the technique for building the MILP model in the dynamic cube attack has flaws. Besides, strong evidence indicates that their bias estimation method is not applicable to Grain-128AEAD and Grain-128. Accordingly, we introduce the three-subset division property without unknown subset (3SDP/u) into dynamic cube attacks and present a correct MILP modeling technique. In addition, we propose a heuristic technique called Polynomial Approximation with regard to Bias (PAB) to evaluate the bias in superpolies in the dynamic cube attack, which can provide a more accurate bias evaluation for high-dimension cubes. As a result, we implemented the dynamic cube attack based on 3SDP/u on 190-round Grain-128AEAD, and we could recover 3 key bits with a complexity 2103.44 and the success probability was evaluated to be 99.68%. For Grain-128, some zero-sum distinguishers of cube size 80 are given for the first time.

The cube attack is one of the most important cryptanalytic techniques against Trivium. Many key-recovery attacks based on cube attacks have been established. However, few attacks can recover the 80-bit full key information practically. In particular, the previous best practical key-recovery attack was on 784-round Trivium proposed by Fouque and Vannet at FSE 2013. To mount practical key-recovery attacks, it requires a sufficient number of low-degree superpolies. It is difficult both for experimental cube attacks and division property based cube attacks with randomly selected cubes due to lack of efficiency. In this paper, we give a new algorithm to construct candidate cubes targeting linear superpolies. Our experiments show that the success probability is 100% for finding linear superpolies using the constructed cubes. We obtain over 1000 linear superpolies for 805-round Trivium. With 42 independent linear superpolies, we mount a practical key-recovery attack on 805-round Trivium, which increases the number of attacked rounds by 21. The complexity of our attack is $ 2^{41.40} $, which could be carried out on a PC with a GTX-1080 GPU in several hours.

Cube attacks are an important type of key recovery attacks against stream ciphers. In particular, they are shown to be powerful against Trivium-like ciphers. Traditional cube attacks are experimental attacks which could only exploit cubes of size less than 40. At CRYPTO 2017, division property based cube attacks were proposed by Todo et al., and an advantage of introducing the division property to cube attacks is that large cube sizes which are beyond the experimental range could be explored, and so powerful theoretical attacks were mounted on many lightweight stream ciphers.In this paper, we revisit the division property based cube attacks. There is an important assumption, called Weak Assumption, proposed in division property based cube attacks to support the effectiveness of key recovery. Todo et al. in CRYPTO 2017 said that the Weak Assumption was expected to hold for theoretically recovered superpolies of Trivium according to some experimental results on small cubes. In this paper, it is shown that the Weak Assumption often fails in cube attacks against Trivium, and moreover a new method to recover the exact superpoly of a given cube is developed based on the bit-based division property. With our method, for the cube I proposed by Todo et al. at CRYPTO 2017 to attack the 832-round Trivium, we recover its superpoly pI (x, v) = v68v78 · (x58⊕v70) · (x59x60⊕x34⊕x61). Furthermore, we prove that some best key recovery results given at CRYPTO 2018 on Trivium are actually distinguishing attacks. Hopefully this paper gives some new insights on accurately recovering the superpolies with the bit-based division property and also attract some attention on the validity of division property based cube attacks against stream ciphers.