劉靜頤，劉韻雯，孫 兵，屈龍江

（國防科技大學(xué)文理學(xué)院，湖南 長沙 410073）

0 引言

分組密碼是對稱密碼中十分重要的一類密碼算法，其數(shù)學(xué)模型是將明文消息編碼表示后的數(shù)字序列，劃分成長度為n的組，每組分別在密鑰的控制下變換成等長的輸出數(shù)字序列。AES 算法是具有SP（Substitution-Permutation）結(jié)構(gòu)的分組密碼算法之一。自2001 年AES 算法被確定為美國新數(shù)據(jù)加密標(biāo)準(zhǔn)以來，對AES 的分析一直是密碼學(xué)的研究重點。AES 的結(jié)構(gòu)具有良好的抗差分分析和線性分析能力，傳統(tǒng)的分析方法對AES 攻擊并不能起到很好的作用，許多其他的攻擊方法因此應(yīng)運而生，如：Boomerang 攻擊、Square 攻擊等。

2015 年FSE 上，T.Tiessen 等[1]利用積分攻擊思想對帶有單個秘密S 盒的AES 算法進(jìn)行了攻擊，并且進(jìn)行了對4 輪至6 輪AES 的密鑰恢復(fù)與S 盒信息恢復(fù)。在2016 年美密會上，孫兵等[2]提出了AES 的首個5 輪區(qū)分器，利用AES 列混合矩陣的性質(zhì)，他們將AES 的4 輪積分性質(zhì)擴(kuò)展到了5 輪，并且不需要S 盒的信息，但該區(qū)分器的構(gòu)造需要整個輸入空間，因此數(shù)據(jù)復(fù)雜度高達(dá)2128。2016 年，L.Grassi 等[3]提出了子空間路徑的分析方法。子空間路徑分析是基于明文空間的某些特定子空間加密路徑的分析方法，可以對帶秘密S 盒的AES 算法進(jìn)行有效攻擊.利用該方法，Grassi[3]構(gòu)造了AES 的4輪不可能差分區(qū)分器，并且攻擊了5 輪AES，將首輪密鑰候選值減少到232個。2017 年，Grassi 等[4]提出了首個不需要密鑰信息的AES 的5 輪選擇明文區(qū)分器，通過限定輸入與輸出空間，經(jīng)過5 輪AES加密后，輸入空間中明文對應(yīng)的密文差分落在輸出空間中的個數(shù)始終為8 的倍數(shù)，其數(shù)據(jù)復(fù)雜度僅為232。2019 年，Grassi[5]利用不變子空間與子空間路徑，構(gòu)造了弱密鑰下AES 的5 輪子空間路徑，對5 輪AES 與隨機(jī)置換進(jìn)行了區(qū)分，弱密鑰量為232。目前沒有一種行之有效的攻擊方法可比窮搜攻擊更快地攻擊全輪AES，在此情況下，對于減輪版本AES 的攻擊就變得十分有意義。對減輪AES 的有效攻擊可以對AES 算法的剩余安全裕度進(jìn)行評估，即目前成功攻擊輪數(shù)與AES 全部輪數(shù)之比；此外，對減輪AES 的攻擊成果還可用于攻擊以減輪AES 為組件的算法，例如使用4 輪AES 的ZORRO[6]，LED[7]和AEZ[8]，以及使用5 輪AES 的WEM[9]，Hound[10]和ELmD[11]。

目前，雖然對帶有秘密S 盒AES 攻擊的最高輪數(shù)為Tiessen 等[1]提出的6 輪攻擊，但在S 盒信息完全未知的情況下，Grassi 等[3]提出的子空間路徑分析方法最為有效，能對5 輪AES 算法進(jìn)行密鑰恢復(fù)。本文基于子空間路徑分析方法，研究得到了弱密鑰下的三條子空間路徑及其性質(zhì)，進(jìn)而構(gòu)造出在特定弱密鑰空間下對帶有秘密S 盒的AES 的2 個5 輪區(qū)分器。

本文主要結(jié)構(gòu)如下:第一節(jié)為準(zhǔn)備工作，簡要介紹AES 算法，對不變子空間的主要定義定理進(jìn)行詳細(xì)介紹，介紹了子空間路徑的相關(guān)定義，第二節(jié)詳細(xì)介紹文獻(xiàn)[3]給出的低輪子空間路徑，第三節(jié)先構(gòu)造出弱密鑰下AES 的幾條子空間路徑，其次利用構(gòu)造出的子空間路徑，得出帶秘密S 盒AES 的2個弱密鑰下的5 輪區(qū)分器，給出了兩個區(qū)分器所需的數(shù)據(jù)復(fù)雜度與計算復(fù)雜度，第四節(jié)為總結(jié)與展望。

