王美琴　胡凱　高超

摘 要：高級加密標(biāo)準(zhǔn)（Advanced Encryption Standard，AES）是國際上最被廣泛使用的加密標(biāo)準(zhǔn)之一。近年來許多新設(shè)計的算法選擇使用縮減輪數(shù)的AES算法作為底層算法，所以縮減輪數(shù)AES的安全性，包括可區(qū)分性質(zhì)需要更加深入的研究。論文利用AES列混合的矩陣每列有兩個相同系數(shù)的性質(zhì)，給出三輪和四輪AES新的區(qū)分攻擊。新的區(qū)分攻擊與傳統(tǒng)的三輪和四輪積分區(qū)分器類似，擁有相同的數(shù)據(jù)和時間復(fù)雜度。

關(guān)鍵詞：高級加密標(biāo)準(zhǔn)；AES；區(qū)分器

中圖分類號：O236.2 文獻標(biāo)識碼：B

Abstract： Advanced Encryption Standard （AES） is one of the most widely used encryption algorithms all over the world. Recently， many new cryptography schemes are designed on the reduced-round AES so the security including the distinguishing property of AES deserves more study. This paper takes advantage of the fact that the matrix used in the MixColumn has two identical coefficients in each column to construct new distinguishes on 3-round and 4-round AES. These two new distinguishers are similar with the traditional integral distinguishers and have the same complexities of time and data.

Key words： advanced encryption standard； AES； distinguisher

1 引言

網(wǎng)絡(luò)空間的發(fā)展是當(dāng)今世界科技變革的代表性領(lǐng)域。網(wǎng)絡(luò)空間的安全問題也是各國重點關(guān)注的議題[1]。密碼學(xué)是網(wǎng)絡(luò)空間安全的基礎(chǔ)學(xué)科，密碼算法是保障網(wǎng)絡(luò)安全的必備工具。自從AES公布以來，已經(jīng)成為最被廣泛使用的加密算法，研究AES的安全性有著重要意義。

2 研究背景與貢獻

2.1 研究背景

想攻擊一個密碼算法，首先要發(fā)現(xiàn)該算法的區(qū)分器。密碼算法的區(qū)分器，是指密碼算法與一個隨機函數(shù)之間表現(xiàn)上的不同。隨后敵手可以利用此區(qū)分器對該密碼算法進行區(qū)分攻擊甚至是密鑰恢復(fù)攻擊。一般說來，區(qū)分攻擊弱于密鑰恢復(fù)攻擊。然而，由于近年來新的密碼算法體制的設(shè)計往往是基于已有的、被廣泛分析的密碼算法，密碼算法的可區(qū)分性質(zhì)受到了越來越多的關(guān)注。（縮短輪數(shù)的）AES從發(fā)布起經(jīng)受住了密碼學(xué)界的多種分析，其安全性被普遍認(rèn)可。所以，有不少新的密碼算法設(shè)計者會選擇縮短輪數(shù)的AES來構(gòu)建新算法。例如，征集認(rèn)真加密標(biāo)準(zhǔn)算法的CAESAR競賽[3]（Competition for Authenticated Encryption： Security， Application and Robustness）的候選算法AEGIS算法[4]選擇四輪AES作為狀態(tài)升級函數(shù)；ELmd算法[5]建議使用縮短輪數(shù)版本的AES算法作為底層算法。盡管這些新的密碼算法的安全性不完全依賴于底層算法的安全性，但是對于這些新設(shè)計的算法來說，底層算法的安全性包括可區(qū)分性質(zhì)仍然至關(guān)重要。

AES是被使用最廣泛的加密算法之一，其安全性備受關(guān)注。對AES的大量分析顯示，縮短輪數(shù)版本的AES存在區(qū)分器。傳統(tǒng)的AES區(qū)分器主要對三輪和四輪的AES版本起作用。例如，AES存在三輪和四輪的積分區(qū)分器[5]、四輪的不可能差分區(qū)分器[7]、四輪的零相關(guān)區(qū)分器[8]等。這些區(qū)分器都是比較通用的區(qū)分器，沒有考慮AES的很多組件的細(xì)節(jié)。例如，這些區(qū)分器都只利用了AES的列混合組件使用的矩陣的最大分支數(shù)是五這個性質(zhì)而沒有用到該矩陣的系數(shù)信息。在2016年的美密會上，孫兵等人首次利用了列混合組件的矩陣每列有兩個系數(shù)相等的信息，給出了五輪的AES零相關(guān)區(qū)分器和積分區(qū)分器[9]。由于這兩個區(qū)分器的表現(xiàn)形式和密鑰的具體信息有關(guān)，這種區(qū)分器后來被定義為密鑰相關(guān)區(qū)分器[10]。隨后，一大批針對五輪AES的區(qū)分器被提出[10-14]，大大提高了密碼學(xué)界對于AES安全性的認(rèn)識。

