| 摘要: |
| 线性密码分析是分组密码算法重要的统计分析方法之一。自从20世纪90年代初Matsui提出线性密码分析以来,很多学者已经对线性密码分析及其推广的各种线性分析进行了大量的研究,辉煌的成果不计其数,其中多维线性密码分析就是一种极其重要的研究成果。线性密码分析利用正确密钥和错误密钥下线性逼近的相关系数的平方服从具有不同期望值的Gamma分布来恢复密钥。多维线性密码分析使用了线性子空间中所有的非零线性逼近,通过组合多个Gamma分布来扩大正确密钥和错误密钥下容量的差异,从而提高了密钥恢复攻击的效率。而线性子空间中的线性逼近对容量的贡献大小不一样,贡献较小的线性逼近对提高密钥恢复攻击效率起的作用较小。为此,Nyberg提出了仿射线性密码分析,它是多维线性密码分析的一个新的变体。仿射线性密码分析舍弃了多维线性子空间中对容量贡献较小或者没有贡献的一半线性逼近,仅从保留的仿射子空间提取信息,构造了更有效的卡方检验统计量对分组密码进行攻击。为了进一步提高攻击的效率,Nyberg猜想舍弃仿射统计量中得分较小的项,利用剩余项仍可以构造服从卡方分布的统计检验统计量。本文利用统计手段证明了Nyberg猜想是正确的,并给出了该猜想的一个应用方法。最后,利用PRESENT和Serpent算法验证了Nyberg模型的有效性。对26轮PRESENT,利用Nyberg猜想进行了数据复杂度为261.5,时间复杂度为268.37的密钥恢复攻击;对27轮PRESENT,可以利用Nyberg猜想进行数据复杂度为263.25,时间复杂度为268.37的密钥恢复攻击。另外,分析了4轮Serpent算法仿射线性密码分析的数据复杂度。 |
| 关键词: 多维线性分析 仿射线性分析 PRESENT |
| DOI：10.19363/J.cnki.cn10-1380/tn.2026.05.17 |
| 投稿时间：2021-03-11修订日期：2021-04-27 |
| 基金项目:本课题得到国家自然科学基金(No.61379138)资助。 |
|
| Affine Linear Cryptanalysis of Block Cipher |
|
CAO Wenqin1,2,3, ZHANG Wentao1,2
|
| (1.State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;2.School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China;3.School of Mathematics and Statistics, Shandong University of Technology, Zibo 255000, China) |
| Abstract: |
| Linear cryptanalysis is one of the important statistical cryptanalytic methods for block ciphers. Since the early 1990s, Matsui proposed linear cryptanalysis, and many scholars have researched the properties of linear cryptanalysis and proposed all kinds of promotion methods based on linear cryptanalysis. They have obtained numerous brilliant achievements. Among them, multidimensional linear cryptanalysis is a kind of extremely important method. Under the right and wrong keys, the squared correlation of a linear approximation has Gamma distributions with different means. Based on this property, linear cryptanalysis can perform recovery key attacks. Multidimensional linear cryptanalysis uses all non-zero linear approximations in linear subspace and combines multiple Gamma distributions to amplify the difference in capacity between right and wrong keys. Therefore, multidimensional linear cryptanalysis improves the efficiency of the key recovery attacks. In linear subspace, the contributions of the linear approximations to the capacity are different, and the one with a smaller contribution plays a smaller role in improving the efficiency of the attacks. In this light, Nyberg proposed affine linear cryptanalysis, which is a new variant of multidimensional linear cryptanalysis. Affine linear cryptanalysis discards a whole half-space of linear approximations, which contribute little or nothing to the capacity, and only extracts information from the reserved affine subspace to construct more effective test statistics to attack block ciphers. In order to further improve the efficiency of the attacks, Nyberg conjectured that discarding the terms with low scores of affine statistic, and the sum of the remaining terms is also a statistic that follows chi-square distribution. This paper proves that Nyberg conjecture is correct using statistical techniques, and gives an application method of this conjecture. Finally, we verify the validity of the new model using PRESENT and Serpent algorithms. We perform 26 rounds attack on PRESENT with about 261.5 data complexity and 268.37 time complexity. For 27 rounds PRESENT, we perform key recovery attack with about 263.25 data complexity and 268.37 time complexity. In addition, we analyze the data complexity of affine linear cryptanalysis on 4-round Serpent. |
| Key words: multidimensional linear cryptanalysis affine linear cryptanalysis PRESENT |
