ARIA分組密碼算法的不可能差分攻擊

謝高淇 衛宏儒

(北京科技大學數理學院 北京 100083) (xiegaoqi@sina.cn)

ARIA密碼算法[1]是韓國國家安全研究所提出的一種SPN(substitution-permutation network)結構[2]的密碼算法，隸屬于分組密碼算法[3]，在2004年時，韓國工業部、商業部和能源部確定ARIA為韓國分組密碼算法標準.在結構上，ARIA密碼算法和AES(advanced encryption standard)算法[4-5]很相似，故很多用來分析AES算法的分析方法可以用來對ARIA密碼算法進行分析，并取得了很好的效果.本文類比對AES算法的分析，結合對ARIA密碼算法的研究，實現對ARIA密碼算法新的攻擊.

從文獻[6-7]可知，不可能差分分析方法是由Biham和Knudsen提出的，一種使用不可能出現的差分即概率為0的差分特征過濾錯誤密鑰猜測，從而得到正確密鑰值的分析方法.一經提出，該方法便得到了廣泛的應用，被應用于分析密碼結構與算法.尤其是對AES算法的分析中效果良好，ARIA密碼算法和AES算法結構上相似，不可能差分分析針對ARIA密碼算法的分析也取得了非常好的效果.

1 算法ARIA

1.1 符號說明

本文所使用符號具體釋義如表1所示：

Table 1 Symbol Description表1 符號說明

1.2 ARIA算法介紹

ARIA密碼算法是SPN結構型分組密碼，分組長度為128 b，密鑰長度為128 b,192 b,256 b，相應的輪數分別為12輪、14輪和16輪[8].128 b的數據分組對應一個4×4的表格，共16 B，如圖1所示.

Fig. 1 The state of 128 b on ARIA圖1 ARIA的128 b狀態

ARIA的輪函數由3個部件構成：

1) 混淆層(substitution layer,SL)

選用2個S盒S1和S2以及它們的逆S-11和S-12.每一個S盒定義為F28上的1個可逆的非線性變換函數S：{0,1}8→{0,1}8.ARIA有2種類型的S盒層：

奇數輪采用的變換為

偶數輪采用的變換為

2) 擴散層(diffusion layer,DL)

擴散層是一個{0,1}8×16→{0,1}8×16的映射，為16 B的線性運算：

(y0,y1,…,y15)T=L°(x0,x1,…,x15)T，

其中，L(x)表示線性函數，“°”是復合運算符.

其中：

y0=x3⊕x4⊕x6⊕x8⊕x9⊕x13⊕x14，
y1=x2⊕x5⊕x7⊕x8⊕x9⊕x12⊕x15，
y2=x1⊕x4⊕x6⊕x10⊕x11⊕x12⊕x15，
y3=x0⊕x5⊕x7⊕x10⊕x11⊕x13⊕x14，
y4=x0⊕x2⊕x5⊕x8⊕x11⊕x14⊕x15，
y5=x1⊕x3⊕x4⊕x9⊕x10⊕x14⊕x15，
y6=x0⊕x2⊕x7⊕x9⊕x10⊕x12⊕x13，
y7=x1⊕x3⊕x6⊕x8⊕x11⊕x12⊕x13，
y8=x0⊕x1⊕x4⊕x7⊕x10⊕x13⊕x15，
y9=x0⊕x1⊕x5⊕x6⊕x11⊕x12⊕x14，
y10=x2⊕x3⊕x5⊕x6⊕x8⊕x13⊕x15，
y11=x2⊕x3⊕x4⊕x7⊕x9⊕x12⊕x14，
y12=x1⊕x2⊕x6⊕x7⊕x9⊕x11⊕x12，
y13=x0⊕x3⊕x6⊕x7⊕x8⊕x10⊕x13，
y14=x0⊕x3⊕x4⊕x5⊕x9⊕x11⊕x14，
y15=x1⊕x2⊕x4⊕x5⊕x8⊕x10⊕x15.

