分組密碼算法ARIA的不可能差分分析和中間相遇攻擊.pdf

1、21世紀是信息化時代，人們天天邀游在信息的海洋里。越來越多的人通過計算機網(wǎng)絡處理大量信息，如電子郵件、網(wǎng)上交易等。信息成為了人類社會發(fā)展的重要資源，成為了當今世界進步和發(fā)展的動力和核心。信息交互和信息傳輸過程中的信息安全問題變得越來越重要。信息安全直接關系到國家安全、電子商務的安全以及廣大民眾的個人隱私權的保護等問題。信息安全的重要性帶動了對密碼學的研究。密碼學作為一門保證數(shù)據(jù)信息安全的科學，得到越來越廣泛的研究和學習。密碼體制按照密鑰

2、共享的方式可以分為對稱密碼體制和公鑰密碼體制。對稱密碼主要包括分組密碼、流密碼和消息認證碼(MAC)，具有易于軟硬件實現(xiàn)、運行速度快、存儲量小等優(yōu)點。
　　 分組密碼是一種有效的帶密鑰的置換，將定長的明文轉換成等長的密文。分組密碼的加密密鑰和解密密鑰相同，或者都能由同一個主密鑰得出，而且加密和解密過程有典型的對稱特性。分組密碼在計算機通信和信息系統(tǒng)安全領域有著廣泛的應用。分組密碼的安全性分析是密碼學研究領域的熱點問題。本文重點研

3、究分組密碼的安全性。
　　 分組密碼算法的設計結構主要有兩種：一種是Feistel網(wǎng)絡結構。該結構每次只有一半的消息分組進入F函數(shù)，因此實現(xiàn)時具有占用硬件資源少的特點，適合在計算能力受限的條件下使用。1977年被確定為國際通用的分組加密標準的早期分組密碼加密標準DES[50]就是這種結構的分組算法中的典型代表。DES是2000年前應用最為廣泛的分組密碼算法。DES的分組大小為64比特，密鑰長度為56比特。另一種是代替-置換網(wǎng)絡(

4、SPN)結構?，F(xiàn)行的高級加密標準AES[15]就是這種結構的代表。AES具有128比特的消息分組長度，密鑰長度有128/192/256比特三種。其它很多分組密碼算法的設計也受到了DES和AES設計原理的影響，例如韓國分組密碼加密標準ARIA算法[40，52，53]就具有與AES十分相似的結構。該算法由幾名韓國密碼學者在2003年提出[52]，并于2004年改進到版本1.0[53]。它基于SPN網(wǎng)絡結構，最大分支數(shù)為8，支持128比特消息

5、分組及128/192/256比特的密鑰長度，對應加密輪數(shù)分別為12/14/16輪。輪函數(shù)是SPN結構，由輪密鑰異或、S盒變換和字節(jié)擴散變換組成。
　　 2003年，ARIA首次在韓國的信息安全年會中公開[52]。此時的版本為0.8，算法具有128比特消息分組，有128/192/256比特三種密鑰長度，分別對應10/12/14輪迭代。此版本中使用了兩個不同的S盒。其中一個S盒是AES的S盒。后來，ARIA在版本0.9[40]中變?yōu)?/p>

