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

謝作敏 陳少真 魯林真

?

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

謝作敏*陳少真 魯林真

(解放軍信息工程大學 鄭州 450001) (數學工程與先進計算國家重點實驗室 鄭州 450001)

分組密碼；不可能差分攻擊；3D密碼；預計算技術

1 引言

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

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

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

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

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

2 3D密碼算法介紹

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

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

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

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

圖1 6輪不可能差分區分器

圖2 一類6輪不可能差分區分器

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

4.1 預計算過程

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

4.2 11輪3D密碼的密鑰恢復攻擊過程

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

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

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

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

6 結束語

本文實現了對10輪與11輪的3D密碼不可能差分攻擊。表2列出了本文的攻擊結果并比較了以往相關文獻的數據。

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

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

輪數選擇明文量時間復雜度存儲(分組長度)攻擊方法文獻 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密碼的攻擊過程，在不可能差分區分器的首位字節位置選擇上做了優化與篩選，同時利用預計算計算，利用S盒的輸入輸出差分計算出滿足條件的輸入輸出對，通過查表分別計算猜測密鑰的候選值，很大程度地減少了計算量，最終得以實現了3D密碼的11輪攻擊，足以說明用存儲換取復雜度的思想是可行且有效的。而這種方法對于分組密碼以及Hash算法的各種攻擊，都提供了很好的優化思路。

[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] 王美一, 唐學海, 李超, 等. 3D密碼的Square攻擊[J]. 電子與信息學報, 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] 唐學海, 李超, 王美一, 等. 3D密碼的不可能差分攻擊[J]. 電子與信息學報, 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]. 電子與信息學報, 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年生，碩士生，研究方向為密碼學與信息安全.

陳少真： 女，1967年生，博士生導師，研究方向為密碼學與信息安全.

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

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改回

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