Modeling for Three-Subset Division Property without Unknown Subset
Modeling for Three-Subset Division Property without Unknown Subset
复制标题
DOI：
10.1007/s00145-021-09383-2
复制
发表时间：
2020-05
影响因子：
3
通讯作者：
Yonglin Hao;G. Leander;W. Meier;Yosuke Todo;Qingju Wang
中科院分区：
文献类型：
--
作者：
Yonglin Hao;G. Leander;W. Meier;Yosuke Todo;Qingju Wang
除法属性是搜索积分区分符的通用工具，而MILP或SAT/SMT等自动工具使我们能够有效地评估传播。在流密码的应用中，它使我们能够从理论上估计立方体攻击的安全性，并对已知的流密码进行最佳的密钥恢复攻击。然而，据报道，一些基于除法属性的密钥恢复攻击由于除法属性的不准确性而退化为区分攻击。三子集划分属性（无未知子集）是解决该不准确性问题的一种有前途的方法，最近在Asiacrypt2019上提出了一种使用自动工具进行三子集划分属性的新算法。在本文中，我们首先证明了这种最先进的算法并不总是有效的，并且我们不能改进现有的密钥恢复攻击。在此基础上，针对无未知子集的三子集分割特性，提出了一种新的基于自动工具的高效算法。我们的算法比现有的算法效率更高，并且可以改进现有的密钥恢复攻击。在trivium的应用程序中，我们展示了842轮密钥恢复攻击。我们还表明，在CRYPTO2018上提出的855轮密钥恢复攻击存在严重缺陷并且不起作用。因此，我们的842轮攻击成为最好的键恢复攻击。在Grain-128AEAD的应用中，我们展示了已知的184轮密钥恢复攻击退化为区分攻击。然后，将识别攻击提高到189发，并给出了190发时的最佳键恢复攻击。在acorn的应用中，我们证明了ISC2019上的772轮密钥恢复攻击实际上是一个常数和区分符。然后，我们给出了新的密钥恢复攻击，这些攻击增加到773-，774-和775-roundACORN。我们在892轮的Kreyvium上验证了当前最佳的键恢复攻击，并恢复了精确的超聚。我们进一步建议将攻击增加到893发。
A division property is a generic tool to search for integral distinguishers, and automatic tools such as MILP or SAT/SMT allow us to evaluate the propagation efficiently. In the application to stream ciphers, it enables us to estimate the security of cube attacks theoretically, and it leads to the best key-recovery attacks against well-known stream ciphers. However, it was reported that some of the key-recovery attacks based on the division property degenerate to distinguishing attacks due to the inaccuracy of the division property. Three-subset division property (without unknown subset) is a promising method to solve this inaccuracy problem, and a new algorithm using automatic tools for the three-subset division property was recently proposed at Asiacrypt2019. In this paper, we first show that this state-of-the-art algorithm is not always efficient and we cannot improve the existing key-recovery attacks. Then, we focus on the three-subset division property without unknown subset and propose another new efficient algorithm using automatic tools. Our algorithm is more efficient than existing algorithms, and it can improve existing key-recovery attacks. In the application toTrivium, we show a 842-round key-recovery attack. We also show that a 855-round key-recovery attack, which was proposed at CRYPTO2018, has a critical flaw and does not work. As a result, our 842-round attack becomes the best key-recovery attack. In the application to Grain-128AEAD, we show that the known 184-round key-recovery attack degenerates to a distinguishing attack. Then, the distinguishing attacks are improved up to 189 rounds, and we also show the best key-recovery attack against 190 rounds. In the application toACORN, we prove that the 772-round key-recovery attack at ISC2019 is in fact a constant-sum distinguisher. We then give new key-recovery attacks mounting to 773-, 774- and 775-roundACORN. We verify the current best key-recovery attack on 892-round Kreyvium and recover the exact superpoly. We further propose a new attack mounting to 893 rounds.