AES不可能差分攻擊的進(jìn)一步改進(jìn)

閆雪萍，戚文峰,譚 林

(戰(zhàn)略支援部隊(duì)信息工程大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，河南 鄭州 450001)

0 引 言

高級(jí)加密標(biāo)準(zhǔn)AES[1]是目前使用最廣泛、研究最多的分組密碼算法。許多密碼算法、Hash函數(shù)和偽隨機(jī)數(shù)發(fā)生器采用類(lèi)似AES的結(jié)構(gòu)來(lái)設(shè)計(jì)，許多密碼算法甚至直接使用減輪AES作為算法的關(guān)鍵部件，如Saturnin[2]、PRINCE[3]、LED[4]和AEZ[5]等。從AES提出至今二十多年來(lái)，學(xué)者們進(jìn)行了大量密碼分析研究。雖然未對(duì)AES產(chǎn)生實(shí)際的威脅，但學(xué)術(shù)界持續(xù)的研究促進(jìn)了人們對(duì)AES密碼結(jié)構(gòu)性質(zhì)的認(rèn)識(shí)和AES密碼分析技術(shù)的發(fā)展。對(duì)AES主要的密碼分析技術(shù)有：積分[1,6]、不可能差分[7-14]、零相關(guān)線性[15]、子空間路徑[16]、混合差分[17-18]、yoyo[19]、交換攻擊[20]、折回鏢[21]、Boomeyong[22]和中間相遇攻擊[23]等。

不可能差分分析技術(shù)[24]利用概率為0的差分特征對(duì)密碼算法進(jìn)行區(qū)分或者密鑰恢復(fù)攻擊，是評(píng)估分組密碼算法安全性的重要方法之一。2000年，Biham等[7]提出AES的4輪不可能差分區(qū)分器和5輪密鑰恢復(fù)攻擊。2002年，Cheon等[8]將其擴(kuò)展到6輪。Zhang等[9]和Bahrak等[10]分別利用不同的4輪AES不可能差分區(qū)分器給出了7輪AES-128的密鑰恢復(fù)攻擊，時(shí)間復(fù)雜度均為2119，數(shù)據(jù)復(fù)雜度均為2115.5。2008年，Lyu等[11]利用多個(gè)差分和密鑰擴(kuò)展算法將文獻(xiàn)[10]中攻擊的時(shí)間復(fù)雜度改進(jìn)到2117.2、數(shù)據(jù)復(fù)雜度改進(jìn)到2112.2。2010年，Mala等[12]提出新的4輪AES不可能差分區(qū)分器，利用數(shù)據(jù)篩選和密鑰猜測(cè)的折中將7輪AES-128攻擊的時(shí)間、數(shù)據(jù)和存儲(chǔ)復(fù)雜度分別改進(jìn)到2110.1，2106.2和294.2。2018年，Boura等[13]改變篩選數(shù)據(jù)對(duì)和猜測(cè)密鑰的順序，利用多個(gè)不可能差分區(qū)分器對(duì)攻擊進(jìn)行了改進(jìn)，得到時(shí)間復(fù)雜度為2113，數(shù)據(jù)復(fù)雜度為2105.1的7輪AES-128密鑰恢復(fù)攻擊(時(shí)間復(fù)雜度被文獻(xiàn)[14]由2106.88更正為2113)。在EUROCRYPT 2021上，Leurent等[14]發(fā)現(xiàn)了AES密鑰方案的新特征，通過(guò)選擇不同的基表示，AES-128的輪密鑰可以表示成4個(gè)32比特的塊獨(dú)立地進(jìn)行變換。利用密鑰方案的新表示技術(shù)，文獻(xiàn)[14]改進(jìn)了Boura等的7輪不可能差分攻擊，時(shí)間、數(shù)據(jù)和存儲(chǔ)復(fù)雜度分別為2110.9、2104.9和274.9。與Mala等的攻擊相比，文獻(xiàn)[14]的攻擊數(shù)據(jù)復(fù)雜度有一定減少，時(shí)間復(fù)雜度略有增加。

