三輪和四輪AES的新型區(qū)分器

王美琴　胡凱　高超

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

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

中圖分類號(hào)：O236.2 文獻(xiàn)標(biāo)識(shí)碼：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ò)空間的安全問(wèn)題也是各國(guó)重點(diǎn)關(guān)注的議題[1]。密碼學(xué)是網(wǎng)絡(luò)空間安全的基礎(chǔ)學(xué)科，密碼算法是保障網(wǎng)絡(luò)安全的必備工具。自從AES公布以來(lái)，已經(jīng)成為最被廣泛使用的加密算法，研究AES的安全性有著重要意義。

2 研究背景與貢獻(xiàn)

2.1 研究背景

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

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

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

2.2 本文貢獻(xiàn)

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

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

3.1 符號(hào)約定

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

3.2 AES

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

其中MC使用的矩陣是

，

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

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

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

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

。

也就是等于某個(gè)值的個(gè)數(shù)一定是個(gè)偶數(shù)。然而，對(duì)于隨機(jī)置換來(lái)說(shuō)，此事件出現(xiàn)的概率約為2-128。

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

，

。

由于對(duì)256個(gè)明文來(lái)說(shuō)，上述兩式的右邊三項(xiàng)都分別是一個(gè)固定常數(shù)，而第一項(xiàng)都是遍歷項(xiàng)，所以有

。

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

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

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

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

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

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

也就是等于某個(gè)值的個(gè)數(shù)一定是個(gè)偶數(shù)。然而，對(duì)于隨機(jī)置換來(lái)說(shuō)，此事件出現(xiàn)的概率約為2-128。

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

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

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

參考文獻(xiàn)

[1] 李偲，先喻.美國(guó)網(wǎng)絡(luò)空間戰(zhàn)略的安全化問(wè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.

作者簡(jiǎn)介：

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

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

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