6、使用4個不同的S盒，迭代輪數(shù)沒有發(fā)生變化。最后，在現(xiàn)行版本1.0[53]中，又將迭代輪數(shù)增加2輪，變?yōu)?2/14/16輪，而且對密鑰生成算法進行了適當?shù)恼{整。2004年，韓國國家技術標準局(KATS)將這一版本在網(wǎng)頁http：//www.nsri.re.kr，ARIA/上公布，并在同年12月正式確定1.0版本的ARIA為韓國分組密碼算法加密標準(KS X1213)。
　　 由于ARIA與AES在結構上有很高的相似性，所以很多AE

7、S的分析方法都對ARIA有效。反之，對ARIA有效的分析方法也很有可能用來分析和攻擊AES。對ARIA安全性的分析也變得非常重要。
　　 算法的設計者Daesung Kwon等人首先給出了ARIA的分析[40]。其中包括差分和線性分析，截斷差分分析，不可能差分分析，積分攻擊，高階差分分析，插值攻擊等。后來于2004年，Alex Biryukov等人對版本0.8進行了安全性評估[11]。他們主要進行了截斷差分分析和專用線性分析。2

8、007年吳文玲等人提出了對版本0.9的6輪不可能差分分析[61]。2008年李申華對吳文玲的6輪不可能差分分析進行了改進[44]。2009年李艷俊提出了最多攻擊到7輪ARIA-256的積分攻擊[45]。唐學海[60]等人在2010年提出最多攻擊到8輪ARIA-256的中間相遇攻擊。
　　 本文中，對現(xiàn)行的1.0版本的ARIA算法進行了安全性分析，主要使用了不可能差分分析及中間相遇攻擊的分析方法，并有如下結果：
　　 (1

9、)7輪ARIA不可能差分分析2007年，吳文玲等人首次發(fā)現(xiàn)了4輪不可能差分特征，該特征如下：(c，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0)()(0，j，0，0，0，0，0，0，j，j，j，0，0，0，j，0)，其中c和j非零。
　　 基于此，吳文玲等人提出了第一個約減至6輪的ARIA不可能差分分析。
　　 李申華又于2008年對ARIA的不可能差分分析進行了改進，發(fā)現(xiàn)了新的不可能差分特征。利用這類特征

10、對六輪ARIA進行攻擊時，相對于吳文玲的不可能差分分析，可以分別減少猜測第1輪和第7輪輪密鑰的1字節(jié)，從而使需猜測的密鑰數(shù)由12字節(jié)減少到10字節(jié)，有效降低了不可能差分攻擊的時間復雜度。
　　 這個四輪不可能差分特征可以描述為：(0，c1，0，0，0，0，0，0，0，0，0，0，c12，0，0，0)()(0，0，0，j，0，0，0，0，0，0，0，j，j，j，0，0)，其中c1，C12和j非零。
　　 李的攻擊需要212

11、0個選擇明文和296次六輪加密運算，時間復雜度比吳文玲的攻擊降低了216。
　　 在此基礎上，對ARIA的不可能差分性質展開了進一步的研究。發(fā)現(xiàn)想進一步減少猜測密鑰的字節(jié)數(shù)幾乎是不可能的了。因此從其他方面入手。發(fā)現(xiàn)了擴散層的一種重要性質，然后結合我們構造的新的4輪不可能差分特征，給出了7輪ARIA-256的不可能差分分析。
　　 擴散層性質。由擴散層(DL)的線性表達式，及擴散層變換的自逆特性，發(fā)現(xiàn)了第一輪中進行擴散變換

12、前狀態(tài)的各字節(jié)之間的4個關系式，利用這4個關系式，可以有效過濾攻擊過程中無用的明文對，從而大大降低了時間復雜度，使得對ARIA的不可能差分分析能夠攻擊到7輪。
　　 這4個等式如下：△X1，5(S L)=△X1，8(S L)=△X1，15(S L)△X1，7(S L)=△X1，9(S L)=△X1，12(S L)△X1，0(S L)⊕△X1，1(S L)⊕△X1，10(S L)⊕△X1，11(S L)=0△X1，3(S L)⊕△

13、X1，4(S L)⊕△X1，10(S L)⊕△X1，13(S L)=0通過使狀態(tài)△X1(S L)的各字節(jié)滿足上述4個等式，能在進行擴散變換前以2-48的概率過濾明文對。
　　 也構造出了對應此4等式的4輪不可能差分特征，形式如下：
　　 4輪不可能差分特征。給定一對只在第3字節(jié)有差分且其他字節(jié)無差分的明文(X3，X'3)，經(jīng)過4輪加密運算后，密文對差分△X7不可能產生如下形式：(j，0，j，0，0，0，0，0，j，0，0

14、，j，0，0，0，0)，即密文對只在(0，2，8，11)4字節(jié)處有非零差分，在其他字節(jié)無差分。這一不可能差分性質可用下式表示：(0，0，c，0，0，0，0，0，0，0，0，0，0，0，0，0)()(j，0，j，0，0，0，0，0，j，0，0，j，0，0，0，0)其中c和j為任意非零值。
　　 在4輪不可能差分特征前邊加兩輪，后邊加一輪，構造我們的7輪不可能差分路線，并在第一輪中通過置換層后的狀態(tài)用4個等式進行過濾。攻擊共需212

15、5選擇明文和大約22387輪加密。
　　 (2)改進的7輪ARIA-256不可能差分分析在上述7輪不可能差分分析結果基礎上，我們經(jīng)進一步的研究，又發(fā)現(xiàn)了擴散層與上述性質類似的性質，不同的是，這次我們得到7個等式，并由此降低了上述7輪攻擊的數(shù)據(jù)和時間復雜度。
　　 這7個等式為：△X1.1(S L)=0△X1，4(S L)=0△X1，3(S L)△X1，6(S L)△X1.9(S L)=△X1，12(S L)△X1.11(

16、S L)=△X1，14(S L)△X1，2(S L)⊕△X1，5(S L)⊕△X1，8(S L)⊕△X1，10(S L)⊕△X1，15(S L)=0△X1，0(S L)⊕ AX1，2(S L)⊕△X1，5(S L)⊕△X1，7(S L)⊕△X1，8(S L)△X1，13(S L)=0我們也構造了適用于此7個等式的4輪不可能差分特征，并在特征前加2輪，后邊加1輪，構成新的7輪不可能差分路線。
　　 差分特征為：4輪不可能差分特征。

17、給定一對在第(10，15)字節(jié)有差分且其他字節(jié)無差分的明文(X3，X'3)，經(jīng)過4輪加密運算后，密文對差分△X7不可能產生如下形式：(0，j，0，j，0，0，0，0，0，j，j，0，0，0，0，0)，即密文對只在(1，3，9，10)4字節(jié)處有非零差分，在其他字節(jié)無差分。這一不可能差分性質可用下式表示：
　　 (0，0，0，0，0，0，0，0，0，c，0，0，0，0，0，c)()(0，j，0，j，0，0，0，0，0，j，j，0，0

18、，0，0，0)其中c和j為任意非零值。這一攻擊需要2121選擇明文和大約22197輪加密。
　　 (3)ARIA中間相遇攻擊ARIA算法的中間相遇攻擊最早由唐學海[60]等人提出，他們最多攻擊到8輪ARIA-256。8輪攻擊的數(shù)據(jù)復雜度為256，時間復雜度為2251.6，預計算復雜度為2252。而7輪ARIA-192攻擊需要2120個明文，2185.3次7輪ARIA-192加密運算，和2187次預計算。6輪攻擊的數(shù)據(jù)/時間/預計

19、算復雜度分別為256，2121.5，及2122.5。5輪攻擊需要25個明文，時間復雜度為265.4，預計算復雜度為2122.5。
　　 在此基礎上，結合2010年由Orr Dunkelman，Nathan Keller，and AdiShamir[24]等人提出的針對AES的中間相遇攻擊，提出了新的ARIA中間相遇攻擊的4輪區(qū)分器，并以此為基礎提出了新的最多攻擊到8輪的中間相遇攻擊，改進了唐學海等人的結果。
　　 4輪區(qū)

20、分器:如果δ-集的活性字節(jié)是第2字節(jié)，用4輪ARIA加密δ-集。則(無序)多重集()完全由以下30字節(jié)變量決定：-狀態(tài)X03(IN)的7字節(jié)1，4，6，10，11，12，15；-狀態(tài)X04(IN)的全部16字節(jié)；-輪密鑰k5的7字節(jié)1，4，6，10，11，12，15。所以，多重集完全由232字節(jié)變量決定。這一多重集共有2232個可能值。
　　 因此如果密鑰的猜測值使得對應的多重集產生了上述的2232個值中的一個值，那么這個密鑰的