本文將Leurent等提出的密鑰方案的新表示技術(shù)應(yīng)用于Mala等的7輪AES-128不可能差分攻擊，將攻擊的時(shí)間復(fù)雜度由2110.1改進(jìn)到2108.96，數(shù)據(jù)復(fù)雜度從2106.2改進(jìn)到2105。表1給出了目前5輪以上AES-128密鑰恢復(fù)攻擊的主要結(jié)果，其中，時(shí)間復(fù)雜度中XOR表示異或，其余為相應(yīng)輪數(shù)的AES加密，數(shù)據(jù)復(fù)雜度中ACC指適應(yīng)性選擇明密文，其余為選擇明文。

表1 5輪以上AES-128密鑰恢復(fù)攻擊主要結(jié)果Table 1 Key recovery attacks on 5 and more rounds of AES-128

(續(xù)表1)

1 準(zhǔn)備工作

1.1 AES算法簡(jiǎn)介

AES算法的分組長(zhǎng)度為128比特，密鑰長(zhǎng)度支持128比特、192比特和256比特，相應(yīng)的迭代輪數(shù)分別為10、12和14，分別用AES-128、AES-192和AES-256來(lái)表示。128比特狀態(tài)通常用有限域28上4×4的矩陣來(lái)描述，矩陣中字節(jié)順序如圖1所示。AES的輪變換包括以下4個(gè)操作：

(1)字節(jié)替換(SB)：狀態(tài)矩陣的每個(gè)字節(jié)查詢(xún)同一個(gè)8比特S盒。

(2)行移位(SR)：將狀態(tài)矩陣的第i行循環(huán)左移i個(gè)字節(jié),其中i=0,1,2,3。

(3)列混合(MC)：用28上一個(gè)MDS矩陣乘以狀態(tài)矩陣的每一列。

(4)輪密鑰加(AK)：將狀態(tài)與輪密鑰逐比特異或。

圖1 狀態(tài)矩陣字節(jié)順序Fig.1 Order of bytes in the state matrix

在加密時(shí)，明文先與主密鑰異或，再進(jìn)行相應(yīng)數(shù)量的輪變換，最后一輪沒(méi)有MC操作。AES一輪輪變換為AK°MC°SR°SB，當(dāng)交換線性運(yùn)算AK和MC的順序時(shí)，輪變換可以表示為MC°AK′°SR°SB。AES的輪密鑰由主密鑰K0通過(guò)密鑰擴(kuò)展方案生成，AES-128的密鑰擴(kuò)展方案如下：

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是輪常數(shù)，Kr,j表示第r輪輪密鑰Kr的第j個(gè)字節(jié)，1≤r≤10,0≤j≤15。關(guān)于AES算法更詳細(xì)的介紹參見(jiàn)文獻(xiàn)[1]。本文用col(i)表示矩陣的第i列，SR(col(i))表示矩陣的第i條反對(duì)角線，SR-1(col(i))表示矩陣的第i條對(duì)角線，i=0,1,2,3。用Xi表示矩陣X的第i個(gè)元素，X{i1,i2,…,in}表示矩陣X的第i1,i2,…,in個(gè)元素。用Xcol(i1,i2,…,in)表示矩陣X的第i1,i2,…,in列上的元素，XSR(col(i1,i2,…,in))表示矩陣X的第i1,i2,…,in條反對(duì)角線上的元素，XSR-1(col(i1,i2,…,in))表示矩陣X的第i1,i2,…,in條對(duì)角線上的元素。

1.2 AES密鑰方案的新表示技術(shù)

在EUROCRYPT 2021上，通過(guò)分析AES-128密鑰方案的不變子空間，Leurent等[14]發(fā)現(xiàn)選擇28上16維向量空間的另一組基e0,e1,…,e15時(shí)，密鑰方案可以表示成4個(gè)塊獨(dú)立地進(jìn)行變換。這里

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)。

