1、第 21 卷第 4 期2022 年12 月广州大学学报(自然科学版)Journal of Guangzhou University(Natural Science Edition)Vol 21No 4Dec2022收稿日期:2022-09-10;修回日期:2022-10-13基金项目:国家密码发展基金资助项目(MMJJ20180204，MMJJ20170103)作者简介:闫雪萍(1997)，女，博士研究生 E-mail:yanxueping163163 com*通信作者 E-mail:wenfeng qi263 net引文格式:闫雪萍，戚文峰，谭林 AES 不可能差分攻击的进一步改进 J 广州
2、大学学报(自然科学版)，2022，21(4):12-20文章编号:1671-4229(2022)04-0012-09AES 不可能差分攻击的进一步改进闫雪萍，戚文峰*，谭林(战略支援部队信息工程大学 网络空间安全学院，河南 郑州450001)摘要:AES 是目前使用最广泛的分组密码算法。不可能差分密码分析是评估分组密码算法安全性的重要方法之一，目前 AES-128 的 7 轮不可能差分密钥恢复攻击是单密钥模式下轮数最长的攻击之一。在不可能差分攻击中，为了获得满足区分器差分的数据，需要进行数据对和猜测密钥的筛选，它们之间有很强的关联性，对攻击复杂度有很大影响。通过对筛选数据对和猜测密钥进行折中可
3、以使不可能差分攻击的时间复杂度较低。目前时间复杂度最低的 7 轮 AES-128 不可能差分攻击是 2010 年 Mala 等利用筛选数据对和猜测密钥的一个折中提出的，攻击的时间、数据和存储复杂度分别为 2110 1、2106 2和 294 2。如果采用只筛选数据对的方法，攻击的数据复杂度和存储复杂度相对较低。2018 年，Boura 等利用只筛选数据对得到时间、数据和存储复杂度分别为2113、2105 1和274 1(原文中的时间复杂度2106 88被更正为 2113)的7 轮 AES-128 不可能差分攻击。在 EUOCYPT2021 上，Leurent 等发现了 AES 密钥方案的新表示
4、技术，将 Boura 等攻击的时间复杂度改进到 2110 9。文章将Leurent 等提出的 AES 密钥方案的新表示技术应用于 Mala 等的7 轮 AES-128 不可能差分攻击，利用改进的密钥方案筛选过程将攻击的时间复杂度从 2110 1改进到 2108 96，数据复杂度从 2106 2改进到 2105。文章给出的 7 轮AES-128 不可能差分攻击的时间复杂度是上述 3 个攻击算法中最低的。关键词:不可能差分分析;AES;密钥方案中图分类号:TN 918.1文献标志码:AFurther improvement of impossible differential attack on
5、AESYAN Xue-ping，QI Wen-feng*，TAN Lin(School of Cyber Security，Strategic Support Force Information Engineering University，Zhengzhou 450001，China)Abstract:The Advanced Encryption Standard(AES)is currently the most widely used block cipherImpossible differential cryptanalysis is an important approach t
6、o evaluate the security of block ciphersCurrently，impossible differential attacks on 7 rounds of AES-128 are among the attacks with the lon-gest rounds in the single-key setting In an impossible differential attack，to obtain data that satisfiesthe difference of the distinguisher，it is necessary to f
7、ilter data pairs and key guesses，and there is aclose correlation between them，which has a great impact on the complexity By making compromisesbetween filtering data pairs and key guesses，we can reduce time complexity of an impossible differen-tial attack The impossible differential attack on 7-round
8、 AES-128 with the lowest time complexity wasproposed by Mala，et al in 2010 with time，data，and memory complexities of 2110 1，2106 2，and294 2，respectively，using a compromise between filtering data pairs and keys guesses If we use themethod that only filters data pairs，data and memory complexities of t
9、he impossible differential attackare low In 2018，Boura，et al used filters data pairs to obtain an impossible differential attack on 7-round AES-128 with time，data and memory complexities of 2113，2105 1，and 274 1(the time complexity第 4 期闫雪萍等:AES 不可能差分攻击的进一步改进in the original paper 2106 88was corrected
10、 to 2113)，respectively In EUOCYPT 2021，Leurent，etal discovered new representations of the AES key schedule and improved the time complexity of theattack by Boura，et al to 2110 9 This paper applies new representations of the AES key schedule pro-posed by Leurent，et al to the impossible differential a
11、ttack on 7 rounds of AES-128 proposed by Ma-la，et al，and improves the time complexity of the attack from 2110 1to 2108 96and the data complexityfrom 2106 2to 2105by the improved filtering process of key schedule The time complexity of our attack isthe lowest of the three attacks mentioned aboveKey w
12、ords:impossible differential cryptanalysis;AES;key schedule0引言高级加密标准 AES1 是目前使用最广泛、研究最多的分组密码算法。许多密码算法、Hash 函数和伪随机数发生器采用类似 AES 的结构来设计，许多密码算法甚至直接使用减轮 AES 作为算法的关键部件，如 Satur-nin 2、PINCE 3、LED 4 和 AEZ5 等。从 AES 提出至今二十多年来，学者们进行了大量密码分析研究。虽然未对 AES 产生实际的威胁，但学术界持续的研究促进了人们对 AES 密码结构性质的认识和 AES 密码分析技术的发展。对 AES 主要
13、的密码分析技术有:积分 1，6、不可能差分 7 14、零相关线性15、子空间路径16、混合差 分17 18、yoyo 19、交 换 攻 击 20、折 回 镖 21、Boomeyong22 和中间相遇攻击23 等。不可能差分分析技术24 利用概率为 0 的差分特征对密码算法进行区分或者密钥恢复攻击，是评估分组密码算法安全性的重要方法之一。2000 年，Biham 等 7提出 AES 的 4 轮不可能差分区分器和 5 轮密钥恢复攻击。2002 年，Cheon 等 8将其扩展到 6 轮。Zhang 等 9和Bahrak 等 10分别利用不同的 4 轮 AES 不可能差分区分器给出了 7 轮 AES-
14、128 的密钥恢复攻击，时间复杂度均为 2119，数据复杂度均为 2115 5。2008 年，Lyu 等 11利用多个差分和密钥扩展算法将文献 10中攻击的时间复杂度改进到 21172、数据复杂度改进到 21122。2010 年，Mala 等 12提出新的 4 轮 AES 不可能差分区分器，利用数据筛选和密钥猜测的折中将 7 轮 AES-128 攻击的时间、数据和存储复杂度分别改进到 21101，21062和 294 2。2018 年，Boura 等 13改变筛选数据对和猜测密钥的顺序，利用多个不可能差分区分器对攻击进行了改进，得到时间复杂度为 2113，数据复杂度为 2105 1的 7 轮
15、AES-128 密钥恢复攻击(时间复杂度被文献 14由 210688更正为2113)。在 EUOCYPT 2021 上，Leurent 等 14发现了 AES 密钥方案的新特征，通过选择不同的基表示，AES-128 的轮密钥可以表示成 4 个 32 比特的块独立地进行变换。利用密钥方案的新表示技术，文献 14 改进了 Boura 等的 7 轮不可能差分攻击，时间、数据和存储复杂度分别为 21109、2104 9和 2749。与 Mala 等的攻击相比，文献 14 的攻击数据复杂度有一定减少，时间复杂度略有增加。本文将 Leurent 等提出的密钥方案的新表示技术应用于Mala 等的7 轮AES
16、-128 不可能差分攻击，将攻击的时间复杂度由 21101改进到 210896，数据复杂度从 2106 2改进到 2105。表 1 给出了目前 5 轮以上 AES-128 密钥恢复攻击的主要结果，其中，时间复杂度中 XO 表示异或，其余为相应轮数的 AES 加密，数据复杂度中 ACC 指适应性选择明密文，其余为选择明文。表 15 轮以上 AES-128 密钥恢复攻击主要结果Table 1Key recovery attacks on 5 and more rounds of AES-128轮数攻击方式时间复杂度数据复杂度存储复杂度参考文献5混合差分224224221 5 17折回镖216 5215ACC29 216积分244234 6232 6Boomeyong278279 72ACC228 22不可能差分2462114 5245 9混合差分281227 5227 5 17混合差分262 62244 42244 42 1831广州大学学报(自然科学版)第 21 卷(续表 1)轮数攻击方式时间复杂度数据复杂度存储复杂度参考文献7中间相遇297299298 23不可能差分21192115