1 準(zhǔn)備工作

1.1 AES 算法

AES 算法（Advanced Encryption Standard）是美國2001 年采用的新數(shù)據(jù)加密標(biāo)準(zhǔn)，標(biāo)準(zhǔn)采用了Joan Daemen 和Vincent Rijmen 設(shè)計的Rijndael 分組密碼算法[12]。AES 算法采用SPN 結(jié)構(gòu)，分組長度為128 比特，密鑰長度為128、192、256。在加密與解密過程中，128 比特信息寫為4×4 的狀態(tài)矩陣，矩陣中的元素為82F 中的元素。根據(jù)密鑰長度的不同，AES 算法的輪數(shù)也有區(qū)別：AES-128 的輪數(shù)為10，AES-192 的輪數(shù)為12，而AES-256 的輪數(shù)為14。AES 算法的輪函數(shù)包括四種變換：字節(jié)代替變換（SB）、行移位變換（SR）、列混合變換（MC）以及密鑰加變換（AK）。

因此，AES 的輪函數(shù)可寫為以上四種變換的復(fù)合：R(x)=AK?MC?SR?SB(x)。需要注意的是，在AES 算法的第一輪加密前存在白化密鑰的異或，在最后一輪加密中省略列混合變換。

AES-128 的密鑰生成算法如圖1 所示。

圖1 AES-128 的密鑰生成算法

本文中統(tǒng)一將AES 的輪函數(shù)寫為R，第i輪輪函數(shù)為R(i)，強(qiáng)調(diào)輪密鑰時，寫為Rk，若稱x為加密（解密）過程中的一個狀態(tài)，則xij則表示x對應(yīng)狀態(tài)矩陣的第i行第j列上的元素。

1.2 不變子空間與子空間路徑

2011 年G.Leander 等[13]在美密會上提出了不變子空間的概念，并將其用于PRINTcipher 上，對PRINTcipher 進(jìn)行了全輪的攻擊。其中心思想是構(gòu)造一個狀態(tài)子空間，若該子空間歷經(jīng)一輪或多輪加密后仍能保持子空間結(jié)構(gòu)上的不變性，那么這種非隨機(jī)現(xiàn)象便可用于構(gòu)造針對該算法的區(qū)分器。在此基礎(chǔ)上，Grassi 等[3]提出了子空間路徑的概念，子空間路徑不強(qiáng)調(diào)子空間結(jié)構(gòu)在輪函數(shù)下的不變性，而是表現(xiàn)了子空間結(jié)構(gòu)在輪函數(shù)下變化的規(guī)律，進(jìn)而利用具有一定規(guī)律的子空間路徑建立區(qū)分器。自提出以來，子空間路徑分析主要被用于對AES 及PRINCE 等SPN 結(jié)構(gòu)密碼算法的攻擊，利用該方法在構(gòu)造區(qū)分器或進(jìn)行密鑰恢復(fù)時，不需要S 盒與密鑰的相關(guān)信息，對輪函數(shù)的分支數(shù)與擴(kuò)散性也進(jìn)行了一定側(cè)面刻畫。

定義1.1.[5]設(shè)Fk(·)=F(·)⊕k為某分組密碼的輪函數(shù)，子空間，使得Fk(U⊕a)=U⊕b，則稱U為Fk的一個不變子空間，其中U⊕a={u⊕a|?u∈U}。

性質(zhì)1.1.[5]設(shè)

若輪密鑰k0,…,kr∈IS，則 IS為AES 的一個r輪不變子空間。

性質(zhì)1.2.[5]設(shè)

若k∈Kweak，，?x∈IS，有R2(x)∈IS +k′，即 IS 在弱密鑰空間Kweak下為AES 的兩輪不變子空間。

換言之，若初始密鑰（白化密鑰）k∈Kweak，?a,b∈IS，都有R2(a)⊕R2(b)∈IS。由于AES 具有良好的擴(kuò)散性質(zhì)，目前尚未找到全密鑰下多輪非平凡不變子空間。顯然，不變子空間分析方法對算法結(jié)構(gòu)及輪函數(shù)的限制較為嚴(yán)格，因此Grassi 在此基礎(chǔ)上進(jìn)行了改進(jìn)，提出子空間路徑的概念：

定義1.2.[3]設(shè)(V1,V2,…,Vr+1)為維數(shù)遞增的r+1個子空間，若使得，則稱(V1,V2,…,Vr+1)為FK的長度為r的子空間路徑。