本文探索AES的列混合的系數(shù)信息在三輪AES和四輪AES場景下的應(yīng)用，從而加深對相應(yīng)輪數(shù)的AES安全性的認(rèn)識。

2.2 本文貢獻

在本文中，利用列混合的系數(shù)信息，分別給出針對三輪和四輪AES的區(qū)分攻擊。這兩種區(qū)分攻擊的時空復(fù)雜度和傳統(tǒng)的積分區(qū)分器相同，但是與積分區(qū)分器相比，新的區(qū)分器能夠識別更多算法的實現(xiàn)細(xì)節(jié)，也就是說，積分區(qū)分器只能識別出MC使用的矩陣的最大分支數(shù)是五，而新的區(qū)分器除此之外，還可以識別出該矩陣的每列上有兩個系數(shù)是相等的。盡管新的區(qū)分器都采用了列混合的系數(shù)信息，但與其他利用MC系數(shù)信息的區(qū)分器不同，我們的區(qū)分器是密鑰無關(guān)的，即最終區(qū)分器的表現(xiàn)在任何密鑰下都是一致的。

3 符號約定與準(zhǔn)備工作

3.1 符號約定

為了敘述的明確和方便，約定本文使用的符號和意義如表1所示。

3.2 AES

AES是一個分組長度為128比特的分組密碼算法，它采用SPN結(jié)構(gòu)。根據(jù)采用的密鑰長度，AES有三個版本，分別是AES-128、AES-192和AES-256，加密輪數(shù)分別是10輪、12輪和14輪。AES的128比特的明文、密文和內(nèi)部狀態(tài)可以寫成一個4×4的狀態(tài)矩陣，矩陣的每一個塊都是一個字節(jié)。AES的組件都是定義在有限域GF（28）上的操作，該有限域的不可約多項式是m（x）=x8+x4+x3+x+1。AES的每一輪的輪函數(shù)可以寫成R（x）=ak○MC○SR○SB（x）。

其中MC使用的矩陣是

，

注意MC矩陣的每一列都有兩個相同的系數(shù) 1。AES的更多細(xì)節(jié)請參考其設(shè)計文檔[1]。

4 新的三輪AES區(qū)分器

本節(jié)將介紹如何利用MC矩陣每一行有兩個相同的系數(shù)的性質(zhì)得到的一個新的三輪AES區(qū)分器。此區(qū)分器如命題1所述。

命題 1：對于三輪AES算法（不包含最后的MC操作），如果明文的第（0，0）字節(jié)是遍歷的，其他15個字節(jié)取任意常數(shù)，那么相應(yīng)的256個密文有如下性質(zhì)：

。

也就是等于某個值的個數(shù)一定是個偶數(shù)。然而，對于隨機置換來說，此事件出現(xiàn)的概率約為2-128。

證明：P0，0是遍歷的，其他字節(jié)是常數(shù)，AK和SB都是字節(jié)上的置換，SR不會改變字節(jié)內(nèi)部狀態(tài)，所以也是遍歷的，其他字節(jié)仍然是常數(shù)。經(jīng)過MC上的矩陣乘法，四個字節(jié)，，，都是遍歷的。經(jīng)過接下來的AK，SB， SR操作，遍歷的四個字節(jié)變成了，，，，其他字節(jié)是常數(shù)。也就是每列都是一個遍歷的字節(jié)和三個常數(shù)?？紤]第一列，經(jīng)過MC之后，有

，

。

由于對256個明文來說，上述兩式的右邊三項都分別是一個固定常數(shù)，而第一項都是遍歷項，所以有

。

結(jié)合接下來的AK和SB操作，因為AES的所有S盒都是相同的，我們有相當(dāng)于AES的S盒的輸出差分值，所有其每個可能的值出現(xiàn)的次數(shù)，必然是偶數(shù)，異或最后的密鑰不會改變這個結(jié)果。

對于隨機置換來說，256個值中，只要有128個值出現(xiàn)的次數(shù)是偶數(shù)，那么剩下的128個值出現(xiàn)的次數(shù)也必然是偶數(shù)，所以要想256個值出現(xiàn)的次數(shù)全部是偶數(shù)，只需要其中128個值是偶數(shù)即可。對于隨機置換， 個異或值是偶數(shù)的概率是2-128。證畢。

此區(qū)分器的數(shù)據(jù)復(fù)雜度是28，攻擊時需要對計數(shù)器進行28次累加操作，所以數(shù)據(jù)復(fù)雜度和時間復(fù)雜度與傳統(tǒng)的三輪積分區(qū)分器相同。但是此區(qū)分器需要存儲一個256個字節(jié)的計數(shù)器，這比三輪積分區(qū)分器略大。

5 新的四輪AES區(qū)分器

