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

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

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

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

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

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

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

7、S的分析方法都對ARIA有效。反之，對ARIA有效的分析方法也很有可能用來分析和攻擊AES。對ARIA安全性的分析也變得非常重要。
　　 算法的設(shè)計(jì)者Daesung Kwon等人首先給出了ARIA的分析[40]。其中包括差分和線性分析，截?cái)嗖罘址治?，不可能差分分析，積分攻擊，高階差分分析，插值攻擊等。后來于2004年，Alex Biryukov等人對版本0.8進(jìn)行了安全性評估[11]。他們主要進(jìn)行了截?cái)嗖罘址治龊蛯Ｓ镁€性分析。2

8、007年吳文玲等人提出了對版本0.9的6輪不可能差分分析[61]。2008年李申華對吳文玲的6輪不可能差分分析進(jìn)行了改進(jìn)[44]。2009年李艷俊提出了最多攻擊到7輪ARIA-256的積分攻擊[45]。唐學(xué)海[60]等人在2010年提出最多攻擊到8輪ARIA-256的中間相遇攻擊。
　　 本文中，對現(xiàn)行的1.0版本的ARIA算法進(jìn)行了安全性分析，主要使用了不可能差分分析及中間相遇攻擊的分析方法，并有如下結(jié)果：
　　 (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非零。
　　 基于此，吳文玲等人提出了第一個(gè)約減至6輪的ARIA不可能差分分析。
　　 李申華又于2008年對ARIA的不可能差分分析進(jìn)行了改進(jìn)，發(fā)現(xiàn)了新的不可能差分特征。利用這類特征

10、對六輪ARIA進(jìn)行攻擊時(shí)，相對于吳文玲的不可能差分分析，可以分別減少猜測第1輪和第7輪輪密鑰的1字節(jié)，從而使需猜測的密鑰數(shù)由12字節(jié)減少到10字節(jié)，有效降低了不可能差分攻擊的時(shí)間復(fù)雜度。
　　 這個(gè)四輪不可能差分特征可以描述為：(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個(gè)選擇明文和296次六輪加密運(yùn)算，時(shí)間復(fù)雜度比吳文玲的攻擊降低了216。
　　 在此基礎(chǔ)上，對ARIA的不可能差分性質(zhì)展開了進(jìn)一步的研究。發(fā)現(xiàn)想進(jìn)一步減少猜測密鑰的字節(jié)數(shù)幾乎是不可能的了。因此從其他方面入手。發(fā)現(xiàn)了擴(kuò)散層的一種重要性質(zhì)，然后結(jié)合我們構(gòu)造的新的4輪不可能差分特征，給出了7輪ARIA-256的不可能差分分析。
　　 擴(kuò)散層性質(zhì)。由擴(kuò)散層(DL)的線性表達(dá)式，及擴(kuò)散層變換的自逆特性，發(fā)現(xiàn)了第一輪中進(jìn)行擴(kuò)散變換

12、前狀態(tài)的各字節(jié)之間的4個(gè)關(guān)系式，利用這4個(gè)關(guān)系式，可以有效過濾攻擊過程中無用的明文對，從而大大降低了時(shí)間復(fù)雜度，使得對ARIA的不可能差分分析能夠攻擊到7輪。
　　 這4個(gè)等式如下：△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通過使?fàn)顟B(tài)△X1(S L)的各字節(jié)滿足上述4個(gè)等式，能在進(jìn)行擴(kuò)散變換前以2-48的概率過濾明文對。
　　 也構(gòu)造出了對應(yīng)此4等式的4輪不可能差分特征，形式如下：
　　 4輪不可能差分特征。給定一對只在第3字節(jié)有差分且其他字節(jié)無差分的明文(X3，X'3)，經(jīng)過4輪加密運(yùn)算后，密文對差分△X7不可能產(chǎn)生如下形式：(j，0，j，0，0，0，0，0，j，0，0

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

15、5選擇明文和大約22387輪加密。
　　 (2)改進(jìn)的7輪ARIA-256不可能差分分析在上述7輪不可能差分分析結(jié)果基礎(chǔ)上，我們經(jīng)進(jìn)一步的研究，又發(fā)現(xiàn)了擴(kuò)散層與上述性質(zhì)類似的性質(zhì)，不同的是，這次我們得到7個(gè)等式，并由此降低了上述7輪攻擊的數(shù)據(jù)和時(shí)間復(fù)雜度。
　　 這7個(gè)等式為：△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我們也構(gòu)造了適用于此7個(gè)等式的4輪不可能差分特征，并在特征前加2輪，后邊加1輪，構(gòu)成新的7輪不可能差分路線。
　　 差分特征為：4輪不可能差分特征。

17、給定一對在第(10，15)字節(jié)有差分且其他字節(jié)無差分的明文(X3，X'3)，經(jīng)過4輪加密運(yùn)算后，密文對差分△X7不可能產(chǎn)生如下形式：(0，j，0，j，0，0，0，0，0，j，j，0，0，0，0，0)，即密文對只在(1，3，9，10)4字節(jié)處有非零差分，在其他字節(jié)無差分。這一不可能差分性質(zhì)可用下式表示：
　　 (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算法的中間相遇攻擊最早由唐學(xué)海[60]等人提出，他們最多攻擊到8輪ARIA-256。8輪攻擊的數(shù)據(jù)復(fù)雜度為256，時(shí)間復(fù)雜度為2251.6，預(yù)計(jì)算復(fù)雜度為2252。而7輪ARIA-192攻擊需要2120個(gè)明文，2185.3次7輪ARIA-192加密運(yùn)算，和2187次預(yù)計(jì)算。6輪攻擊的數(shù)據(jù)/時(shí)間/預(yù)計(jì)

19、算復(fù)雜度分別為256，2121.5，及2122.5。5輪攻擊需要25個(gè)明文，時(shí)間復(fù)雜度為265.4，預(yù)計(jì)算復(fù)雜度為2122.5。
　　 在此基礎(chǔ)上，結(jié)合2010年由Orr Dunkelman，Nathan Keller，and AdiShamir[24]等人提出的針對AES的中間相遇攻擊，提出了新的ARIA中間相遇攻擊的4輪區(qū)分器，并以此為基礎(chǔ)提出了新的最多攻擊到8輪的中間相遇攻擊，改進(jìn)了唐學(xué)海等人的結(jié)果。
　　 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個(gè)可能值。
　　 因此如果密鑰的猜測值使得對應(yīng)的多重集產(chǎn)生了上述的2232個(gè)值中的一個(gè)值，那么這個(gè)密鑰的