定義1.3.[3]令為第i行第j列的元素等于1、其他位置全為0 的矩陣。根據(jù)AES 輪函數(shù)的構(gòu)造及其性質(zhì)，可構(gòu)造多輪的子空間路徑。先定義如下幾種基礎(chǔ)子空間：

（1）列空間Ci=＜e0,i,e1,i,e2,i,e3,i＞，例如

（2）定義對角空間Di=SR-1(Ci)，例如：

其中α≡0x02。

引理1.1.[3]Di∩Cj=＜ei+j,j＞DI∩CJ=＜ej+i,j＞，其中i∈I，j∈J，且交空間的維度為|I|·|J|。

2 AES 的子空間路徑

2.1 AES 的一輪與二輪子空間路徑

性質(zhì)2.1.[3]（1）設(shè)I?{0,1,2,3}，其中0 ≤|I|≤3，對，使得RK(DI⊕a)=，都有R(x1)⊕R(x2)∈CI。

（2）設(shè)I?{0,1,2,3}，其中0 ≤|I|≤3，，使得RK(CI⊕a)=MI⊕b，即，都有R(x1)⊕R(x2)∈MI。

以上為AES 的兩條概率為1 的一輪子空間路徑，將二者結(jié)合則可得到一條概率為1 的兩輪子空間路徑。

性質(zhì)2.2.[3]設(shè)I?{0,1,2,3}，其中0 ≤|I|≤3，，使得，即，都有R2(x1)⊕R2(x2)∈MI。

換言之，設(shè)I?{0,1,2,3}，且I≠?，都有Pr(R(2)(u)⊕R(2)(v)∈MI|u⊕v∈DI)=1。

2.2 AES 的三輪子空間路徑

前面回顧了AES 的兩條概率為1 的一輪子空間路徑以及一條概率為1 的兩輪子空間路徑。若將一輪子空間路徑與兩輪子空間路徑結(jié)合，可得到一條三輪子空間路徑，從而對更高輪數(shù)的AES 進(jìn)行攻擊。

兩條一輪子空間路徑分別為DI→CI、CI→MI，兩輪子空間路徑為DI→CI→MI，由于R-1(DI)與R(MI)不具有明顯的結(jié)構(gòu)特點，因此只對DI→DJ→CJ→MJ與DI→CI→CJ→MJ進(jìn)行研究。

引理2.1.[3]設(shè)I,J?{0,1,2,3}，?CI,DJ都 有Pr(x∈DJ|x∈CI)=(2-8)4|I|-|I|·|J|。

證明.根據(jù)條件概率公式：

DJ∩CI與CI的維數(shù)分別為|I|·|J|與4·|I|，即DJ∩CI與CI中元素的16 個字節(jié)中分別有|I|·|J|與4·|I|個字節(jié)非0。因此Pr(x∈DJ∩CI)=(2-8)16-|I|·|J|,P r(x∈CI)=(2-8)16-4·|I|，則

引理2.2.[3]設(shè)I,J?{0,1,2,3}，?MI,CJ都有Pr(x∈CJ|x∈MI)=(28)-4|I|+|I|·|J|。

引理2.3 的證明方法與引理2.2 基本相似，不做過多描述。

2.3 弱密鑰下的5 輪AES 區(qū)分器

根據(jù)上一節(jié)，當(dāng)初始密鑰為Kweak中的弱密鑰時，子空間 IS 經(jīng)過兩輪加密以后被映到自身的一個陪集IS +a。也即，若給定x,y∈IS，初始密鑰k∈Kweak，則有R2(x)⊕R2(y)∈ IS。又根據(jù) IS 與DI定義，可知

性質(zhì)2.3.[5]若I≡{0,2},{1,3}，則有

對于隨機(jī)置換∏，概率則為，因此可將AES 算法與隨機(jī)置換區(qū)分開。

3 對帶秘密S 盒AES 的分析

當(dāng)輪密鑰k1,…,kr∈IS 時，子空間 IS 為AES 算法的一個全輪的不變子空間，但當(dāng)輪密鑰為隨機(jī)選取時不能保持其加密過程中的結(jié)構(gòu)不變性。本節(jié)首先討論 IS 在AES 加密過程與密鑰擴(kuò)展算法中的性質(zhì)，在此基礎(chǔ)上，利用上節(jié)介紹的幾條子空間路徑，本文構(gòu)造出新的弱密鑰下AES 的子空間路徑，并給出了AES 算法的兩個5 輪區(qū)分器。

3.1 弱密鑰下AES 的子空間路徑