對(duì)于AES-128第r輪的輪密鑰Kr=(Kr,0,Kr,1,…,Kr,15)，設(shè)sr=(sr,0,sr,1,…,sr,15)是Kr在基e0,e1,…,e15下的坐標(biāo)，0≤r≤10。對(duì)行向量和列向量不加區(qū)分，則Kr=Asr，其中矩陣A是標(biāo)準(zhǔn)基到基e0,e1,…,e15的過(guò)渡矩陣,

于是有sr=A-1Kr，具體表示為

(1)

對(duì)于AES-128第r+1輪的輪密鑰Kr+1，設(shè)sr+1是Kr+1在基e0,e1,…,e15下的坐標(biāo)，0≤r≤9。文獻(xiàn)[14]發(fā)現(xiàn)了如下特征：

(2)

根據(jù)公式(2)，如果已知sr的4個(gè)字節(jié)sr,{4i,4i+1,4i+2,4i+3}就能夠計(jì)算sr+1的4個(gè)字節(jié)sr+1,{4(i+1),4(i+1)+1,4(i+1)+2,4(i+1)+3}，這里腳標(biāo)模16，0≤i≤3.利用輪密鑰在基e0,e1,…,e15下的新表示，將AES-128的密鑰擴(kuò)展方案等價(jià)轉(zhuǎn)換成4個(gè)塊的獨(dú)立運(yùn)算，這一特征可以用于不可能差分攻擊時(shí)驗(yàn)證不同輪密鑰部分字節(jié)的關(guān)系。

2 7輪不可能差分攻擊的改進(jìn)

本節(jié)利用文獻(xiàn)[14]的AES密鑰方案的新表示技術(shù)給出改進(jìn)的密鑰方案篩選過(guò)程，將文獻(xiàn)[12]中攻擊的時(shí)間復(fù)雜度由2110.1改進(jìn)到2108.96，數(shù)據(jù)復(fù)雜度由2106.2改進(jìn)到2105。文獻(xiàn)[12]使用的4輪AES不可能差分區(qū)分器如圖2所示，輸入差分在某條對(duì)角線上為0，輸出差分不可能僅有1個(gè)字節(jié)非0。

圖2 AES的4輪不可能差分區(qū)分器Fig.2 Impossible differential distinguisher for 4-round AES

圖3 7輪AES不可能差分攻擊Fig.3 Impossible differential attack on 7-round AES

根據(jù)AES-128密鑰方案中輪密鑰之間的關(guān)系，

K1,0=K0,0+S(K0,13)+C1,K1,2=K0,2+S(K0,15),

猜測(cè)K0,SR-1(col(0,2))之后，可以直接計(jì)算出K1,{0,2}。因此,在算法中，只需要猜測(cè)14字節(jié)的輪密鑰K0,SR-1(col(0,2))‖K1,{8,10}‖K7,SR(col(3))即可進(jìn)行攻擊。猜測(cè)K1,{8,10}之后，根據(jù)

K0,4=K1,8+K1,0+K0,8,K0,6=K1,2+K1,10+K0,10,

可以計(jì)算出K0,{4,6}，所以算法最終可以篩選出K0,{0,5,10,15,2,7,8,13,4,6}‖K7,SR(col(3))的猜測(cè)值。