3) 輪密鑰加(round key addition,RKA)

中間狀態與128 b的輪子密鑰進行異或操作，輪子密鑰由密鑰編排算法生成.

2 不可能差分攻擊

差分密碼分析利用高概率特征(或差分)恢復密鑰，而不可能差分密碼分析方法的基本思想是利用概率為0的特征(或差分)，排除那些導致特征(或差分)概率為0的候選密鑰.對于一條概率為0的差分路徑，當使用正確密鑰解密密文對時，得不到符合該路徑的差分；但若使用猜測密鑰解密密文對時，得到符合該路徑的差分，則該猜測密鑰值是錯誤的；通過這種方法來篩去所有的錯誤密鑰猜測值，那么剩下的就是需要恢復的正確密鑰.

利用不可能差分分析對r輪迭代密碼進行分析的流程為：

步驟1. 尋找r-1輪差分α0→αr-1，使此特征成立的概率為0.

步驟2. 選擇明文對(P,P⊕α0)，滿足差分為α0，并進行r輪加密，所得密文記作C和C*.

步驟3. 猜測第r輪輪密鑰kr的所有可能值，對每一個猜測密鑰分別對C和C*解密1輪，所得到的值記作D和D*；判斷D⊕D*=αr-1是否成立，如果成立則對應的猜測值一定是錯誤密鑰.

步驟4. 重復上述步驟，直到密鑰唯一確定為止.

Fig. 2 Features of impossible differential on ARIA圖2 ARIA不可能差分性質

假設通過上述攻擊可以得到|K|位密鑰，每個明密文對可以淘汰2-t的密鑰量，為保證正確的密鑰被唯一確定，所需要的明密文對N必須滿足：

(2|K|-1)×(1-2-t)N<1，

當t比較大時可得：

N>2t×ln 2×|K|≈2t-0.53|K|，

觀察此式可以發現，在實現不可能差分密碼分析時，所需要猜測的密鑰量基本不影響數據復雜度，這便是和其他攻擊的不同之處.不可能差分密碼分析方法的數據復雜度主要是由每個明密文對所能淘汰密鑰的概率所決定的.

3 7輪ARIA算法的不可能差分攻擊

本文要構造7輪ARIA密碼算法的不可能差分攻擊，在新的4輪不可能差分路徑的前邊增加2輪，后邊增加1輪，得到新的7輪不可能差分攻擊路徑.然后利用ARIA密碼算法擴散層的性質，過濾無用的明密文對，大大降低復雜度，構成新的7輪ARIA算法的不可能差分攻擊.

3.1 ARIA密碼算法的2個性質

性質1. 如圖2所示，給定一明文對，滿足僅在字節(1,12)處取值不相等，其他字節處相等.在經過4輪變換后，密文對不滿足3個性質：

1) 2個密文在字節(3,11,12,13)處不相等；

2) 密文在其他字節處相等；

3) 密文差分在(3,11,12,13)處相等.

即：

(0,a1,0,0,0,0,0,0,0,0,0,0,a12,0,0,0)|→
(0,0,0,f,0,0,0,0,0,0,0,f,f,f,0,0)

是不可能的，其中a1,a12,f是非0值.

證明. ARIA的4輪變換可以分為前2輪變換和后2輪變換這2部分.

對于前2輪變換.假設輸入差分為

(0,a1,0,0,0,0,0,0,0,0,0,0,a12,0,0,0)，

因為是用同一密鑰對2個明文進行的加密運算，所以經過RKA后差分沒有發生變化.

經過SL，差分變為

(0,b1,0,0,0,0,0,0,0,0,0,0,b12,0,0,0)，

其中，b1,b12為非0字節.

隨后進行第1輪DL變換，差分變為

p=232264=2-32，

然后進行第2輪RKA和SL變換，差分變為

