AES不可能差分攻击的进一步改进
闫雪萍，戚文峰,谭 林
(战略支援部队信息工程大学 网络空间安全学院，河南 郑州 450001)
高级加密标准AES[1]是目前使用最广泛、研究最多的分组密码算法。许多密码算法、Hash函数和伪随机数发生器采用类似AES的结构来设计，许多密码算法甚至直接使用减轮AES作为算法的关键部件，如Saturnin[2]、PRINCE[3]、LED[4]和AEZ[5]等。从AES提出至今二十多年来，学者们进行了大量密码分析研究。虽然未对AES产生实际的威胁，但学术界持续的研究促进了人们对AES密码结构性质的认识和AES密码分析技术的发展。对AES主要的密码分析技术有：积分[1,6]、不可能差分[7-14]、零相关线性[15]、子空间路径[16]、混合差分[17-18]、yoyo[19]、交换攻击[20]、折回镖[21]、Boomeyong[22]和中间相遇攻击[23]等。
不可能差分分析技术[24]利用概率为0的差分特征对密码算法进行区分或者密钥恢复攻击，是评估分组密码算法安全性的重要方法之一。2000年，Biham等[7]提出AES的4轮不可能差分区分器和5轮密钥恢复攻击。2002年，Cheon等[8]将其扩展到6轮。Zhang等[9]和Bahrak等[10]分别利用不同的4轮AES不可能差分区分器给出了7轮AES-128的密钥恢复攻击，时间复杂度均为2119，数据复杂度均为2115.5。2008年，Lyu等[11]利用多个差分和密钥扩展算法将文献[10]中攻击的时间复杂度改进到2117.2、数据复杂度改进到2112.2。2010年，Mala等[12]提出新的4轮AES不可能差分区分器，利用数据筛选和密钥猜测的折中将7轮AES-128攻击的时间、数据和存储复杂度分别改进到2110.1，2106.2和294.2。2018年，Boura等[13]改变筛选数据对和猜测密钥的顺序，利用多个不可能差分区分器对攻击进行了改进，得到时间复杂度为2113，数据复杂度为2105.1的7轮AES-128密钥恢复攻击(时间复杂度被文献[14]由2106.88更正为2113)。在EUROCRYPT 2021上，Leurent等[14]发现了AES密钥方案的新特征，通过选择不同的基表示，AES-128的轮密钥可以表示成4个32比特的块独立地进行变换。利用密钥方案的新表示技术，文献[14]改进了Boura等的7轮不可能差分攻击，时间、数据和存储复杂度分别为2110.9、2104.9和274.9。与Mala等的攻击相比，文献[14]的攻击数据复杂度有一定减少，时间复杂度略有增加。
本文将Leurent等提出的密钥方案的新表示技术应用于Mala等的7轮AES-128不可能差分攻击，将攻击的时间复杂度由2110.1改进到2108.96，数据复杂度从2106.2改进到2105。表1给出了目前5轮以上AES-128密钥恢复攻击的主要结果，其中，时间复杂度中XOR表示异或，其余为相应轮数的AES加密，数据复杂度中ACC指适应性选择明密文，其余为选择明文。
表1 5轮以上AES-128密钥恢复攻击主要结果Table 1 Key recovery attacks on 5 and more rounds of AES-128
(续表1)
1.1 AES算法简介
AES算法的分组长度为128比特，密钥长度支持128比特、192比特和256比特，相应的迭代轮数分别为10、12和14，分别用AES-128、AES-192和AES-256来表示。128比特状态通常用有限域28上4×4的矩阵来描述，矩阵中字节顺序如图1所示。AES的轮变换包括以下4个操作：
(1)字节替换(SB)：状态矩阵的每个字节查询同一个8比特S盒。
(2)行移位(SR)：将状态矩阵的第i行循环左移i个字节,其中i=0,1,2,3。
(3)列混合(MC)：用28上一个MDS矩阵乘以状态矩阵的每一列。
(4)轮密钥加(AK)：将状态与轮密钥逐比特异或。
图1 状态矩阵字节顺序Fig.1 Order of bytes in the state matrix
在加密时，明文先与主密钥异或，再进行相应数量的轮变换，最后一轮没有MC操作。AES一轮轮变换为AK°MC°SR°SB，当交换线性运算AK和MC的顺序时，轮变换可以表示为MC°AK′°SR°SB。AES的轮密钥由主密钥K0通过密钥扩展方案生成，AES-128的密钥扩展方案如下：
Kr,0=Kr-1,0+S(Kr-1,13)+Cr,
Kr,1=Kr-1,1+S(Kr-1,14),
Kr,2=Kr-1,2+S(Kr-1,15),
Kr,3=Kr-1,3+S(Kr-1,12),
Kr,j=Kr-1,j+Kr,j-4,
其中,Cr是轮常数，Kr,j表示第r轮轮密钥Kr的第j个字节，1≤r≤10,0≤j≤15。关于AES算法更详细的介绍参见文献[1]。本文用col(i)表示矩阵的第i列，SR(col(i))表示矩阵的第i条反对角线，SR-1(col(i))表示矩阵的第i条对角线，i=0,1,2,3。用Xi表示矩阵X的第i个元素，X{i1,i2,…,in}表示矩阵X的第i1,i2,…,in个元素。用Xcol(i1,i2,…,in)表示矩阵X的第i1,i2,…,in列上的元素，XSR(col(i1,i2,…,in))表示矩阵X的第i1,i2,…,in条反对角线上的元素，XSR-1(col(i1,i2,…,in))表示矩阵X的第i1,i2,…,in条对角线上的元素。
1.2 AES密钥方案的新表示技术
在EUROCRYPT 2021上，通过分析AES-128密钥方案的不变子空间，Leurent等[14]发现选择28上16维向量空间的另一组基e0,e1,…,e15时，密钥方案可以表示成4个块独立地进行变换。这里
e0=(0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1),
e1=(0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0),
e2=(0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0),
e3=(1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0),
e4=(0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0),
e5=(0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
e6=(1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0),
e7=(0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0),
e8=(0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0),
e9=(1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0),
e10=(0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0),
e11=(0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0),
e12=(1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0),
e13=(0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0),
e14=(0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0),
e15=(0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0)。
对于AES-128第r轮的轮密钥Kr=(Kr,0,Kr,1,…,Kr,15)，设sr=(sr,0,sr,1,…,sr,15)是Kr在基e0,e1,…,e15下的坐标，0≤r≤10。对行向量和列向量不加区分，则Kr=Asr，其中矩阵A是标准基到基e0,e1,…,e15的过渡矩阵,
于是有sr=A-1Kr，具体表示为
(1)
对于AES-128第r+1轮的轮密钥Kr+1，设sr+1是Kr+1在基e0,e1,…,e15下的坐标，0≤r≤9。文献[14]发现了如下特征：
(2)
根据公式(2)，如果已知sr的4个字节sr,{4i,4i+1,4i+2,4i+3}就能够计算sr+1的4个字节sr+1,{4(i+1),4(i+1)+1,4(i+1)+2,4(i+1)+3}，这里脚标模16，0≤i≤3.利用轮密钥在基e0,e1,…,e15下的新表示，将AES-128的密钥扩展方案等价转换成4个块的独立运算，这一特征可以用于不可能差分攻击时验证不同轮密钥部分字节的关系。
本节利用文献[14]的AES密钥方案的新表示技术给出改进的密钥方案筛选过程，将文献[12]中攻击的时间复杂度由2110.1改进到2108.96，数据复杂度由2106.2改进到2105。文献[12]使用的4轮AES不可能差分区分器如图2所示，输入差分在某条对角线上为0，输出差分不可能仅有1个字节非0。
图2 AES的4轮不可能差分区分器Fig.2 Impossible differential distinguisher for 4-round AES
图3 7轮AES不可能差分攻击Fig.3 Impossible differential attack on 7-round AES
根据AES-128密钥方案中轮密钥之间的关系，
K1,0=K0,0+S(K0,13)+C1,K1,2=K0,2+S(K0,15),
猜测K0,SR-1(col(0,2))之后，可以直接计算出K1,{0,2}。因此,在算法中，只需要猜测14字节的轮密钥K0,SR-1(col(0,2))‖K1,{8,10}‖K7,SR(col(3))即可进行攻击。猜测K1,{8,10}之后，根据
K0,4=K1,8+K1,0+K0,8,K0,6=K1,2+K1,10+K0,10,
可以计算出K0,{4,6}，所以算法最终可以筛选出K0,{0,5,10,15,2,7,8,13,4,6}‖K7,SR(col(3))的猜测值。
假设K0,{0,5,10,15,2,7,8,13,4,6}‖K7,SR(col(3))的每个猜测值经过不可能差分区分器的筛选后被留下的概率为P，则平均有2112P个值被留下。对于每个留下的值，首先遍历主密钥K0剩余的6个字节K0,{1,3,9,11,12,14}，由密钥扩展方案计算出K7，并筛选出满足计算的K7,SR(col(3))与被留下的值相同的K0,{1,3,9,11,12,14}，这一过程被称为密钥方案筛选过程。被筛选出的K0,{1,3,9,11,12,14}的个数期望为248×2-32=216，将它们与K0,{0,5,10,15,2,7,8,13,4,6}一起作为候选密钥进行加密验证。密钥方案筛选过程需要2112P×248=2160P次密钥方案的计算，最后对 2112P×216=2128P个候选密钥进行加密验证。
2.1 改进的密钥方案筛选过程
在密钥方案筛选过程中，对于每一个可能的密钥值K0,{0,5,10,15,2,7,8,13,4,6}‖K7,SR(col(3))，
(1)遍历K0,{12,14}的216个可能值，根据公式(1)计算s0,{0,1,2,3}，再根据公式(2)计算s7,{12,13,14,15}，验证K7,12=s7,12是否成立。如果成立再计算s0,{8,9,10,11}和s7,{4,5,6,7}，验证K7,6=s7,4+s7,14是否成立，如果成立将K0,{12,14}的值保留。这步筛选后平均留下216×2-16=1个K0,{12,14}的值。
(2)遍历K0,11和K0,1+K0,9的216个可能值，由公式(1)计算s0,{4,5,6,7}，再由公式(2)计算s7,{0,1,2,3}，以s7,0的值为索引将K0,11和K0,1+K0,9的值存储到表格L中。平均一个s7,0的值对应28个K0,11和K0,1+K0,9的值。
(3)遍历K0,9和K0,3+K0,11的216个可能值，由公式(1)计算s0,{12,13,14,15}，再由公式(2)计算s7,{8,9,10,11}，验证K7,9=s7,8+s7,15是否成立。如果成立，根据s7,0=s7,13+s7,10+s7,7+K7,3计算对应的s7,0。查询表格L得到对应的K0,11和K0,1+K0,9，求解出K0,{1,3,9,11}。最终平均得到K0,{1,3,9,11,12,14}的216×2-8×28=216个可能值。
经过改进之后，密钥方案筛选过程的时间复杂度由2160P次密钥方案的计算减少到 2112P×216=2128P次密钥方案的计算，留下的候选密钥个数不变,即2128P个。
2.2 改进的7轮AES-128不可能差分攻击方案
2.2.1 预处理阶段
在预处理阶段，得到预计算表格L1,L2,i,L2,j和L3，i=0,1,2,3，j=8,9,10,11。
2.2.2 在线阶段
在线阶段攻击的流程如下:
(1)选取2n个不同的明文结构，每个结构在第0条和第2条对角线遍历，其余8个字节取任意固定值，得到2n+127个只在第0条和第2条对角线有差分的明文对。筛选出密文差分满足(C1+C2)SR(col(0,1,2))=0的2n+31个明文对(P1,P2)存入表T1中。
(3)对明文对(P1,P2)，根据ΔPSR-1(col(2))的值在表格L1中搜索得到对应的216个状态对(X1,SR-1(col(2)),X2,SR-1(col(2)))。分别将这些状态对与(P1,SR-1(col(2)),P2,SR-1(col(2)))异或得到216个K0,SR-1(col(2))的值，并将其以明文对 (P1,P2)为索引存入表T2中。
(6)将K0,{2,7,8,13,4,6}‖K7,SR(col(3))的所有可能值存入表格T中。将T4中的密钥值从T中删去，再对T中留下的K0,{2,7,8,13,4,6}‖K7,SR(col(3))的值，与当前猜测的K0,SR-1(col(0))一起，调用改进的密钥方案筛选过程算法得到候选密钥。
(7)对候选密钥进行加密验证。
附录中的算法1给出了改进的7轮AES-128不可能差分攻击。对于K0,SR-1(col(0))的每个猜测值和表T2中的每个明文对(P1,P2)，平均在表T4中对应216×4×210=228个K0,{2,7,8,13,4,6}‖K7,SR(col(3))的不可能值。筛选后每个16字节密钥K0,{0,5,10,15,2,7,8,13,4,6}‖K7,SR(col(3))的猜测值被留下的概率为P=(1-228×2-80)2n+15≈e-2n-37。在预处理阶段，构造表格L1需要264×2×4=267次S盒计算，构造L2,i和L2,j共需要232×4×2=235次S盒计算，构造L3需要242×2×4=245次S盒计算。在线上阶段，对于K0,SR-1(col(0))的每个猜测值，步骤2中筛选明文对(P1,P2)需要2n+31×2×4=2n+34次S盒计算，步骤3中构造表格T2需要2n+15×216=2n+31次内存访问(MA)，相当于2n+31次S盒计算，步骤4中构造表格T3需要2n+15×216×(2+8+8)≈2n+35.17次S盒计算，步骤5中构造表格T4需要2n+15×210=2n+25次内存访问。对于每个K0,SR-1(col(0))的猜测值，表格T4中一共有2n+15×228=2n+43个K0,{2,7,8,13,4,6}‖K7,SR(col(3))的不可能值，所以步骤6的删除操作共需要232×2n+43=2n+75次内存访问。改进的密钥方案筛选过程的复杂度为2128P次密钥方案计算，步骤7一共需要2128P次加密。算法最终的时间复杂度为2n+75/(20×7)+2128P≈2n+67.87+2128-1.44×2n-37，当n=41 时算法时间复杂度最低，为2108.96。算法的数据复杂度为2n+64=2105。筛选满足密文差分的明文对所用的Hash表的规模为296，对于K0,SR-1(col(0))的每个猜测值，表格T4的大小为2n+43，表格T为280，所以算法的存储复杂度主要取决于Hash表的大小296。
本文将Leurent等提出的AES密钥方案的新表示技术应用于Mala等的7轮AES-128不可能差分攻击，将攻击的时间复杂度从2110.1改进至2108.96，数据复杂度从2106.2改进至2105。有一些问题需要进一步研究，例如：①Leurent等的密钥方案新表示技术将AES-128的密钥扩展方案等价转换成4个块的独立运算，是否存在其他新表示可以将密钥扩展方案进一步转化为更多块的独立运算；
②本文对于攻击的改进幅度不大，如何更好地处理数据筛选与密钥猜测的折中，以及结合其他技术进一步改进攻击的复杂度。
附录：
算法1 改进的7轮AES-128不可能差分攻击
预处理：构造表格L1,L2,i,L2,j和L3，i=0,1,2,3,j=8,9,10,11。
输入：241个明文结构，每个明文结构在第0条和第2条对角线遍历，其余8个字节取任意固定值。
输出：主密钥K0。
对每个明文结构，以密文的第0、1、2条反对角线的值为索引构建Hash表，将满足密文差分(C1+C2)SR(col(0,1,2))=0的明文对(P1,P2)存入表格T1中。
for 每个K0,SR-1(col(0))do
for每个 (P1,P2)∈T1do
根据 ΔPSR-1(col(2))在表L1中寻找对应的216个(X1,SR-1(col(2)),X2,SR-1(col(2)))。分别将它们与(P1,SR-1(col(2)),P2,SR-1(col(2)))异或得到216个K0,SR-1(col(2))的值，以明文对(P1,P2)为索引存入表T2中。
end if
end for
for 每个(P1,P2)∈T2和K0,SR-1(col(2))do
计算K1,{0,2}，得到(Y1,{0,2},Y2,{0,2})。计算ΔY{8,10}。
当i,j属于一条对角线时，将对应的K1,8与K1,10组合得到4个K1,{8,10}，计算对应的K0,{4,6}，将其添加到表T2中(P1,P2)和K0,SR-1(col(2))对应的条目之中得到表T3。
end for
for 每个(P1,P2)∈T3do
end for
将K0,{2,7,8,13,4,6}‖K7,SR(col(3))的所有可能值存入表格T中。
将T4中每个K0,{2,7,8,13,4,6}‖K7,SR(col(3))的值从表格T中删去。
forT剩余的K0,{2,7,8,13,4,6}‖K7,SR(col(3))do
for每个K0,{12,14}do
计算s0,{0,1,2,3}和s7,{12,13,14,15}。如果K7,12=s7,12，计算s0,{8,9,10,11}和s7,{4,5,6,7}。如果K7,6=s7,4+s7,14，将K0,{12,14}保留。
end for
for每个K0,11和K0,1+K0,9do
计算s0,{4,5,6,7}和s7,{0,1,2,3}，以s7,0的值为索引将K0,11‖K0,1+K0,9的值存入表L。
end for
for每个K0,9和K0,3+K0,11do
计算s0,{12,13,14,15}和s7,{8,9,10,11}。如果K7,9=s7,8+s7,15，计算s7,0=s7,13+s7,10+s7,7+K7,3，对表格L索引得到其对应的K0,11‖K0,1+K0,9，计算得到K0,{1,3,9,11}。将对应的K0进行加密验证。
ifK0通过验证 then
returnK0。
end if
end for
end for
end for