假設(shè)K0,{0,5,10,15,2,7,8,13,4,6}‖K7,SR(col(3))的每個(gè)猜測(cè)值經(jīng)過(guò)不可能差分區(qū)分器的篩選后被留下的概率為P，則平均有2112P個(gè)值被留下。對(duì)于每個(gè)留下的值，首先遍歷主密鑰K0剩余的6個(gè)字節(jié)K0,{1,3,9,11,12,14}，由密鑰擴(kuò)展方案計(jì)算出K7，并篩選出滿足計(jì)算的K7,SR(col(3))與被留下的值相同的K0,{1,3,9,11,12,14}，這一過(guò)程被稱(chēng)為密鑰方案篩選過(guò)程。被篩選出的K0,{1,3,9,11,12,14}的個(gè)數(shù)期望為248×2-32=216，將它們與K0,{0,5,10,15,2,7,8,13,4,6}一起作為候選密鑰進(jìn)行加密驗(yàn)證。密鑰方案篩選過(guò)程需要2112P×248=2160P次密鑰方案的計(jì)算，最后對(duì) 2112P×216=2128P個(gè)候選密鑰進(jìn)行加密驗(yàn)證。

2.1 改進(jìn)的密鑰方案篩選過(guò)程

在密鑰方案篩選過(guò)程中，對(duì)于每一個(gè)可能的密鑰值K0,{0,5,10,15,2,7,8,13,4,6}‖K7,SR(col(3))，

(1)遍歷K0,{12,14}的216個(gè)可能值，根據(jù)公式(1)計(jì)算s0,{0,1,2,3}，再根據(jù)公式(2)計(jì)算s7,{12,13,14,15}，驗(yàn)證K7,12=s7,12是否成立。如果成立再計(jì)算s0,{8,9,10,11}和s7,{4,5,6,7}，驗(yàn)證K7,6=s7,4+s7,14是否成立，如果成立將K0,{12,14}的值保留。這步篩選后平均留下216×2-16=1個(gè)K0,{12,14}的值。

(2)遍歷K0,11和K0,1+K0,9的216個(gè)可能值，由公式(1)計(jì)算s0,{4,5,6,7}，再由公式(2)計(jì)算s7,{0,1,2,3}，以s7,0的值為索引將K0,11和K0,1+K0,9的值存儲(chǔ)到表格L中。平均一個(gè)s7,0的值對(duì)應(yīng)28個(gè)K0,11和K0,1+K0,9的值。

(3)遍歷K0,9和K0,3+K0,11的216個(gè)可能值，由公式(1)計(jì)算s0,{12,13,14,15}，再由公式(2)計(jì)算s7,{8,9,10,11}，驗(yàn)證K7,9=s7,8+s7,15是否成立。如果成立，根據(jù)s7,0=s7,13+s7,10+s7,7+K7,3計(jì)算對(duì)應(yīng)的s7,0。查詢(xún)表格L得到對(duì)應(yīng)的K0,11和K0,1+K0,9，求解出K0,{1,3,9,11}。最終平均得到K0,{1,3,9,11,12,14}的216×2-8×28=216個(gè)可能值。

經(jīng)過(guò)改進(jìn)之后，密鑰方案篩選過(guò)程的時(shí)間復(fù)雜度由2160P次密鑰方案的計(jì)算減少到 2112P×216=2128P次密鑰方案的計(jì)算，留下的候選密鑰個(gè)數(shù)不變,即2128P個(gè)。

2.2 改進(jìn)的7輪AES-128不可能差分攻擊方案

2.2.1 預(yù)處理階段

在預(yù)處理階段，得到預(yù)計(jì)算表格L1,L2,i,L2,j和L3，i=0,1,2,3，j=8,9,10,11。

2.2.2 在線階段

在線階段攻擊的流程如下:

(1)選取2n個(gè)不同的明文結(jié)構(gòu)，每個(gè)結(jié)構(gòu)在第0條和第2條對(duì)角線遍歷，其余8個(gè)字節(jié)取任意固定值，得到2n+127個(gè)只在第0條和第2條對(duì)角線有差分的明文對(duì)。篩選出密文差分滿足(C1+C2)SR(col(0,1,2))=0的2n+31個(gè)明文對(duì)(P1,P2)存入表T1中。