從第三節(jié)三輪AES區(qū)分器的細(xì)節(jié)來看，任意一個明文集合滿足一個字節(jié)是遍歷的，其余字節(jié)是常數(shù)，都可得到相似的結(jié)果。和高階積分類似，對于四輪AES，如果明文的（0，0），（1，1），（2，2），（3，3）字節(jié)是活躍的，可以將明文集合看成是224個滿足三輪區(qū)分器明文的集合，由于最后對每個異或值的個數(shù)進行統(tǒng)計是累加的，所以最后每個異或值的個數(shù)仍然是偶數(shù)。我們不加證明地給出命題2。

命題2：對于四輪AES算法（不包含最后的MC操作），如果明文的第（0，0），（1，1），（2，2），（3，3）字節(jié)是遍歷的，其他12個字節(jié)取任意常數(shù)，那么相應(yīng)的232個密文有如下性質(zhì)：

也就是等于某個值的個數(shù)一定是個偶數(shù)。然而，對于隨機置換來說，此事件出現(xiàn)的概率約為2-128。

四輪的區(qū)分器需要232個選擇明文，232次內(nèi)存訪問以更新計數(shù)器，存儲復(fù)雜度仍然是256個字節(jié)。

6 結(jié)束語

利用MC矩陣每列有兩個相同系數(shù)的性質(zhì)，給出了三輪和四輪AES新的區(qū)分器。這兩種區(qū)分器和傳統(tǒng)的三輪和四輪AES的積分區(qū)分器類似，數(shù)據(jù)和時間復(fù)雜度也相同，但是比積分區(qū)分器能夠識別更多的算法信息，也就是MC使用的矩陣每列有兩個相同的系數(shù)。新的區(qū)分器可以更好地理解MC的系數(shù)對AES算法安全性的影響，為以后的算法設(shè)計和分析提供指導(dǎo)。

參考文獻

[1] 李偲，先喻.美國網(wǎng)絡(luò)空間戰(zhàn)略的安全化問題研究[J].網(wǎng)絡(luò)空間安全，2018，01，21-6.

[2] Rijmen， J.D.V.， The Design of Rijndael：AES-The Advanced Encryption Standard. Edition 1 ed. 2001， Berlin： Springer-Verlag.

[3] CAESAR： Competition for Authenticated Encryption： Security， Applicability， and Robustness， https：//competitions.cr.yp.to/index.html.

[4] Hongjun Wu， B.P.， AEGIS： A Fast Authenticated Encryption Algorithm （v1.1. 2016），https：//competitions.cr.yp.to/round3/aegisv11.pdf.

[5] Nilanjan Datta， M.N.， Proposal of ELmD v2.1. 2016. https：//competition/cr.yp.to/round2/elmdv21.pdf.

[6] Knudsen， L. and D. Wagner. Integral Cryptanalysis. 2002. Berlin， Heidelberg： Springer Berlin Heidelberg. Page 112-127.

[7] Biham， E.， Keller， N.： `Cryptanalysis of reduced variants of Rijndael'， 3rdAES Conf.， 2000.

[8] Bagdonov A， Rijmen V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers. 2014： 369-83.

[9] Sun B， Liu M， Guo J， Qu L， Rijmen V. New Insights On AES-Like SPN Ciphers. In： Robshaw M， Katz J， eds.Berlin， Heidelberg： Springer Berlin Heidelberg， 2016： 605-24.

[10] Grassi L， Rechberger C， R?njom S. Subspace Trail Cryptanalysis and its Applications to AES. IACR Transactions on Symmetric Cryptology； Volume 2016， Issue 2. 2017.

[11] Cui T， Sun L， Chen H， Wang M. Statistical Integral Distinguisher with Multi-Structure and its Application on AES. In： Pieprzyk J， Suriadi S， eds.Cham： Springer International Publishing， 2017： 402-20.

[12] Grassi L， Rechberger C， R?njom S. A New Structural-Differential Property of 5-Round AES. In： Coron J， Nielsen JB， eds.Cham： Springer International Publishing， 2017： 289-317.

[13] R?njom S， Bardeh NG， Helleseth T. Yoyo Tricks with AES. In： Takagi T， Peyrin T， eds.Cham： Springer International Publishing， 2017： 217-43.

[14] Grassi L. MixColumns Properties and Attacks on （Round-Reduced） AES with a Single Secret S-Box. In： Smart NP， ed.Cham： Springer International Publishing， 2018： 243-63.

作者簡介：

王美琴（1974-），女，山東人，教授；主要研究方向和關(guān)注領(lǐng)域：對稱密碼的分析與設(shè)計。

胡凱（1992-），男，山東人，碩士研究生；主要研究方向和關(guān)注領(lǐng)域：對稱密碼的分析與設(shè)計。

高超（1981-），男，山東人，碩士研究生；主要研究方向和關(guān)注領(lǐng)域：對稱密碼的分析與設(shè)計。