11輪3D密碼的不可能差分攻擊

謝作敏 陳少真 魯林真

?

11輪3D密碼的不可能差分攻擊

謝作敏*陳少真 魯林真

(解放軍信息工程大學(xué) 鄭州 450001) (數(shù)學(xué)工程與先進(jìn)計算國家重點實驗室 鄭州 450001)

分組密碼；不可能差分攻擊；3D密碼；預(yù)計算技術(shù)

1 引言

2008年，文獻(xiàn)[1]提出3D密碼算法。其設(shè)計原理來源于美國高級加密標(biāo)準(zhǔn)AES，它的分組長度與密鑰長度都為512 bit，一共有22輪，AES采用的是2維的4×4的字節(jié)矩陣，而3D密碼算法采用了3維4×4×4的字節(jié)矩陣。由于3D密碼新的設(shè)計理念，加上現(xiàn)代科學(xué)技術(shù)的發(fā)展以及計算能力的不斷刷新，分組密碼的趨勢必然是朝向更長的分組以及密鑰長度發(fā)展，出于其安全性以及潛在應(yīng)用考慮，該密碼算法備受關(guān)注。

不可能差分攻擊最先由文獻(xiàn)[2,3]提出，用來分析DEAL與Skipjack算法。目前，不可能差分攻擊被廣泛地應(yīng)用到了各種結(jié)構(gòu)的分組密碼攻擊中，在AES[4], CLEFIA[5], MISTY1[6], Camellia[7]等密碼上有非常好的攻擊效果。近年來，不可能差分攻擊也有了一些新的擴展與發(fā)展，文獻(xiàn)[8]利用相關(guān)密鑰不可能差分攻擊方法攻擊了8輪的AES-192, 2010年，文獻(xiàn)[9]提出了不可能的概率差分攻擊方法得到CLEFIA的最優(yōu)攻擊結(jié)果。

對3D密碼的安全性分析最先由設(shè)計者Nakahara[1]提出。2010年文獻(xiàn)[10]提出了最大可以擴展到9輪的3D密碼的Square攻擊。接著文獻(xiàn)[11]提出了9輪不可能差分攻擊。文獻(xiàn)[12]在2011年提出了10輪不可能差分攻擊。2012年，文獻(xiàn)[13]提出了10輪3D密碼的中間相遇攻擊，與此同時文獻(xiàn)[14]提出利用截斷差分攻擊首次實現(xiàn)了存在概率的對11輪3D密碼的攻擊。在今后的若干年，3D密碼的研究仍然將是一個熱點。

本文在不可能差分路徑的選取以及密鑰恢復(fù)過程中的數(shù)據(jù)處理做了若干提升：為了使不可能差分?jǐn)U展到更多的輪數(shù)，在6輪不可能差分區(qū)分器的構(gòu)造過程中，發(fā)現(xiàn)了一類較優(yōu)的差分路徑；在排除錯誤猜測密鑰的過程中，利用預(yù)計算技術(shù)，將重復(fù)的加解密運算通過查表完成，大大減少了時間復(fù)雜度；初始化一部分猜測密鑰，結(jié)合盒的可逆性質(zhì)，建立部分輪子密鑰與選擇明文對的Hash表，使得在最后錯誤密鑰排除過程中不用存儲所有的猜測密鑰，降低攻擊所需的存儲；為了恢復(fù)出主密鑰，預(yù)留一部分沒有排除掉的錯誤輪子密鑰，再窮舉另外一部分輪子密鑰，以達(dá)到部分減少時間復(fù)雜度的目的。

本文的結(jié)構(gòu)安排如下：第2節(jié)簡要介紹3D密碼的加密算法以及一些性質(zhì)；第3節(jié)描述3D密碼的一類新的6輪不可能差分區(qū)分器；第4節(jié)介紹3D密碼的11輪不可能差分攻擊；第5節(jié)給出了3D密碼的10不可能差分攻擊；第6節(jié)是結(jié)束語。

2 3D密碼算法介紹

表1 3D密碼S盒差分分布表

3 3D密碼算法的6輪不可能差分區(qū)分器

為了使攻擊達(dá)到更高的輪數(shù)，在不可能差分區(qū)分器首尾字節(jié)的選取上進(jìn)行了優(yōu)化篩選。如圖1所示，此不可能差分區(qū)分器由兩段構(gòu)成，前3輪差分以及后3輪分別以概率1成立，而它們在中間相遇產(chǎn)生矛盾(由圖1矛盾顯然，具體證明略)，從而構(gòu)成6輪不可能差分區(qū)分器。圖1中“*”表示活動的非零字節(jié)差分值，“?”表示未知的差分值。第6輪中的輪密鑰加與下一輪的列混合進(jìn)行了交換。

性質(zhì)3(一類6輪不可能差分區(qū)分器) 對3D密碼的第偶數(shù)輪輸入，如果滿足4個子塊中的任意一個子塊中的其中兩列中的3行為活動差分字節(jié)，而其它的58個字節(jié)差分值為零，經(jīng)過6輪加密后，不可能出現(xiàn)輸出狀態(tài)有1個字節(jié)差分非零，而其它的字節(jié)差分值為零的情況。

圖1 6輪不可能差分區(qū)分器

圖2 一類6輪不可能差分區(qū)分器

4 對11輪3D密碼的不可能差分攻擊

4.1 預(yù)計算過程

本小節(jié)，建立5類Hash表用來分別提取密鑰，將密鑰恢復(fù)過程中的加解密過程通過查表完成，可以很好降低時間復(fù)雜度。

4.2 11輪3D密碼的密鑰恢復(fù)攻擊過程