(3)對(duì)明文對(duì)(P1,P2)，根據(jù)ΔPSR-1(col(2))的值在表格L1中搜索得到對(duì)應(yīng)的216個(gè)狀態(tài)對(duì)(X1,SR-1(col(2)),X2,SR-1(col(2)))。分別將這些狀態(tài)對(duì)與(P1,SR-1(col(2)),P2,SR-1(col(2)))異或得到216個(gè)K0,SR-1(col(2))的值，并將其以明文對(duì) (P1,P2)為索引存入表T2中。

(6)將K0,{2,7,8,13,4,6}‖K7,SR(col(3))的所有可能值存入表格T中。將T4中的密鑰值從T中刪去，再對(duì)T中留下的K0,{2,7,8,13,4,6}‖K7,SR(col(3))的值，與當(dāng)前猜測(cè)的K0,SR-1(col(0))一起，調(diào)用改進(jìn)的密鑰方案篩選過(guò)程算法得到候選密鑰。

(7)對(duì)候選密鑰進(jìn)行加密驗(yàn)證。

附錄中的算法1給出了改進(jìn)的7輪AES-128不可能差分攻擊。對(duì)于K0,SR-1(col(0))的每個(gè)猜測(cè)值和表T2中的每個(gè)明文對(duì)(P1,P2)，平均在表T4中對(duì)應(yīng)216×4×210=228個(gè)K0,{2,7,8,13,4,6}‖K7,SR(col(3))的不可能值。篩選后每個(gè)16字節(jié)密鑰K0,{0,5,10,15,2,7,8,13,4,6}‖K7,SR(col(3))的猜測(cè)值被留下的概率為P=(1-228×2-80)2n+15≈e-2n-37。在預(yù)處理階段，構(gòu)造表格L1需要264×2×4=267次S盒計(jì)算，構(gòu)造L2,i和L2,j共需要232×4×2=235次S盒計(jì)算，構(gòu)造L3需要242×2×4=245次S盒計(jì)算。在線上階段，對(duì)于K0,SR-1(col(0))的每個(gè)猜測(cè)值，步驟2中篩選明文對(duì)(P1,P2)需要2n+31×2×4=2n+34次S盒計(jì)算，步驟3中構(gòu)造表格T2需要2n+15×216=2n+31次內(nèi)存訪問(wèn)(MA)，相當(dāng)于2n+31次S盒計(jì)算，步驟4中構(gòu)造表格T3需要2n+15×216×(2+8+8)≈2n+35.17次S盒計(jì)算，步驟5中構(gòu)造表格T4需要2n+15×210=2n+25次內(nèi)存訪問(wèn)。對(duì)于每個(gè)K0,SR-1(col(0))的猜測(cè)值，表格T4中一共有2n+15×228=2n+43個(gè)K0,{2,7,8,13,4,6}‖K7,SR(col(3))的不可能值，所以步驟6的刪除操作共需要232×2n+43=2n+75次內(nèi)存訪問(wèn)。改進(jìn)的密鑰方案篩選過(guò)程的復(fù)雜度為2128P次密鑰方案計(jì)算，步驟7一共需要2128P次加密。算法最終的時(shí)間復(fù)雜度為2n+75/(20×7)+2128P≈2n+67.87+2128-1.44×2n-37，當(dāng)n=41 時(shí)算法時(shí)間復(fù)雜度最低，為2108.96。算法的數(shù)據(jù)復(fù)雜度為2n+64=2105。篩選滿足密文差分的明文對(duì)所用的Hash表的規(guī)模為296，對(duì)于K0,SR-1(col(0))的每個(gè)猜測(cè)值，表格T4的大小為2n+43，表格T為280，所以算法的存儲(chǔ)復(fù)雜度主要取決于Hash表的大小296。

3 結(jié)束語(yǔ)