(0,c1,c2,0,0,c5,c6,c7,c8,c9,0,c11,c12,0,0,c15)，

再進行第2輪的DL變換，差分變為

(d0,d1,…,d15)，

其中，有d6=d11=c2⊕c7⊕c9⊕c12.

至此，完成了ARIA前2輪變換.

再考慮：

(0,0,0,f,0,0,0,0,0,0,0,f,f,f,0,0)

經過2輪變化的逆過程.

經過1次DL-1變換，變成

(0,f,0,0,f,f,0,0,f,0,0,0,0,0,0,0)，

然后再經過1次SL-1變換，差分變為

(0,e1,0,0,e4,e5,0,0,e8,0,0,0,0,0,0,0)，

其中，e1,e4,e5,e8為非0值.

又因為異或子密鑰不改變差分值，故直接繼續進行下一次DL-1，差分變為

(e4⊕e8,e5⊕e8,e1⊕e4,e5,e5⊕e8,e1⊕e4,
0,e1⊕e8,e1⊕e4,e1⊕e5,e5⊕e8,e4,e1,e8,
e4⊕e5,e1⊕e4⊕e5⊕e8)，

再經過1次SL-1和RKA變換后，差分變為

至此，ARIA的2輪逆運算結束.

證畢.

c0=c13=b6⊕b8，

(1)

c3=c14=b5⊕b11，

(2)

c5=c8=b1⊕b15，

(3)

c2⊕c4⊕c7⊕c9⊕c10⊕c15=0.

(4)

同理可證明式(2)和式(3)都成立.

同時，有：

c2=b1⊕b6⊕b11⊕b15,
c4=b5⊕b8⊕b11⊕b15,
c7=b1⊕b6⊕b8⊕b11,
c9=b1⊕b5⊕b6⊕b11,
c10=b5⊕b6⊕b8⊕b15,
c15=b1⊕b5⊕b8⊕b15.

所以容易得證式(4)也是以概率1成立的.

p=248280=2-32.

證畢.

3.2 7輪ARIA的不可能差分攻擊過程

本文在3.1節已證明的4輪不可能差分路徑的前邊增加2輪變換，后邊增加1輪變換，得到新的7輪不可能差分攻擊，如圖3所示.其中ARIA密碼算法的最后1輪沒有擴散層，取而代之的是輪密鑰加(RKA).

攻擊過程如下：

步驟2. 取2N個上述結構(即2N×2223=2223+N個明文對).選取明文對中在(0,1,2,4,5,6,7,8,9,10,14,15)這12 B處差分為0的密文對，滿足這樣的密文對有2223+N×2-8×(16-4)=2127+N對.

Fig. 3 7-round impossible differential attacks on ARIA圖3 7輪ARIA不可能差分攻擊

步驟3. 猜測密鑰字節(k8,3,k8,11,k8,12,k8,13)，對每個保留下來的密文對(C,C)，分別進行計算：

步驟4. 猜測k1的14 B，并利用性質2進行分析.

步驟4.1. 假設剩余的密文所對應的明文對為(P,P)，猜測(k1,0,k1,13)，計算：

步驟4.2. 猜測(k1,3,k1,14)，計算：

步驟4.3. 類似地，猜測(k1,5,k1,8)密鑰字節，計算：

步驟4.4. 猜測(k1,2,k1,4,k1,7,k1,9,k1,10,k1,15)密鑰字節，計算：

選擇滿足：

相應明文對.此時剩余的明文對為279+N×2-8=271+N個.

步驟4.5. 猜測(k1,1,k1,12)的值，計算：

此時沒有條件，所以沒有過濾.

步驟5. 猜測(k2,1,k2,5,k2,6,k2,8,k2,11,k2,15)的值，計算：

3.3 復雜性分析

分析該攻擊的時間復雜度：

在步驟3中，若同時計算4 B的值，時間復雜度為

