Paper Info
Title
Improved Division Property Based Cube Attacks Exploiting Algebraic Properties Of Superpoly
Abstract
At CRYPTO 2017 and IEEE Transactions on Computers in 2018, Todo et al. proposed the division property based cube attack method making it possible to launch cube attacks with cubes of dimensions far beyond practical reach. However, assumptions are made to validate their attacks. In this paper, we further formulate the algebraic properties of the superpoly in one framework to facilitate cube attacks in more successful applications: we propose the "flag" technique to enhance the precision of MILP models, which enable us to identify proper non-cube IV assignments; a degree evaluation algorithm is presented to upper bound the degree of the superpoly s.t. the superpoly can be recovered without constructing its whole truth table and overall complexity of the attack can be largely reduced; we provide a divide-and-conquer strategy to TRIVIUM-like stream ciphers namely TRIVIUM, Kreyvium, TriviA-SC1/2 so that the large scale MILP models can be split into several small solvable ones enabling us to analyze TRIVIUM-like primitives with more than 1000 initialization rounds; finally, we provide a term enumeration algorithm for finding the monomials of the superpoly, so that the complexity of many attacks can be further reduced. We apply our techniques to attack the initialization of several ciphers namely 839-round TRIVIUM, 891-round Kreyvium, 1009-round TriviA-SC1, 1004-round TriviA-SC2, 184-round Grain-128a and 750-round ACORN respectively.
Year
DOI
Venue
2019
10.1109/TC.2019.2909871
IEEE TRANSACTIONS ON COMPUTERS
Keywords
DocType
Volume
Cube attack, division property, milp, TRIVIUM, kreyvium, grain-128a, ACORN, TriviA-SC1/2
Journal
68
Issue
ISSN
Citations 
10
0018-9340
0
PageRank 
References 
Authors
0.34
0
7
Name
Order
Citations
PageRank
Yonglin Hao1132.28
Takanori Isobe242139.28
Lin Jiao344.27
Chaoyun Li4266.77
Willi Meier5155.73
Yosuke Todo616019.09
Qingju Wang711610.73