上一節(jié)介紹了AES 的子空間路徑DI→CI→MI與弱密鑰下的不變子空間 IS。若存在I∈{0,1,2,3}，使得CI,MI與 IS 間存在一輪路徑，則可將二者結(jié)合起來構(gòu)造出更高輪數(shù)的路徑。

為了更清楚地了解子空間CI在維數(shù)不同時是否存在到 IS 的路徑，我們對其進(jìn)行分類。首先我們討論|I|=2，即CI的維數(shù)等于8 時到 IS 的路徑。

I.|I|=2

|I|=2 即I∈{{0,1},{0,2},{0,3},{1,2},{1,3},{2,3}}。本文將|I|=2 分為兩大類情況進(jìn)行討論。

（1）I∈{{0,1},{0,3},{1,2},{2,3}}

當(dāng)輪密鑰k∈Kweak時，當(dāng)且僅當(dāng)以下方程組成立：

利用文獻(xiàn)[11]中求有限域上線性方程組的方法，解得上述方程組有且僅有平凡解，即當(dāng)且僅當(dāng)a=b=c=d=e=f=g=h≡0 時，方程組成立。

對于C{1,2},C{0,3},C{2,3}，一輪變換后（不考慮密鑰加）得到的方程組與C{0,1}相比僅在變量符號上進(jìn)行了變化，這是因為C{0,1},C{1,2},C{0,3},C{2,3}經(jīng)過一輪變換后得到的實際是四個相同列向量組合成的矩陣，得到的其實為同一個方程組。因此在I∈{{0,1},{0,3},{1,2},{2,3}}的情況下，CI經(jīng)過一輪變換后映到 IS 的概率為0。

（2）I∈{{0,2},{1,3}}

其中α=0x02。輪密鑰k∈Kweak時，要使,當(dāng)且 僅 當(dāng)a=e,b=f,c=g,d=h，即C{0,2}? IS。因此k∈Kweak時，C{0,2}經(jīng)過一輪變換后映到 IS 的概率為2-32。

定理3.1.|I|=2 時，CI經(jīng)過一輪AES 變換后映到IS 的概率為

定理3.2.|I|=1 時，CI中的明文對經(jīng)過一輪加密后（不考慮輪密鑰），密文差分落在子空間 IS 的概率為0，即Pr(R(x)⊕R(y)∈ IS|x,y∈CI)=0。

證明.以I={0}為例。設(shè)，不考慮輪密鑰加，C0經(jīng)過一輪加密后變?yōu)椋?/p>

由于字節(jié)代替變換（SB）不改變空間結(jié)構(gòu)，因此對上述證明過程無影響。顯然，要使，當(dāng)且僅當(dāng)a=c≡0，d=b≡0，因此從C0到 IS 的一輪不可能差分路徑得證。

AES-128 的逆密鑰生成算法如圖2 所示。

上述定理及其證明中，沒有考慮輪密鑰的參與，這是因為子空間IS 結(jié)構(gòu)的特殊性，當(dāng)C0到 IS的輪密鑰選取不當(dāng)時，有可能造成，但。

圖2 AES-128 的逆密鑰生成算法

顯然，k0,k1均不屬于 IS。根據(jù)上述輪密鑰的設(shè)定，R(D0)=C0+k0，不妨設(shè)，則∈C{0,1}。根據(jù)上文可知，，而，因此的概率也為0。

定理3.3.|I|=1 時，MI中的明文對經(jīng)過一輪加密后（不考慮輪密鑰），密文差分落在子空間 IS的概率為0，即。

3.2 帶秘密S 盒AES 的5 輪區(qū)分器

由上一小節(jié)，在k∈Kweak的弱密鑰下，?I∈{0,1,2,3},|I|=1，CI,MI經(jīng)過一輪變換后映到 IS的概率為0；?I∈{0,1,2,3},|I|=2 時，則有：

對于隨機(jī)置換，CI,MI經(jīng)過一輪變換后映到 IS的概率均為2-64。根據(jù)子空間路徑DI→CI與弱密鑰下的不變子空間，可構(gòu)造弱密鑰下AES 的一條4 輪路 徑：。

（1）不可能差分區(qū)分器

根據(jù)上一節(jié)所介紹，當(dāng)|I|=1 時，?MI,CI，有，其中R′=MC?SR?SB。在不考慮密鑰加的情況下，IS為AES 算法的不變子空間，考慮密鑰加時，則不一定；而當(dāng)密鑰空間進(jìn)行縮小，即初始密鑰k∈Kweak時，IS為AES 算法的兩輪不變子空間。以此為基礎(chǔ)，根據(jù)3.1.2 構(gòu)造的三輪不可能差分，我們可構(gòu)造弱密鑰下AES 的一條5 輪不可能差分，具體 為。