而實際上，只需3×2149即可.由于可以先對2 B的值進行計算，然后進行比較.如若相等，進行下一步的計算；如若不相等，可直接舍棄，從而達到降低復雜度的效果.對于剩余的對，使用相同的方法進行計算，并和前面的值相比較.如若相等，便保留，如若不相等，則舍棄.同理，對剩余的對，使用相同的方法進一步過濾.此方法稱為“early-abort”技術[8].

因為這一步只需要計算4 B的值，所以共需要

次1輪加密運算.

注意到下邊的每一步中都有應用“early-abort”技術.

因為在步驟4中，只有RKA和SL這2種運算，故可以認為每一次的運算都相當于23的1輪運算.

所以步驟4中：

步驟4.1需要

次1輪加密；

步驟4.2需要

次1輪加密；

步驟4.3需要

次1輪加密；

步驟4.4需要

次1輪加密；

步驟4.5需要

次1輪加密；

步驟4.6只有DL變換操作，所以需要

次1輪加密.

步驟5需要的復雜度為

次1輪加密.

所以總的攻擊復雜度為

次7輪加密運算.

從分析過程中的步驟1中可知，本文選擇明文數為2112，并選擇2N個結構，其中N=7，所以本文攻擊共需要2119選擇明文.

綜上，本文的攻擊復雜度為：2119選擇明文和大約2218次7輪加密運算.

4 8輪ARIA算法的不可能差分攻擊

本文要構造8輪ARIA密碼算法的不可能差分攻擊，類似構造7輪ARIA密碼算法的不可能差分攻擊，在新的4輪不可能差分路徑的前邊增加2輪，后邊增加2輪，得到新的8輪不可能差分路徑.然后利用ARIA密碼算法擴散層的性質，過濾掉無用的明密文對，從而構成8輪ARIA算法的不可能差分攻擊.

4.1 ARIA密碼算法的另一性質

h0=h10=h13=g6⊕g13,

(5)

h2=h9=h12=g11⊕g12,

(6)

h3⊕h4⊕h8=0,

(7)

h1⊕h5⊕h11=0,

(8)

h6⊕h7⊕h14=0.

(9)

同理可證明式(6)也是成立的.

Fig. 4 8-round impossible differential attacks on ARIA圖4 8輪ARIA不可能差分攻擊

同時，有h3=g11⊕g13，h4=g11，h8=g13.所以容易得證式(7)也是以概率1成立的.同理，h1=g12,h5=g3,h11=g3⊕g12,h6=g12⊕g13,h7=g3⊕g11⊕g12⊕g13,h14=g3⊕g11.所以式(8)和式(9)也是成立的.

證畢.

4.2 8輪ARIA的不可能差分攻擊過程

本文在3.1節的性質1已證明4輪不可能差分路徑的前邊增加2輪，后邊增加2輪，得到新的8輪不可能差分攻擊，如圖4所示.其中ARIA密碼算法的最后1輪沒有擴散層，取而代之的是輪密鑰加(RKA).

攻擊過程如下：

步驟2. 取2N個上述結構(即2N×2223=2223+N個明文對).選取明文對中在第16 B(15)處差分為0的密文對，滿足這樣的密文對有2223+N×2-8×(16-15)=2215+N對.

步驟3. 猜測密鑰字節

(k9,0,k9,1,k9,2,k9,3,k9,4,k9,5,k9,6,k9,7,
k9,8,k9,9,k9,10,k9,11,k9,12,k9,13,k9,14),

對每個保留下來的密文對(C,C)，分別進行如下計算：

步驟4. 猜測k8的15 B，并利用性質3進行分析.

步驟4.2. 猜測(k8,0,k8,10,k8,13)，并計算：

步驟4.3. 猜測(k8,2,k8,9,k8,12)，計算：

步驟4.4. 猜測(k8,3,k8,4,k8,8)密鑰字節，計算：

