三輪和四輪AES的新型區分器

王美琴　胡凱　高超

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

關鍵詞：高級加密標準；AES；區分器

中圖分類號：O236.2 文獻標識碼：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 引言

網絡空間的發展是當今世界科技變革的代表性領域。網絡空間的安全問題也是各國重點關注的議題[1]。密碼學是網絡空間安全的基礎學科，密碼算法是保障網絡安全的必備工具。自從AES公布以來，已經成為最被廣泛使用的加密算法，研究AES的安全性有著重要意義。

2 研究背景與貢獻

2.1 研究背景

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

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

本文探索AES的列混合的系數信息在三輪AES和四輪AES場景下的應用，從而加深對相應輪數的AES安全性的認識。

2.2 本文貢獻

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

3 符號約定與準備工作

3.1 符號約定

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

3.2 AES

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

其中MC使用的矩陣是

，

注意MC矩陣的每一列都有兩個相同的系數 1。AES的更多細節請參考其設計文檔[1]。

4 新的三輪AES區分器

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

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

。

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

證明：P0，0是遍歷的，其他字節是常數，AK和SB都是字節上的置換，SR不會改變字節內部狀態，所以也是遍歷的，其他字節仍然是常數。經過MC上的矩陣乘法，四個字節，，，都是遍歷的。經過接下來的AK，SB， SR操作，遍歷的四個字節變成了，，，，其他字節是常數。也就是每列都是一個遍歷的字節和三個常數。考慮第一列，經過MC之后，有

，

。

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

。

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

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

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

5 新的四輪AES區分器

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

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

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

四輪的區分器需要232個選擇明文，232次內存訪問以更新計數器，存儲復雜度仍然是256個字節。

6 結束語

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

參考文獻

[1] 李偲，先喻.美國網絡空間戰略的安全化問題研究[J].網絡空間安全，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-），女，山東人，教授；主要研究方向和關注領域：對稱密碼的分析與設計。

胡凱（1992-），男，山東人，碩士研究生；主要研究方向和關注領域：對稱密碼的分析與設計。

高超（1981-），男，山東人，碩士研究生；主要研究方向和關注領域：對稱密碼的分析與設計。