乌兹别克斯坦电影
中国科学 E 辑: 信息科学 2007年 第37卷 第2期: 191~198
www.scichina
收稿日期: 2006-07-12; 接受日期: 2006-09-28
国家自然科学基金(批准号: 60673072)和现代通信国家重点实验室基金(批准号: 51436030105DZ0105)资助项目
* 联系人, E-mail: jchen@mail.xidian.edu
1) Daemen J, Rijnmen V. AES Proposal: Rijndael, v/envryption/aes/rijndael 2) The Advanced Encryption Standard, v/aes
《中国科学》杂志社
SCIENCE IN CHINA PRESS 不可能差分分析高级加密标准 陈 杰* 胡予濮 张跃宇
(西安电子科技大学, 计算机网络与信息安全教育部重点实验室, 西安 710071)
摘要 不可能差分是通过寻不可能出现的差分关系, 排除满足这种关系的密
钥, 并最终恢复出秘密密钥的一种攻击方法. 研究了高级加密标准(AES)的不可 能差分分析, 利用AES-192和AES-256的密钥编排方案, 结合时间-存储权衡攻
击, 提出了不可能差分密码分析7轮 AES-192和8轮AES-256的方法. 新方法分
析7轮AES-192需要294.5 选择明文, 记忆存储空间为2129分组, 以及约2157的7
轮AES-192加密. 新方法分析8轮AES-256需要2101 选择明文, 记忆存储空间为
2201 分组, 以及约2228的8轮AES-256加密.
关键词 分组密码 不可能差分密码分析 高级加密标准 密码分析
Rijndael 1)是美国新的高级加密标准(AES)2)征集比赛中的获胜者. 它是在Square 密码[1]基础上设计的一种结构为替换置换网络的分组密码. 因为Square 密码可以抵抗差分攻击和线性攻击, 所以AES 也可以抵抗这两种攻击. 但是由于AES 线性层扩散的不完全性, 先后出现了许多新的攻击方法, 包括不可能
差分攻击[2]、飞来器攻击[3]、矩形攻击[4]、渗透攻击[5]、代数攻击[6]、碰撞攻击[7]等.
2001年Cheon 等人又将不可能差分应用于6轮AES [8], 该攻击需要291.5的选择明文, 2122的6轮加密, 以及289分组的记忆存储空间, 恢复密钥的错误概率为2−34.5. 2004年Raphael 利用192比特和256比特密钥扩展方案, 又将不可能差分攻击应用于7轮AES-192和AES-256的密码分析中[9], 此方法分别需要292和292.5的选择明文, 分别需要2186和2250.5的7轮加密, 并且都需要2153分组的记忆存储空间. 2006年, Biham 将相关密钥和不可能差分相结合, 提出了相关密钥不可能差分分析8轮AES-192的方法[10]. 此方法分析8轮AES-192需要268.5的选择明文, 需要2184的8轮AES-192加密, 以及269分组的记忆存储空间. 但该方法需要相关密钥, 目前已知的最佳不可能差分密码分析的结果就是文献[9]中的结论. 本文主要就AES 的不可能差分进行分析, 将AES 的不可能差分结合AES 的密钥扩展算法和时间-存储权衡攻击, 提出7轮AES-192和8轮AES-256的不可能差分分析方法.
192 中国科学 E 辑 信息科学 第37卷
1 AES 结构介绍
AES 是一个明文分组为128比特的分组密码, 其密钥长度有128, 192或256比特三种, 分别记作AES-128, AES-192和AES-256. AES 针对不同的输入密钥长度需要的迭代轮数也不同, AES-128需要迭代10轮, AES-192迭代12轮, AES-256迭代14轮. AES 轮变换的每个状态可 以形象地表示为一个44×的矩
阵形式, 该矩阵中的每个元素是一个8比特字节, 如图1所示. AES 的轮函数由以下4种变换组成: 非线性88×S-盒替换, 行循环移位, 列混淆变换, 密钥加法运算. AES 算法除了第一轮之前有一个密钥加法运算, 最后一轮没有列混淆运算, 其他轮函数都是由S-盒替换、行移位、列混淆、密
钥加法这个顺序所构成.
AES 在密钥扩展阶段, 将密钥扩展成4行()41R ×+列的扩展密钥数组, 这里用W [i ][()41R ×+] (i =0, 1, 2, 3)来表示, 其中R 表示AES 的迭代轮数. 例如: 第i 轮的轮密钥Expanded Key[i ]由W 中的第4i 列到第4(i +1)−1列给出. 初始密钥为 W [i ][0], …, W [i ][N −1], 其中i ∈{0,1,2,3}, AES-128的N = 4, AES-192的N = 6, AES-256的N = 8.当i ∈{0,1,2,3}和(){},,411j N R ∈×+−"时, W [i ][j ]的值可以通过算法1得到.
算法1
(a) If (N ≤6)
for (j =N; j <4(R +1); j ++)
{If ( j mod N = =0)
{W [0][j ]=W [0][j −N ]⊕S [W [1][j −1]]⊕rcon[ j /N ];
钟信才for (i =1; i <4; i ++)
W [i ][j ]=W [i ][j −N ]⊕S [W [i+1mod4][ j −1]];}
else { for (i =0; i <4; i ++)
W [i ][j ]=W [i ][j −N ]⊕W [i ][j −1];} }
(b) else if (N >6)
for(j =N; j <4(R +1); j ++)
{If (j mod N = =0)
{ W [0][j ]=W [0][j −N ]⊕S [W [1][j −1]]⊕rcon[ j /N ];
for (i =1; i <4; i ++)
W [i ][j ]=W [i ][j −N ]⊕S [W [i+1mod4][ j −1]];}
else if (j mod N = =4)
{for (i =0; i <4; i ++)
thinkcentre m4350qW [i ][j ]=W [i ][j −N ]⊕S[W [i ][ j −1]];}
else { for (i =0; i <4; i ++)
W [i ][j ]=W [i ][j −N ]⊕W [i ][ j −1];} }
其中rcon[k ]表示轮常量, 用于消除对称. S :{}{}3232
0,10,1→ 是一个非线性置换. 针对AES 算法的结构特点, 下节将介绍4轮AES 的一般不可能差分密码分析.
1 2 3 4
5 6 7 8 9 10 11 12
13 14 15 16 图1 128比特数据分组AES 状态的44×字节矩阵分布
第2期
陈 杰等: 不可能差分分析高级加密标准 193
2 4轮AES 中的不可能差分密码分析
不可能差分是通过寻不可能出现的差分关系, 排除满足这种关系的密钥, 并最终恢复出秘密密钥的一种攻击方法. 2000年Biham 和Keller 首次将不可能差分应用于AES 的密码分析1) , 并给出了AES 的4轮不可能差分特性的性质1.
性质1 若明文对只有1字节不同(一个活动字节), 则4轮AES 的密文对不可能在以下4种组合出现相同: (1,8,11,14), (2,5,12,15), (3,6,9,16)或(4,7,10,13).
我们可以由性质1得到: 当4轮AES 的明文对只有一个活动字节, 输出对的非活动字节不可能包含性质1中4种情形的任何一种. 例如: 当4轮AES 的明文对仅有一个活动字节时, 输出对的活动字节不可能在(2, 5, 6, 9), 如图2所示.
图2 AES 的4轮不可能差分
图2中SB 表示S-盒替换; SR 表示行循环移位; MC 表示列混淆变换; AR 表示密钥加法运算. SB −1, SR −1, MC −1和AR −1分别表示它们的逆运算. 黑框表示对应输入对的当前状态字节不同(活动字节), 白
框表示对应输入对的当前状态字节相同(非活动字节). 需要注意的是: 只有行移位和列混淆会影响输入对活动字节的位置和个数.
列混淆是一个输入为4字节的线性变换, 因而它也是输入对差分的线性变换. 若列混淆输出差分的3个字节为零, 由列混淆的可逆性可知: 可能的输入差分共有28−1种. 因为输出差分只有1个活动字节的情形共有4种, 并且当输入差分非零时输出差分必定非零, 所以输出差分的3字节为零的概率是8324(21)/2×−.
引理1 列混淆MC 及其逆变换MC −1的输出差分有3字节为零的概率是p = 2−22.
核酸杂交
当输入差分的某些值为固定值时, 引理1仍然成立. 同理可得, 列混淆及其逆变换输入差分在固定位置有3个活动字节, 输出差分在固定位置有2个活动字节的概率为
())
23888121212q −⎡⎤′=−−≈⎢⎥⎣
⎦.
1) Biham E, Keller N. Cryptanalysis of reduced variants of Rijndael, v/envryption/aes/round2/ conf3/aes3papers.html
194 中国科学 E 辑 信息科学 第37卷
3 AES 中的不可能差分分析
3.1 7轮AES-192的不可能差分分析七叶和茶
本节将介绍一种新的7轮AES-192不可能差分密码分析方法. 该攻击方法是基于性质1的4轮不可能差分的基础, 利用AES-192密钥编排方案在4轮不可能差分的前面加了1轮, 后面加了2轮. 该攻击需要294.5选择明文, 2157的7轮AES-192加密, 以及2129分组的记忆存储空间, 猜测错误密钥的概率仅为2−52.
攻击过程如图3所示, 共7个步骤:
图3 AES-192的7轮不可能差分分析
1. 我们把明文状态的某些字节具有固定值, 而其他字节的值可以任意选取的这种明文集合称为一种结构. 考虑如下结构: 明文状态仅在(1,6,11,16)处的值可以任意选取, 其他位置的值均为固定值. 这种结构包括232个明文, 共有32326322122××=明文对.
2. 选取262.5种第1步中的结构, 即选取明文62.53294.5222×=, 明文对62.563125.5222×=. 再在这些明文对中选取它们的密文差分在(5, 8, 11, 12, 14, 15)处为活动字节, 其他位置均为非活动字节的那些明密文对. 满足这样条件的对有125.58045.5222−×=.
3. 猜测第7轮子密钥的(1, 2, 5, 8, 11, 12, 14, 15)处的64比特. 并且对选取的每一密文对(,)C C ∗, 计算第6轮的前两列输出1167()C SB SR C K −−=⊕D 和1167()C SB SR C K ∗−−∗=⊕D .
4. 选取第6轮行移位后的输出差分即166()MC C C −∗⊕, 在(1, 2, 5, 14) 处为活动字节的那
些明密文对.由上节可知此概率为2881611
()222q q −−−′=≈×=, 符合以上条件的对有45.51629.5222−×=.
5. 猜测第6轮的前两列64比特子密钥, 并且对符合上面要求的明密文对计算第5轮的前
第2期
陈 杰等: 不可能差分分析高级加密标准 195
两列输出111566()C SB SR MC C K −−−=⊕D D 和111566()C SB SR MC C K ∗−−−∗=⊕D D . 当第5轮行移
位后前两列每列只有2个活动字节, 且第4轮输出的4个活动字节不在4个不同列时的概率为
61620.3230(122)236
q −−−=−−=. 选取这样的对, 共有29.50.329.2222−×=对.
6. 猜测满足以上5步的明文对(P , P *)的(1, 6, 11, 16)处32比特初始密钥K 0, 并计算00(()())MC SR SB P K SB P K ∗⊕⊕⊕D 的值, 选取该值只有一个活动字节的明密文对, 由引理1可知此概率为2422242p −−=×=.
7. 由第2节的分析可知: 满足以上6步的差分是不可能差分, 所以每一个通过该假设的密钥都是错误密钥. 排除所有满足以上6步的密钥, 最后恢复出秘密密钥.
3.2 7轮AES-192的不可能差分复杂度分析
由上一节可知: 在分析第6步229.2明密文对之后, 猜测初始密钥K 0的4字节为错误值的概率为29.27.2322223221802(12)2e 2−−−−≈≈. 我们希望初始假设的128比特密钥K 6和K 7是正确的, 从而可以排除所有错误的32比特初始密钥K 0, 因而剩下的错误值(K 0, K 6, K 7)的概率为12818052222−−×=. 因此, 当仅剩一个K 0值时我们认为密钥K 6和K 7是正确的.
第3步和第5步所需猜测的轮密钥为: W [0][28], W [1][28], W [0][29], W [3][29], W [2][30], W [3][30], W [1][31], W [2][31], W [i ][24]和W [i ][25], 此处i = 0,1, 2, 3, 共128比特. 由于W [2][31] = W [2][25]⊕W [2][30], W [3][30] =W [3][24]⊕S [W [0][29]], W [2][30] = W [2][24]⊕S [W [3][29]], 所以我们只需猜测K 6和K 7的104比特.
第3步需要 6445.5110.52222××=的1轮加密. 第5步需要(10464)29.570.52222−××=的1轮加密. 第6步需要约
29.21043222222222159222{1(12)(12)(12)}2−−−××+−+−++−≈"
的1轮加密. 因此该攻击共需110.570.51591592222++≈的1轮加密. 64比特的第7轮子密钥K 7可以由2159的1轮加密恢复出来. 如果知道连续的192比特轮子密钥, 则可以恢复出秘密密钥. 攻击者可以通过穷举到第7轮剩下的64比特密钥以及第6轮后两列密钥, 共128比特, 需要2128的7轮AES-192加密运算. 因而该攻击分析7轮AES-192共需要约2157的7轮AES-192加密. 所需的存储空间为10432136222×
=比特=136********=分组.
3.3 8轮AES-256的不可能差分分析
本节将介绍一种新的8轮AES-256不可能差分密码分析方法. 该攻击是基于性质1的4轮不可能差分的基础, 利用AES-256密钥编排方案在4轮不可能差分的前面加了1轮后面加了3轮. 该攻击需要2101选择明文, 2228的8轮AES-256加密, 以及2201分组的记忆存储空间, 猜测错误密钥的概率仅为2−298.
攻击过程如图4所示, 共9个步骤:
1. 选取明文状态仅在(1, 6, 11, 16)处的值可以任意选取, 其他位置均为固定值的这种结 构, 该结构包括232个明文, 共有32326322122××=明文对. 由此可得: 满足此结构的明文差分控水系统
196 中国科学 E 辑 信息科学 第37卷
的活动字节仅在(1, 6, 11, 16)处.
图4 AES-256的8轮不可能差分分析
2. 选取269种第1步中的结构, 即选取明文6932101222×=, 明文对6963132222×=. 再在这些明文对中选取它们的密文差分在(5, 8, 11, 12, 14, 15)处为活动字节, 其他位置为非活动字节的那些明密文对. 满足这样条件的对有1328052222−×=.
3. 猜测第8轮子密钥的(1, 2, 5, 8, 11, 12, 14, 15)处的64比特. 并且对选取的每一密文对(,)C C ∗, 计算第7轮的前两列输出1178()C SB SR C K −−=⊕D , 1178()C SB SR C K ∗−−∗=⊕D .
4. 选取这样的对: 第7轮行移位后的输出差分即177()MC C C −∗⊕, 在(2, 5, 6, 9) 处为活动
字节的那些明密文对. 此概率为
2881611
()222q q −−−′=≈×=, 符合上面条件的对有521636222−×=.
5. 猜测第7轮的前两列64比特子密钥, 并且对符合上面要求的明密文对计算第6轮中间两列的输出111677()C SB SR MC C K −−−=⊕D D 和111677()C SB SR MC C K ∗−−−∗=⊕D D .
6. 选取这样的对: 第6轮行移位后的输出差分即166()MC C C −∗⊕, 在(2, 11, 14, 15) 处为
活动字节的那些明密文对. 满足该条件的概率为
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议