選擇滿足h3⊕h4⊕h8=0的明文對.剩余的明文對為239+N×2-8=231+N個.

步驟4.5. 猜測(k8,1,k8,5,k8,11)密鑰字節，計算：

選擇滿足h1⊕h5⊕h11=0的明文對.剩余的明文對為231+N×2-8=223+N個.

步驟4.6. 猜測(k8,6,k8,7,k8,14)密鑰字節，計算：

選擇滿足h6⊕h7⊕h14=0的明文對.剩余的明文對為223+N×2-8=215+N個.

步驟5. 猜測k1的14 B，并利用性質2進行分析.

步驟5.1. 假設剩余的密文所對應的明文對為(P,P)，猜測(k1,0,k1,13)，計算：

步驟5.2. 猜測(k1,3,k1,14)，計算：

步驟5.3.類似地，猜測(k1,5,k1,8)密鑰字節，計算：

步驟5.4. 猜測(k1,2,k1,4,k1,7,k1,9,k1,10,k1,15)密鑰字節，計算：

選擇滿足條件：

的明文對.此時剩余的明文對為2N-9×2-8=2N-17個.

步驟5.5. 猜測(k1,1,k1,12)的值，計算：

此時沒有條件，所以沒有過濾.

步驟6. 猜測(k2,1,k2,5,k2,6,k2,8,k2,11,k2,15)的值，計算：

4.3 復雜性分析

分析該攻擊的時間復雜度：

在步驟3中，本文依然使用“early-abort”技術，共需要

次1輪加密運算.

因為在步驟4中，只有RKA和SL這2種運算，故可以認為每一次的運算都相當于23的1輪運算.

所以步驟4中：

步驟4.1只有DL變換操作，所以需要

次1輪加密；

步驟4.2需要

次1輪加密；

步驟4.3需要

次1輪加密；

步驟4.4需要

次1輪加密；

步驟4.5需要

次1輪加密；

步驟4.6需要

次1輪加密.

在步驟5中，同理，只有RKA和SL運算，可以認為每一次的運算都相當于23的1輪運算.

所以步驟5中：

步驟5.1需要

次1輪加密；

步驟5.2需要

次1輪加密；

步驟5.3需要

次1輪加密；

步驟5.4需要

次1輪加密；

步驟5.5需要

次1輪加密；

步驟5.6只有DL變換操作，所以需要

次1輪加密.

步驟6需要的復雜度為

次1輪加密.

所以總的攻擊復雜度為

次8輪加密運算.

在分析過程步驟1中，本文選擇明文數為2112，并選擇2N個結構，其中N=95，所以本文攻擊共需要2207選擇明文.

綜上，本文的攻擊復雜度為：2207選擇明文和大約2346次8輪加密運算.

5 結 論

本文在證明不可能差分路徑成立的基礎上，根據ARIA密碼的結構特征，在第3節中，于不可能差分路徑前面增加2輪、后面增加1輪，實現了對ARIA分組密碼算法的新的7輪不可能差分分析.研究表明，此路徑下，7輪不可能差分攻擊共需要2119選擇明文和大約2218次7輪加密運算.與表2中7輪ARIA密碼算法的不可能差分攻擊結果相比較，攻擊進一步降低了數據復雜度和時間復雜度.在第4節，本文首次提出了對ARIA密碼算法的8輪不可能差分攻擊，在不可能差分路徑前面增加2輪、后面增加2輪，構成8輪ARIA密碼算法的新攻擊.研究表明，在此路徑下，8輪ARIA密碼算法的不可能差分攻擊共需要2207選擇明文和大約2346次8輪加密運算.但超過窮舉搜索的攻擊復雜度，故可認為在該路徑下8輪不可能差分攻擊中ARIA密碼算法是安全的.

Table 2 Summary of Cryptanalysis of ARIA by ImpossibleDifferential表2 ARIA密碼算法的不可能差分分析的安全性總結