本文將Leurent等提出的AES密鑰方案的新表示技術(shù)應(yīng)用于Mala等的7輪AES-128不可能差分攻擊，將攻擊的時(shí)間復(fù)雜度從2110.1改進(jìn)至2108.96，數(shù)據(jù)復(fù)雜度從2106.2改進(jìn)至2105。有一些問(wèn)題需要進(jìn)一步研究，例如：①Leurent等的密鑰方案新表示技術(shù)將AES-128的密鑰擴(kuò)展方案等價(jià)轉(zhuǎn)換成4個(gè)塊的獨(dú)立運(yùn)算，是否存在其他新表示可以將密鑰擴(kuò)展方案進(jìn)一步轉(zhuǎn)化為更多塊的獨(dú)立運(yùn)算；②本文對(duì)于攻擊的改進(jìn)幅度不大，如何更好地處理數(shù)據(jù)篩選與密鑰猜測(cè)的折中，以及結(jié)合其他技術(shù)進(jìn)一步改進(jìn)攻擊的復(fù)雜度。

附錄：

算法1 改進(jìn)的7輪AES-128不可能差分攻擊

預(yù)處理：構(gòu)造表格L1,L2,i,L2,j和L3，i=0,1,2,3,j=8,9,10,11。

輸入：241個(gè)明文結(jié)構(gòu)，每個(gè)明文結(jié)構(gòu)在第0條和第2條對(duì)角線遍歷，其余8個(gè)字節(jié)取任意固定值。

輸出：主密鑰K0。

對(duì)每個(gè)明文結(jié)構(gòu)，以密文的第0、1、2條反對(duì)角線的值為索引構(gòu)建Hash表，將滿足密文差分(C1+C2)SR(col(0,1,2))=0的明文對(duì)(P1,P2)存入表格T1中。

for 每個(gè)K0,SR-1(col(0))do

for每個(gè) (P1,P2)∈T1do

根據(jù) ΔPSR-1(col(2))在表L1中尋找對(duì)應(yīng)的216個(gè)(X1,SR-1(col(2)),X2,SR-1(col(2)))。分別將它們與(P1,SR-1(col(2)),P2,SR-1(col(2)))異或得到216個(gè)K0,SR-1(col(2))的值，以明文對(duì)(P1,P2)為索引存入表T2中。

end if

end for

for 每個(gè)(P1,P2)∈T2和K0,SR-1(col(2))do

計(jì)算K1,{0,2}，得到(Y1,{0,2},Y2,{0,2})。計(jì)算ΔY{8,10}。

當(dāng)i,j屬于一條對(duì)角線時(shí)，將對(duì)應(yīng)的K1,8與K1,10組合得到4個(gè)K1,{8,10}，計(jì)算對(duì)應(yīng)的K0,{4,6}，將其添加到表T2中(P1,P2)和K0,SR-1(col(2))對(duì)應(yīng)的條目之中得到表T3。

end for

for 每個(gè)(P1,P2)∈T3do

end for

將K0,{2,7,8,13,4,6}‖K7,SR(col(3))的所有可能值存入表格T中。

將T4中每個(gè)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每個(gè)K0,{12,14}do

計(jì)算s0,{0,1,2,3}和s7,{12,13,14,15}。如果K7,12=s7,12，計(jì)算s0,{8,9,10,11}和s7,{4,5,6,7}。如果K7,6=s7,4+s7,14，將K0,{12,14}保留。

end for

for每個(gè)K0,11和K0,1+K0,9do

計(jì)算s0,{4,5,6,7}和s7,{0,1,2,3}，以s7,0的值為索引將K0,11‖K0,1+K0,9的值存入表L。

end for

for每個(gè)K0,9和K0,3+K0,11do

計(jì)算s0,{12,13,14,15}和s7,{8,9,10,11}。如果K7,9=s7,8+s7,15，計(jì)算s7,0=s7,13+s7,10+s7,7+K7,3，對(duì)表格L索引得到其對(duì)應(yīng)的K0,11‖K0,1+K0,9，計(jì)算得到K0,{1,3,9,11}。將對(duì)應(yīng)的K0進(jìn)行加密驗(yàn)證。

ifK0通過(guò)驗(yàn)證 then

returnK0。

end if

end for

end for

end for