对全轮AES_128的Biclique攻击

对全轮AES_128的Biclique攻击 DOI: 10, 3969 / j, issn, 1671-0673, 2012, 05, 003 AES-128Biclique对全轮的攻击 ，徐田敏陈少真 ( )，450001信息工程大学 网络空间安全学院河南 郑州 : AES Biclique ，AES-128 Biclique 摘要文章给出了一个 算法的 结构提出了对 算法的 全轮攻48 126, 35 ，2，2。AES-128 击攻击的数据复杂度是 恢复密钥的计算复杂度是 次加密全轮 算法 : ; AES ; Biclique 关键词分组密码算法结构 : TN918, 1: A: 1671-0673( 2012) 05-0527-04中图分类号文献标识码文章编号 Biclique Cryptanalysis of the Full-Round AES-128 Algorithm XU Tian-min，CHEN Shao-zhen ( Institute of Cyberspace Security，Information Engineering University，Zhengzhou 450001，China) Abstract: A Biclique structurei s presentedf or the AES algorithm，and the Biclique cryptanalysis of 48 the fu-round AES-128 agorthm s dscussed, The data compexty of the attack s 2，and the llliiilii 126, 35 computation complexity of key recoveryi s 2full-round AES encryptions, Key words: block cipher; AES; Biclique structure 0 引言 ,1, AES、192 256 128 ，128分组密码算法 是 比特分组长度的国际标准密码算法密钥长度分别为 和 比，10、12 14。AES ，特对应的轮数分别为 和 作为全球加密标准它的安全性一直是密码学界最关注的 。，，,2,热点在过去的十几年里对它的攻击陆续有新的结果文献使用两个密钥和相关密钥不可能差分攻 8 AES-192，,3,AES-192 AES-256 ，,4,AES-击了 轮 文献对 和 进行了相关密钥矩形攻击文献首次对全轮 256 ，,5,，AES 进行分析文献提出了一种自动搜索相关密钥差分的方法并对所有版本的 进行了相关密钥 。，飞镖攻击而上述攻击方法对明密文以及密钥都有很强的限制条件而这种条件在实际应用中是几乎不 ，AES 。可能达到的所以它们对 的安全性实际上是不构成威胁的 ,6,，，文献提出中间相遇攻击的思想这种攻击方法已经对许多分组密码算法进行了有效分析文献 ,7,AES ，,8,，。给出对 算法的中间相遇攻击文献改进了这种攻击给出复杂度更低的结果 ,10,,9,Hash Biclique，3 AES 文献将用于攻击 函数的 技术用于对分组密码的攻击构造了 轮 独立的 Biclique ，，AES-。Biclique结构结合中间相遇攻击方法对 进行了优于穷举攻击的全轮攻击在构造独立的 1 复杂度比较 ，“”，结构时需要构造两条不相交的差分路径而 ， 对于扩散较快的分组密码算法的轮函数要构造 轮数数据复杂度计算复杂度攻击方法文献 48126, 35 10 Biclique 攻击本文22。这样的两条差分路径是困难的本文对攻击路径进 88126, 18,9, Biclique 攻击 不10 22，，行了改进大大降低了数据复杂度复杂度比较如 ,11, 56 251, 6 可能差分攻击7 22 1。表 : 2012-01-06; : 2012-03-20收稿日期修回日期 : ( 61070178) ; ( 01-02-8)基金项目国家自然科学基金重点资助项目信息安全国家重点实验室开放课基金 : ( 1986 ,) ，，，。作者简介徐田敏男硕士生主要研究方向为分组密码 1 Bcque ili分析 1, 1 Bcque ili结构 d , 1f S C:设 将中间状态 映射到密文 f( S)，，j ，2 ，C=f( S) ，= C，0 i 如果对所有的 称数组 K i K,i，,j j ,{ C} ，{ S} ，{ K,i，j,} ,d Biclique。为一个 维的 i j 2, 2Biclique用独立的相关密钥差分构造 1 ，; ，。定义 如果一个字节的输入差分非零则称为活动字节反之称为非活动字节 2 ，，定义 如果一条差分路径中的活动字节在另一条差分路径中均为非活动字节称这两条差分路 。径为不相交的差分路径 K,0，0,SC，:设密钥 将中间状态 映射到密文 考虑两类差分路径 0 0 K Δ i K -，0 ，，，= 0;?Δ差分 Δ其中ΔΔ i i 0 0 f K % j K-0，，，= 0，。?%差分% 其中%% j j 0 0 f --:，如果 Δ差分和%差分路径不相交可以构造一个联合差分 i j K K %Δ i j d ，i，j { 0，…，2,1 } ，% Δ对所有 ? j i f SC:、K,0，0,，用联合差分替换 和 得到 0 0 K KK,0，0, Δ % i jSC， %? Δ 0 j 0 i f K K, , = C，K = K,0，0, Δ Δi，j 0 i i= S，C，d Biclique。S令 % %得到一个 维的 j 0 j ij 1, 3Biclique 分析的步骤 d d 2d 2 2 ，j,，Bcque : C= f( S )C 、S 2K,iili对 个密文 个中间状态 和 个密钥 建立一个 结构满足 iji K,i，j,j oracle dC: C ，K,i，j,= K，，K2 PP攻击者访问解密预言机用 解密 得到 个明文 如果猜测密钥 则 secret i i i i secret ,1 e K,i，j,:满足i，,jK, ? ? K,i，j, Pv= v( 1)S ji ? ε 1ε 2 ( 1) ，K,i，j,Ki ，j,，K,攻击者通过验证等式确定猜测密钥 为密钥 的候选密钥若存在密钥 使得 secret ? ?( 1) ，v v 。 式成立称 和 为一个匹配 1, 4预计算d( 1) ，，2 2 ?在验证等式 之前可进行下列预计算并存储中间状态预计算的计算量和存储量均为 2d ，2( i ，，S j 通过预计算将攻击总体计算 进行分割而在后续计算中通过减少 盒的计算对特定的 和 只要 d S-) ，，0 i，j 2 ,1 ， 计算那些和储存值不同的 盒值从而降低整体攻击的计算量攻击者对所有的 预?? :计算 , ,K 0，j , , K ? ? i，0 vPv ; S，? ?i j d + 1 2 。得到 个值 2AES-128 算法 8 GF( 2) AES-128 SPN ，128 分组密码算法 是 型的密码体制比特的状态和轮密钥可以看作 上的元素 4 × 4 :组成的 矩阵 : 2 ，10 ，SubByte，加密过程首先将明文和白化密钥进行模 加然后经过 轮轮变化得到密文每轮由 ShftRow，MxCoumn，AddRoundKey ，1 MxCoumniilil。组成最后 轮略去 SubByte S-ShiftRow ，128 16 128 ，是一个非线性变换比特输入通过 个 盒得到 比特输出值对矩阵的每 ，，i i ( i = 0，1，2，3 ) ，MixColumn ( y，y，y，y)MC( x，= 行进行移位操作其中第 行移位 字节通过计算 0 1 2 3 0 x，x，x，) 。得到输出值1 2 3 AES-128 ，#1 1 SubByte MxCoumn，#2 1 il对 的每轮状态进行标记其中表示第 轮 前的状态表示第 轮 ，#3 2 SubByte ShiftRow 。，……，#20 10 后的状态表示第 轮 前的状态表示第 轮 后的输出 0 1 10 0 r , 1 : K K，K，…，K，K= K，K4 SK 密钥扩展算法将主密钥 扩展成轮子密钥 令 对 第 列的值进行 运 r , 1 SubWord( RotWord( X) )Rcon( i / s) ) ，KSK 1 ( :? 运算记为 运算将得到的值与 第 列的值异或得到算注 r r , 1 r r Ki i , 1 Ki ( ，2i4，1r10) 。 1 ，KK第 列的值将 第 列的值与 第 列的值异或得到 第 列的值其中???? 3AES-128 全轮 密钥恢复 , 13密钥分割 ，AES 对密钥进行分割因为 密钥扩展算法每轮子密 ，。 钥之间都是双射变换所以可以对轮子密钥进行划分8,0，0,0，8 K设第 轮的子密钥 有两个字节为 而其它字 112 ，2。16 ，1节跑遍所有的值共 个 字节值如图 密钥群 88{ K,i，j,} K,0，0,i、j ， 是在 上枚举所有的 的差分值112 2。8 2，如图 将第 轮的密钥空间分割成 个组每组有 16 2。个密钥 8 8{ K,，j,}2 i图 密钥集 ,0，0,1 K图 初始密钥 3, 28 3 Biclique维的 轮 Biclique 。AES 5，AES 本节构造一个轮数尽可能长的 结构因为 的轮函数的扩散层分支数为 又 算法 1 MixColumn ，1, 2 Biclique ，最后 轮略去了 运算使用 节中的方法构造 结构若要保证两条差分路径不相 ，8 3 Biclique :交至多只能构造一个 维 轮的 结构 , 1C= 0，S= f( C) ;?确定 计算 8 0 0 K,0，0,0 K K ;( S 8) ( S 8) ?构造密钥差分 Δ和% ij K, 2 ，--( S 8)1根据 节Δ差分和 %差分是由密钥差分 Δ i j i K K K ( S 8) ，( S 8) ( S 8) 和%决定的而 Δ和%的选择由两方面的 jij : --因素决定一方面需要 Δ差分路径和 %差分路径重复的字 i j ，; -节数尽可能的少从而降低计算复杂度另一方面需要 Δ差 i ，分在密文上有差分的字节尽可能的少从而降低数据复杂 K K 。 3 。( S 8) ( S 8) 如图 所示度构造初始密钥的差分 Δ和 % ij K K --;?构造 Δ差分路径和%差分路径 i j ( S 8) ( S 8) 3 图 初始密钥的差分 Δ和% ijK K ，( S 8) ( S 8) 和密钥扩展算法由初始密钥差分 Δ和 % ij --，4 。AES-128 3 可以得到 算法的两条不相交的 轮差分路径 Δ差分和 %差分如图 所示 i j KK, , , , S= S，C( S 8) ，8 3 Bi-= C，K = K ( S 8)计算 % %可得到一个 维的 轮 Δ Δ i，j 0，0 j 0 j ij 0 i i clique ,{ C} ，{ S} ，{ K,i，j,} ,。 i j -8 ，，由上可知Δ差分仅影响密文的 个字节所有的密 i K =C。( S 10)，文在 有相同的值另外由于 Δ 0，1，4，6，9，10，13，14 i 3 KK( S 10)( S 10) ， C=C=C，，= Δ可得 所以数据复 Δ i 7 i 11 3 11 7 48 2。杂度不会超过 3, 3 Biclique 7 匹配前 轮 ，--首先在 %差分和 Δ差分的基础上构造两条全轮的 i j ，，P差分路径并得到这两条路径重叠的部分然后通过验证 i ?K,，j,i? ? K,，j,i， ， ， ， v = v Si，j,K, 来判断 是否为秘密密 ?#5#5 j 0 0 εε 12 ，,9,，1 ，K钥 采用文献的匹配方法只对 字节进行匹配 secret S-。，这样可以减少一些重复计算的 盒从而降低计算复杂度 K,0，,j ? ? K,i，0, d + 1v v SP2 通过预计算 ? 和 得到了 个值和 ? i j ，j i、相应的中间状态存储值对每个 还要重新计算那些和储 v :，存状态 不同的值估算一下每个方向重新计算的量 图 4--Δ差分和 %差分 j id 0 i，j2 ,1 ，向前方向重复计算分析 对所有的 ??计 ? ? K,i，j,K,i，0,Pv ，Pv ，算 重复计算和 ? 储存值不同的字节它的个数 i i K,，j,K,，0,，5 ii取决于密钥 和 的差分由图 可知向前方向需要重复计算的S-。13 盒有 个 i，,jK,? d i，j2, 1，v 0S ，向后方向重复计算分析 对所有的 计算 ??? jK,0，,j ? v S，j,，K,i重复计算和 储存值不同的字节它的个数取决于密钥 和 ? j K,0，j,，5 S-49 。的差分由图 可知向后方向需要重复计算的 盒有 个3, 4 复杂度 n , 2d Bcque 2 ili，因为恢复所有的密钥需要进行 分析 次这种攻击方 :法的复杂度如下 n $ 2d C=( C+ C+ C+ C) ，2 full Biclique precomp recomp f alsepas ，CBiclique ; C;其中是构造一个 的复杂度是预计算的复杂度 Biclique precomp C; Cv 是重新计算的复杂度是指在错误的位置上对 进行匹配recomp falsepas 8 ，1 ，2。的复杂度如果对 字节匹配这个值大约为 8CC2 AES 和 两者复杂度的总和不会超过 次的全轮 加 precomp Biclique ，CSubByte MixColumn ，密取决于重复计算的 运算以及 运算而 recomp SubByte AES 。运算是 运算的复杂度的主要部分由上可知需要重复计 S-S-62，AES-128 160 + 40 = 200，算的 盒个数为 因为 总的 盒的个数为 1614, 31112 814, 31 * 62 /200 = 2，，C= 2( 2 + 2C= 2最后可得复杂度 故 full recomp 8 126, 35 = 2。+ 2) 4 Biclique ，Biclique Bi-本文首先介绍了 结构如何构造一个 结构和 clique ; AES-128 ; 分析的步骤及预计算然后对 算法进行了简单的描述 AES-128 ，最后用此方法对全轮 算法进行了攻击攻击的数据复杂度是 48 126, 35 2，2。AES ，时间复杂度为 这种方法不仅适用于对 的攻击只要是 。密钥扩展算法具有较慢的扩散性质的分组密码都适用于这种攻击方法 ,2, Mark Blunden，Adrian Escott, Related Key Attacks on Reduced Round KASUMI,C,/ / FSE 2001, 2002: 277-285,,3, Eli Biham，Orr Dunkelman1，Nathan Keller, A Related-Key Rectangle Attack on the Full KASUMI,EB / OL,, ,2011-12-19,, http: / e/prnt, acr, org 2005, ii ,4, Orr Dunkelman，Nathan Keller，Adi Shamir, A Pratical-Time Attack on the A5 /3 CryptosystemUse d in Third Generation GSM,EB / OL,, ,2011-12-19,, http: / e/print, iacr, org, 2010, ,5, Kuhn U, Cryptanalysis of reduced-round MISTY,M,, Springer-Verlag，2001: 325-339, ,6, Teruo Saito, A Single-Key Attack on 6-Round KASUMI,EB / OL,, ,2011-12-19,, http: / e/print, iacr, org, 2011, ,7, Nobuyuki SUGIO，Hiroshi AONO，Sadayuki HONGO, A Study on Higher Order Differential Attack of KASUMI ,J,, IEICE Transactons，2007: 14-21, i ,8, Sugio N，Tanaka H，Kaneko T, A study on higher order differential attack of KASUMI,C,/ / Proc, International Symposium on Information Theory and its Applications, 2002: 755-758, ,9, Jia Keting，Yu Hongbo，Wang Xiaoyun, A Meet-in-the-Middle Attack on the Full KASUMI,EB / OL,, ,2011-12-19,, http: / / eprint, iacr, org, 2011, ,10, Wonil Lee，Kouichi Sakurai，Seokhie Hong，Sangjin Lee, On the pseudorandomnesso f a modification of KASUMI Type Per- mutatons,C,/ / CSC 2004, 2005: 313-329, iII ,11, Johan Wallen, Design principles of the KASUMI block cipher,EB / OL,, ,2011-12-19,, http: / e/print, iacr, org, 2000, 欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍欍 ( )530 上接第 页 :参考文献 ,1, Joan D，Lars RK，Vincent R, The Block Cipher Square ,C,/ / F SE’97, 1997: 149-165, ,2, Goce J，Yvo D, Related-key differential cryptanalysis of 192-bit key AES variants ,C,/ / P roceedings of Selected Areas in Cryptography200 3, Lecture Noteins Computer Science 3006，Springer-Verlag，2004: 208-221, ,3, Jongsung K，Seokhe H，Bart P, Reated-key rectange attackso n reduced AES-192 and AES-256,C,/ / P roceedngs of Fast illi SoftwareE ncryption 2007, Lecture Noteins Computer Science 4593，Springer-Verlag，2007: 225-241, ,4, Alex B，Dmitry K，Ivica N, Distinguisher and Related-Key Attack on the Full AES-256,C,/ / Proceedings of CRYPTO 2009,Lec ture Noteins Computer Science 5677，Springer-Verlag，2009: 231-249, ,5, Biryukov A，Nikolic I, Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Applica- tion to AES，Camellia，Khazad and Others,C,/ / EUROCRYPT 2010, LNCS，2010: 22-344, ,6, Diffie W，Hellman ME, Exhaustive Cryptanalysis of the NBS Data Encryption Standard,J,, Computer，1977，10: 74-84, ,7, Huseyin D，Ali AS, A Meet-in-the-Middle Attack on 8-Round AES,C,/ / FSE 2008, LNCS 5086，2008: 116-126, ,8, Orr D，Nathan K，Adi S, mproved Snge-Key Attacks on 8-round AES,R / OL,, ,2010-05-31,, http: / e/prnt, acr, org / , Iilii,9, Andrey B，Dmtry K，Chrstan R, Bcque Cryptanayss of the Full AES,C,/ / ASACRYPT11, 2011: 344-371, iiiililiI' ,10, Dmitry K，Christian R，Alexandra S, Bicliques for preimages: attackso n Skein-512 and the SHA-2 family,C,/ / FSE'12, 2012: 244-263, ,11, Hamid M，Mohammad D，Vincent R，et al, Improved Impossible Differential Cryptanalysis of 7-Round AES-128,C,/ / IN- DOCRYPT10, 2010: 282-291, ’