Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly
Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly
复制标题
DOI：
10.1109/tc.2019.2909871
复制
发表时间：
2018-08
影响因子：
3.7
通讯作者：
Yonglin Hao;Takanori Isobe;Lin Jiao;Chaoyun Li;W. Meier;Yosuke Todo;Qingju Wang
中科院分区：
文献类型：
--
作者：
Yonglin Hao;Takanori Isobe;Lin Jiao;Chaoyun Li;W. Meier;Yosuke Todo;Qingju Wang
在 CRYPTO 2017 和 IEEE Transactions on Computers 2018 上，Todo 等人。提出了基于划分属性的立方体攻击方法，使得发起立方体维度远远超出实际范围的立方体攻击成为可能。然而，做出假设是为了验证他们的攻击。在本文中，我们在一个框架中进一步阐述了超多态的代数性质，以促进立方体攻击在更成功的应用中的应用：我们提出了“标志”技术来提高 MILP 模型的精度，这使我们能够识别正确的非立方体 IV 分配；提出了一种度评估算法来确定超多态度的上限。无需构建整个真值表就可以恢复超级多态性，并且可以大大降低攻击的整体复杂性；我们为 Trivium 类流密码（即 Trivium、Kreyvium、TriviA-SC1/2）提供分而治之的策略，以便将大型 MILP 模型拆分为几个小的可解模型，使我们能够通过超过 1000 轮初始化来分析 Trivium 类原语；最后，我们提供了一种求超多项式单项式的项枚举算法，从而可以进一步降低许多攻击的复杂度。我们应用我们的技术来攻击几个密码的初始化，分别是 839 轮 Trivium、891 轮 Kreyvium、1009 轮 TriviA-SC1、1004 轮 TriviA-SC2、184 轮 Grain-128a 和 750 轮 Acorn。
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.