接下來用上述5 輪不可能差分構(gòu)造5 輪不可能差分區(qū)分器。為了對AES 與隨機(jī)置換進(jìn)行區(qū)分，我們要考慮以下兩種情況：

情形1：選取明文差分落在DI(|I|=1)中的明文對，用AES 算法對其進(jìn)行加密

情形2：選取明文差分落在DI(|I|=1)中的明文對，對其進(jìn)行隨機(jī)置換

若令m=233.3，DI中的明文對經(jīng)過隨機(jī)置換后至少有一對密文差分落在 IS 中的概率為95.18%（＞95%）。為了區(qū)分AES 算法與隨即置換，攻擊者需要構(gòu)造所有可能的密文對并計算最終在 IS中發(fā)生碰撞的密文對個數(shù)。233.3個明文可產(chǎn)生約265.6個密文對，因此在隨即置換下發(fā)生碰撞的個數(shù)應(yīng)為265.6·264=21.6≈3，在AES 下發(fā)生碰撞的個數(shù)應(yīng)為265.6·0=0。

（2）弱密鑰下的5 輪區(qū)分器

根據(jù)引理2.2 與 引理2.3，?MI,CJ，都有Pr(x∈CJ|x∈MI)=(2-8)4·|I|-|I|·|J|，|J|=2，且J∈{{0,2,{1,3}}}時，Pr(x∈CJ|x∈MI)=(2-8)4·|I|-|I|·2=2-16·|I|，因此可構(gòu)造AES 的一條5 輪子空間路徑：，其每一輪的概率為。

|I|=1 時，對于AES 算法，該子空間路徑的概率為2-16×2-32=2-48，對于隨機(jī)置換，上述路徑的概率為2-64。

|I|=2 時，對于AES 算法，該子空間路徑的概率為2-32×2-32=2-64，對于隨機(jī)置換，上述路徑的概率為2-64，此時無法對AES 與隨機(jī)置換進(jìn)行區(qū)分。

|I|=3 時，對于AES 算法，該子空間路徑的概率為2-48×2-32=2-80，對于隨機(jī)置換，上述路徑的概率為2-64。

接下來用5 輪子空間路徑構(gòu)造5 輪AES 區(qū)分器。以I={0,1,3}為例，為了區(qū)分AES 加密與隨機(jī)置換加密，我們需要比較以下兩種情況：

情形1：選取明文差分落在DI中的明文對，用AES 算法對其進(jìn)行加密

情形2：選取明文差分落在DI中的明文對，對其進(jìn)行隨機(jī)置換

通過選取一對差分落在DI中的明文，分別用AES 算法與隨機(jī)置換對其進(jìn)行加密，情形1 得到的密文差分以2-80的概率落在不變子空間 IS中，而在情形2 中，5 輪加密后的差分則以2-64的概率落在IS 中。根據(jù)不可能差分區(qū)分器可知，令明文數(shù)量m=233.3時，經(jīng)過隨即置換后至少有一組密文差分落在 IS 中的概率為95.18%（＞95%）。233.3個明文可產(chǎn)生約265.6個密文對，因此在隨即置換下發(fā)生碰撞的個數(shù)應(yīng)為265.6·264=21.6≈3，在AES 下發(fā)生碰撞的個數(shù)應(yīng)為265.6·2-80=2-14.4≈0。

4 結(jié)語

本文基于Grassi 的子空間路徑分析與Leander的不變子空間分析方法，將子空間路徑分析的結(jié)果進(jìn)行推廣，研究得到了3 條新的AES 的子空間路徑。通過在弱密鑰下，限制明文差分與對應(yīng)的密文差分分別落在選定的空間，可將AES 算法與隨機(jī)置換區(qū)分，構(gòu)造出弱密鑰下的2 個5 輪AES 區(qū)分器，選擇明文量均為233.3。較之Lorenzo Grassi 的弱密鑰5輪區(qū)分器，本文構(gòu)造的區(qū)分器輪數(shù)相同，但在實際進(jìn)行區(qū)分時具有更低的數(shù)據(jù)復(fù)雜度。在下一步工作中，我們將考慮利用MILP 等方法來尋找，當(dāng)明文空間維數(shù)提高時基于子空間路徑與不變子空間的區(qū)分器，并利用子空間路徑分析方法對其他具有秘密S 盒的SPN 型算法以及類AES 算法進(jìn)行分析。