Cube Cryptanalysis of Round-Reduced ACORN
Cube Cryptanalysis of Round-Reduced ACORN
复制标题
DOI：
10.1007/978-3-030-30215-3_3
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Jingchun Yang;Meicheng Liu;D. Lin
中科院分区：
文献类型：
--
作者：
Jingchun Yang;Meicheng Liu;D. Lin
立方体攻击是对对称密码原语进行密码分析的最有效的技术之一。立方体攻击的基本思想是通过对立方体（公共变量的子集，例如，明文位或IV位）。本文利用立方体密码分析方法对CAESAR竞赛决赛的6个算法之一的认证流密码ACORN进行了分析，给出了区分攻击和密钥恢复攻击的一些新结果。首先，我们给出了一种新的立方体测试器的寻找方法，该方法基于贪婪立方体寻找算法，并利用数值映射方法估计基于NFSR密码系统的代数次数。我们将其应用于ACORN，并获得最佳的实用区分攻击，其690轮的变体使用的立方体大小为38，其706轮的变体使用的立方体大小为46。然后，我们从理论上分析了ACORN的安全界限，基于分割性质的立方体攻击。通过利用嵌入性质，我们找到了一些新的ACORN算法，因此其775轮变体的输出的零和性质可以被观察到，复杂度为。最后，我们提出了一个密钥恢复攻击ACORN减少到772轮。恢复123维立方体的线性超多边形的时间复杂度为。据我们所知，这是对轮减ACORN的最佳密钥恢复攻击。值得注意的是，这项工作并没有威胁到ACORN的安全。
The cube attack is one of the most powerful techniques in cryptanalysis of symmetric cryptographic primitives. The basic idea of cube attack is to determine the value of a polynomial in key bits by summing over a cube (a subset of public variables,e.g., plaintext bits or IV bits). If the degree of the polynomial is relatively low, then we can obtain a low-degree equation in key bits, thus may contribute to reducing the complexity of key recovery.In this paper, we use cube cryptanalysis to analyze the authenticated stream cipher ACORN (one of the 6 algorithms in the final portfolio of the CAESAR competition), and give some new results in both distinguishing attacks and key recovery attacks. Firstly, we give a new method of finding cube testers, which is based on the greedy algorithm of finding cubes, and the numeric mapping method for estimating the algebraic degree of NFSR-based cryptosystems. We apply it to ACORN, and obtain the best practical distinguishing attacks for its 690-round variant using a cube of size 38, and its 706-round variant using a cube of size 46. Then we theoretically analyze the security bound of ACORN via the division property based cube attack. By exploiting the embedded property, we find some new distinguishers for ACORN, so the zero-sum property of the output of its 775-round variant can be observed with a complexity of. Finally, we propose a key recovery attack on ACORN reduced to 772 rounds. The time complexity to recover the linear superpoly of the 123-dimensional cube is. As far as we know, this is the best key recovery attack on round-reduced ACORN. It is also worth noting that this work does not threaten the security of ACORN.