在以后的研究中，著重尋找新的不可能差分路徑，證明新的不可能差分性質，嘗試降低8輪ARIA密碼算法不可能差分攻擊的時間復雜度和數據復雜度.由于ARIA算法和AES算法結構上相似，很多用來分析AES算法的分析方法對ARIA密碼算法肯定具有一定的效果，所以繼續對ARIA的其他分析方法進行研究，比如線性攻擊、中間相遇攻擊、積分攻擊等，提高對ARIA算法的攻擊輪數.同時，也可以將對ARIA密碼算法的分析方法遷移到對AES密碼算法的分析中，用來改進AES現有的分析結果.

[1]Daesung K, Jaesung K, Sangwoo P, et al. New block cipher: ARIA[G]LNCS 2971: Proc of the 6th Int Conf on Information Security and Cryptology. Berlin: Springer, 2004: 432-445

[2]Chen Shaozhen. The Basis of Cryptography[M]. Beijing: Science Press, 2008 (in Chinese)(陳少真. 密碼學基礎[M]. 北京: 科學出版社, 2008)

[3]Stinson D. Cryptography Theory and Practice[M]. Translated by Feng Dengguo. 3rd ed. Beijing: Publishing House of Electronics Industry, 2009 (in Chinese)(Stinson D. 密碼學原理與實踐[M]. 馮登國, 譯. 3版. 北京: 電子工業出版社, 2009)

[4]Liu Ya, Gu Dawu, Liu Zhiqiang, et al. New improved impossible differential attack on reduced-round AES-128[G]LNEE 114: Proc of Computer Science and Convergence. Berlin: Springer, 2012: 453-461

[5]Mala H, Dakhilalian M, Rijmen V, et al. Improved impossible differential cryptanalysis of 7-round AES-128[G]LNCS 6498: Proc of the 11th Int Conf on Cryptology in India. Berlin: Springer, 2010: 282-291

[6]Dunkelman O. Techniques for cryptanalysis of block ciphers[D]. Haifa, Israel: Technion-Israel Institute of Technology, Faculty of Computer Science, 2006

[7]Biryukov A, Wagner D. Slide attacks[G]LNCS 1636: Proc of the 6th Int Workshop on Fast Software Encryption. Berlin: Springer, 1999: 245-259

[8]Du Chenghang. Impossible differential analysis and middle encounter attack of block cipher algorithm ARIA[D]. Jinan: Shandong University, 2011 (in Chinese)(杜承航. 分組密碼算法ARIA的不可能差分分析和中間相遇攻擊[D]. 濟南: 山東大學, 2011)

[9]Wu Wenling, Zhang Wentao, Feng Dengguo. Impossible differential cryptanalysis of reduced-round ARIA and Camellia[J]. Journal of Computer Science and Technology, 2007, 22(3): 449-456

[10]Li Shenhua, Song Chunyan. Improved impossible differential cryptanalysis of ARIA[C]Proc of the 2008 Int Conf on Information Security and Assurance. Los Alamitos, CA: IEEE Computer Society, 2008: 129-132

[11]Du Chenghang, Chen Jiezhe. Impossible differential cryptanalysis of ARIA reduced to 7 rounds[G]LNCS 6467: Proc of the 9th Int Conf on Cryptology and Network Security. Berlin: Springer, 2010: 20-30

[12]Su Chongmao. New impossible differential attack on 7-round reduced ARIA[J]. Journal of Computer Applications, 2012, 32(1): 45-48 (in Chinese)(蘇崇茂. 7輪ARIA-256的不可能差分新攻擊[J]. 計算機應用, 2012, 32(1): 45-48)

XieGaoqi, born in 1994. Master. His main research interests include cryptanalysis of block ciphers.

WeiHongru, born in 1963. Associate professor. His main research interests include mathematics, information security and cryptography, and key technologies of Internet of things.