4.3 對11輪3D密碼攻擊的復(fù)雜度分析

5 對10輪3D密碼的不可能差分攻擊

本節(jié)在圖3的11輪不可能差分路徑的基礎(chǔ)上，開展對3D密碼的10輪不可能差分攻擊?？紤]到加解密結(jié)構(gòu)的相似性，本節(jié)將逆向圖3的11輪不可能差分路徑，即圖3中的第11輪為本攻擊的第1輪，圖3中的第2輪為本攻擊的第10輪(最后一輪)。根據(jù)加解密相似性，對于圖1構(gòu)造的6輪不可能差分，倒過來，也是顯然成立的。具體攻擊路徑如圖4所示。

圖3 3D密碼的11輪不可能差分攻擊路徑

6 結(jié)束語

本文實現(xiàn)了對10輪與11輪的3D密碼不可能差分攻擊。表2列出了本文的攻擊結(jié)果并比較了以往相關(guān)文獻(xiàn)的數(shù)據(jù)。

圖4 3D密碼的10輪不可能差分攻擊路徑

表2本文與部分3D密碼攻擊結(jié)果比較

輪數(shù)選擇明文量時間復(fù)雜度存儲(分組長度)攻擊方法文獻(xiàn) 7-IA[10] 7ID[11] 8-IA[10] 8ID[11] 9-IA[10] 9ID[11] 10ID[12] 102444.472318.82184.4ID本文 10MitM[13] 112493.032511.22388ID本文

ID：不可能差分攻擊，MitM：中間相遇攻擊，IA：積分攻擊

本文較以往的對3D密碼的攻擊過程，在不可能差分區(qū)分器的首位字節(jié)位置選擇上做了優(yōu)化與篩選，同時利用預(yù)計算計算，利用S盒的輸入輸出差分計算出滿足條件的輸入輸出對，通過查表分別計算猜測密鑰的候選值，很大程度地減少了計算量，最終得以實現(xiàn)了3D密碼的11輪攻擊，足以說明用存儲換取復(fù)雜度的思想是可行且有效的。而這種方法對于分組密碼以及Hash算法的各種攻擊，都提供了很好的優(yōu)化思路。

[1] Nakahara J Jr. 3D: A three-dimensional block cipher[J]., 2008, 5339: 252-267.

[2] Knudsen L. DEAL-a 128-bit block cipher[J]., 1998, 258: 2-11.

[3] Biham E, Biryukov A, and Shamir A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials [J]., 1999, 1592: 12-23.

[4] Liu Ya, Gu Dawu, Liu Zhi-qiang,.. New improved impossible differential attack on reduced-round AES-128[C]. Computer Science and Convergence , Springer-Verlag, Jeju, Korea, 2012, Vol. 114: 453-461.

[5] Mala H, Dakhilalian M, and Shakiba M. Impossible differential attacks on 13-round CLEFIA-128[J]., 2011, 26(4): 744-750.

[6] Jia K, Li L, Rechberger C,.. Impossible differential attacks on reduced-round MISTY1[J]., 2013, 7707: 222-233.

[7] Liu Y, Li L, Gu D,.. New observations on impossible differential cryptanalysis of reduced-round Camellia[J]., 2012, 7549: 90-109.

[8] Biham E and Dunkelman O. Related-key impossible differential attacks on 8-round AES-192[J]., 2006, 3860: 21-33.

[9] Cihangir Tezcan. The improbable differential attack: cryptanalysis of reduced-round CLEFIA[J]., 2010, 6498: 197-209.

[10] 王美一, 唐學(xué)海, 李超, 等. 3D密碼的Square攻擊[J]. 電子與信息學(xué)報, 2010, 32(1): 157-161.

Wang M Y, Tang X H, Li C,.. Square attacks on 3D cipher[J].&, 2010, 32(1): 157-161.

[11] 唐學(xué)海, 李超, 王美一, 等. 3D密碼的不可能差分攻擊[J]. 電子與信息學(xué)報, 2010, 32(10): 2516-2520.

Tang X H, Li C, Wang M Y,.. Impossible differential attack on 3D cipher[J].&, 2010, 32(10): 2516-2520.

[12] Nakahara J Jr. New impossible differential and known-key distinguishers for the 3D cipher[J]., 2011, 6672: 208-221.

[13] 蘇崇茂, 韋永壯, 馬春波. 10輪3D分組密碼算法的中間相遇攻擊[J]. 電子與信息學(xué)報, 2012, 34(3): 694-697.

Su Chong-mao, Wei Yong-zhuang, and Ma Chun-bo. Meet- in-the-middle attack on 10-round reduced 3D block Cipher[J].&, 2012, 34(3): 694-697.

[14] Takuma Koyama, Lei Wang, Yu Sasaki,.. New truncated differential cryptanalysis on 3D block cipher[J]., 2012, 7232: 109-125.

謝作敏： 男，1989年生，碩士生，研究方向為密碼學(xué)與信息安全.

陳少真： 女，1967年生，博士生導(dǎo)師，研究方向為密碼學(xué)與信息安全.

魯林真： 男，1985年生，博士生，研究方向為密碼學(xué)與信息安全.

Impossible Differential Cryptanalysis of 11-Round 3D Cipher

Xie Zuo-min Chen Shao-zhen Lu Lin-zhen

(,450001,) (,450001,)

Block cipher; Impossible differential attack; 3D cipher; Precomputation

TN918.1

A

1009-5896(2014)05-1215-06

10.3724/SP.J.1146.2013.00948

謝作敏 xiezuomin@126.com

2013-07-01收到，2013-12-16改回

信息保障技術(shù)重點實驗室開放基金(KJ-13-010)資助課題