Paper 2019/381

Revisit Division Property Based Cube Attacks: Key-Recovery or Distinguishing Attacks?

Chen-Dong Ye and Tian Tian

Abstract

Cube attacks are an important type of key recovery attacks against stream ciphers. In particular, it is 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 to 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, based on some new techniques to remove invalid division trails, some best key recovery results given at CRYPTO 2017 and CRYPTO 2018 on Trivium are proved to be distinguishers. First, we build a relationship between the bit-based division property and the algebraic degree evaluation on a set of active variables. Second, based on our algebraic point of view, we propose a new variant of division property which incorporates the distribution of active variables. Third, a new class of invalid division trails are characterized and new techniques based on MILP models to remove them are proposed. Hopefully this paper could give some new insights on accurately evaluating the propagation of the bit-based division property and also attract some attention on the validity of division property based cube attacks against stream ciphers.