Tags:Cube attack, Division property, Grain-128AEAD, MILP and Three-subset division property
Abstract:
The cube attack is a powerful cryptanalytic technique against stream ciphers. Cube attacks exploit the algebraic properties of symmetric ciphers by recovering a particular polynomial, the superpoly, and subsequently, the secret key. Nowadays, the division property based approach has become very popular, allowing us to recover the exact superpoly cleverly. However, the computational cost to recover the superpoly becomes prohibitive as the number of rounds of the cipher increases. In this paper, we study NIST lightweight 3rd round candidate Grain-128AEAD in the light of division property-based cube attacks. We first introduce some good cubes of dimensions 91, 92, 93, 94, and then we construct an algorithm to find conditional key bits for the cubes of Grain-128AEAD mentioned above. Next, we apply three subset division property-based cube attacks without unknown subsets to recover exact superpolies for 192, 193, 194, 195-round Grain-128AEAD in the weak-key setting, which are the longest till now. Moreover, we are able to find good cubes that are used to build distinguishers of Grain-128AEAD in the weak-key setting. In particular, we show that Grain-128AEAD can be distinguished from a random source up to 193-rounds in the weak-key setting, which is the best zero-sum distinguisher of Grain-128AEAD till now using division property-based cube attacks.
Superpoly Recovery of Grain-128AEAD Using Division Property