付立仕 金晨輝

?

MIBS-80的13輪不可能差分分析

付立仕*金晨輝

(解放軍信息工程大學(xué) 鄭州 450001)

該文首次對13輪MIBS-80算法進行了不可能差分分析。首先基于MIBS-80中S盒的不可能差分篩選明文對，其次通過第1輪輪密鑰與第2輪輪密鑰、第1輪輪密鑰與第13輪輪密鑰之間的制約關(guān)系進一步篩選明文對。該文的攻擊排除掉的明文對數(shù)量是已有的不可能差分攻擊排除掉的明文對數(shù)量的倍，因而同時降低了攻擊的存儲復(fù)雜度和時間復(fù)雜度。此外，該文多次利用查表的方法求出攻擊中涉及的密鑰，進一步降低了攻擊所需的時間復(fù)雜度和存儲復(fù)雜度。最后，該文利用獨立的80 bit輪密鑰來恢復(fù)主密鑰，確保得到正確密鑰。該文的攻擊需要個選擇明文，次13輪加密，存儲量為個64 bit，該結(jié)果優(yōu)于已有的不可能差分攻擊。

輕量級分組密碼；MIBS-80算法；不可能差分分析；密鑰制約關(guān)系

1 引言

近年來，隨著微型計算設(shè)備如RFID、無線傳感等技術(shù)的廣泛應(yīng)用，輕量級分組密碼成為了密碼學(xué)的一個研究熱點。許多輕量級分組密碼算法也被研制出來，如PRESENT, LED, KLEIN, LBlock和MIBS等。2009年，文獻[1]在CANS會議上首次提出了MIBS算法，MIBS占用資源少，適合應(yīng)用于計算能力受限的微型計算設(shè)備上。自MIBS算法被提出以來，其安全性受到廣泛重視，目前已有基于不可能差分分析[2,3]、差分分析[2,4]、線性分析[2]、積分攻擊[5]、多維線性攻擊[6]、中間相遇攻擊[7]、多維零相關(guān)線性分析[8]、相關(guān)密鑰不可能差分分析[9]的分析結(jié)果。

不可能差分攻擊是于1999年在文獻[10]和文獻[11]中分別提出來的。它的攻擊原理是利用差分轉(zhuǎn)移概率為0的差分對應(yīng)排除錯誤的密鑰，進而恢復(fù)出正確的密鑰。若密鑰使得密鑰中存在不可能差分對應(yīng)，則該密鑰為錯誤的密鑰。2010年，文獻[12]基于快速排序給出了明文對的篩選方法，降低了篩選明文對所占的時間復(fù)雜度。在2014年的亞密會上，文獻[13]提出了狀態(tài)檢測技術(shù)來進一步降低不可能差分攻擊過程中所要猜測的密鑰數(shù)，進而降低了不可能攻擊的時間復(fù)雜度。目前，不可能差分攻擊已是攻擊密碼算法的有效方法之一，其中不可能差分攻擊對AES[14,15], FOX[16,17], ARIA[18], Camellia, 3D[22]已取得了顯著效果。

本文主要研究不可能差分分析對MIBS算法的攻擊效果。2010年CANS會議上文獻[2]首次給出了MIBS算法中存在的8輪不可能差分對應(yīng)，并對MIBS-80進行了12輪的不可能差分攻擊。2012年，文獻[3]指出了文獻中[2]不可能差分分析的錯誤，并進一步改進了對12輪MIBS-80算法的不可能差分攻擊。2014年，文獻[6]修正了文獻[2]中不可能差分的攻擊結(jié)果，但并沒有給出具體的攻擊算法。需要指出的是，文獻[3]利用連續(xù)的80 bit輪子密鑰進而恢復(fù)出主密鑰，但連續(xù)的80 bit輪密鑰之間有至少13 bit的冗余信息，因此在文獻[3]給出的時間復(fù)雜度之內(nèi)并不能得出正確密鑰。本文利用獨立的80 bit子密鑰恢復(fù)出主密鑰，確保能夠得到正確的密鑰。

為了降低時間復(fù)雜度和存儲復(fù)雜度，本文在對13輪MIBS-80算法進行攻擊時盡可能早和盡可能多地排除明文對，并結(jié)合查表方法窮舉盡可能少的密鑰。首先，基于MIBS算法中S盒的不可能差分對應(yīng)，本文比文獻[2,3]中的不可能差分攻擊多過濾倍的明文對，降低了明文對的數(shù)量。在攻擊過程中，基于第1輪密鑰與第2輪密鑰，第13輪密鑰和第1輪密鑰之間的密鑰制約關(guān)系，本文進一步對明文對進行過濾。通過以上過濾，本文過濾掉的明文對數(shù)量是文獻[2,3]中過濾掉的明文對數(shù)量的倍，因而降低了攻擊所需要的時間復(fù)雜度和存儲復(fù)雜度。本文多次利用查表技術(shù)給出攻擊過程中所涉及的密鑰，進一步降低了攻擊的時間復(fù)雜度和存儲復(fù)雜度。此外，為了降低存儲復(fù)雜度，本文在具體攻擊時，依次對每個明文結(jié)構(gòu)中的明文對進行過濾，故只需存儲當前結(jié)構(gòu)中保留的明文對，而在對下一個結(jié)構(gòu)進行攻擊時，釋放上一個結(jié)構(gòu)所占用的存儲空間，由此降低了存儲復(fù)雜度。本文還給出了MIBS-80算法第1, 2, 12, 13輪的輪密鑰與主密鑰之間的關(guān)系，在攻擊過程中利用密鑰之間的制約關(guān)系進一步降低了攻擊的時間復(fù)雜度?；诖吮疚氖状翁岢隽藢?3輪MIBS-80的不可能差分攻擊，該文的結(jié)果優(yōu)于文獻[2,3]中對MIBS-80的不可能差分攻擊。

2 MIBS算法簡介

MIBS算法是嵌套SP網(wǎng)絡(luò)的Feistel結(jié)構(gòu)的分組密碼算法，其消息分組長度為64 bit，加密輪數(shù)為32輪。MIBS算法的密鑰規(guī)模有64 bit和80 bit兩種，分別記為MIBS-64和MIBS-80，本文針對MIBS-80進行了13輪的不可能差分攻擊。

由于本文分析的是MIBS-80算法，因此本文只介紹MIBS-80的密鑰生成算法，MIBS-64算法的密鑰生成算法詳見文獻[1], MIBS-80的密鑰生成算法如下所示。

3 約減至13輪的不可能差分攻擊

3.1 預(yù)備知識

證明 性質(zhì)(1)在在文獻[14]中已有證明。下面我們來證明性質(zhì)(2)。令

故性質(zhì)2得證。

引理3[2]在MIBS-80算法中，相鄰兩輪的輪密鑰之間具有線性關(guān)系，即

引理4可由MIBS-80算法的密鑰擴展算法直接得到，在此不再證明。在已知時，可直接通過S盒的逆運算求出共53 bit密鑰。

推論 MIBS-80算法中第13輪密鑰與第1輪密鑰之間有如下關(guān)系：

3.2 對13輪MIBS-80的不可能差分攻擊

在對MIBS-80算法的不可能差分攻擊中，本文主要利用文獻[2]給出的8輪不可能差分，并在該8輪不可能差分的基礎(chǔ)上向前擴展3輪，向后擴展2輪，由此攻擊了13輪MIBS-80算法(如圖1)。由文獻[2]知，若輸入差分對應(yīng)為，輸出差分對應(yīng)為，當時，差分對應(yīng)的轉(zhuǎn)移概率為零。

本節(jié)我們首先給出對13輪MIBS-80進行不可能差分的攻擊流程圖，如圖2所示。接下來給出具體攻擊過程如下：

步驟1 選擇由滿足下面形式的明文組成的結(jié)構(gòu)：

步驟2 對每個結(jié)構(gòu)中的明文對，選擇密文差分滿足如下形式的明文對：即

由MIBS算法擴散層可知：

則有

圖1 13輪MIBS-80的不可能差分攻擊

圖2 13輪MIBS-80的不可能差分攻擊流程圖

3.3 攻擊復(fù)雜度分析

該攻擊的算法復(fù)雜度主要集中在步驟2~步驟8之中，下面分析每個步驟的時間復(fù)雜度。

步驟2的時間復(fù)雜度主要為兩次篩選明文對所占用的時間復(fù)雜度，第1次篩選所占的時間為次比較運算，所占用的空間為bit。

4 結(jié)束語

本文對MIBS-80算法進行了攻擊，首次提出了對其13輪的不可能差分攻擊，得到了目前不可能差分攻擊對MIBS-80算法最好的分析結(jié)果。本文在攻擊過程中利用S盒的不可能差分對應(yīng)和輪密鑰之間的制約關(guān)系盡早地排除錯誤的明文對，省掉了錯誤明文對所占用的時間復(fù)雜度和存儲復(fù)雜度。同時，本文多次利用查表技術(shù)給出在攻擊中所需要猜測的密鑰，進一步降低了攻擊所需的時間復(fù)雜度。此外，我們在攻擊中對2個結(jié)構(gòu)依次執(zhí)行第2~4步驟，因

表1 MIBS-80攻擊結(jié)果比較

備注：“—”指參考文獻中沒有給出相應(yīng)的存儲復(fù)雜度

此只需存儲當前結(jié)構(gòu)中通過過濾的明文對，在第4步驟結(jié)束后釋放當前結(jié)構(gòu)占用的存儲空間，繼而對下個結(jié)構(gòu)執(zhí)行第2~4步驟，由此將存儲空間降低了倍。本文的攻擊充分利用MIBS-80算法擴散層的性質(zhì)和各輪的輪密鑰之間的制約關(guān)系，如何將這些性質(zhì)和制約關(guān)系用到MIBS-80的其它攻擊方法上還有待進一步研究。

[1] IZADI M, SADEGHIYAN B, and SADEGHIAN S. MIBS: a new light-weight block cipher[C]. CANS 2009, Ishikawa, Japan, 2009: 334-348. doi: 10.1007/978-3-642-10433-6_22.

[2] BAY A, NAKAHARA J, and VAUDENAY S. Cryptanalysis of reduced-round MIBS block cipher[C]. CANS 2010, Malaysia, 2010: 1-19. doi: 10.1007/978-3-642-17619-7_1.

[3] 杜承航, 陳佳哲. 輕量級分組密碼算法MIBS不可能差分分析[J]. 山東大學(xué)學(xué)報(理學(xué)版), 2012, 47(7): 55-58.

DU Chenghang and CHEN Jiazhe. Impossible differential cryptanalysis of reduced-round MIBS[J].(), 2012, 47(7): 55-58

[4] 楊林, 王美琴. 約簡輪的MIBS算法的差分分析[J]. 山東大學(xué)學(xué)報(理學(xué)版), 2010, 45(4): 12-15.

YANG Lin and WANG Meiqin. Differential cryptanalysis of reduced-round MIBS[J].(), 2010, 45(4): 12-15.

[5] 王高麗, 王少輝. 對MIBS算法的Integral攻擊[J]. 小型微型計算機系統(tǒng), 2012, 33(4): 773-777.

WANG Gaoli, and WANG Shaohui. Integral cryptanalysis of reduced-round MIBS block cipher[J]., 2012, 33(4): 773-777.

[6] BAY A, HUANG J, and VAUDENAY S. Improved linear cryptanalysis of reduced-round MIBS[C]. The 9th International Workshop on Security, Hirosaki, 2014: 204-220. doi: 10.1007/978-3-319-09843-2_16.

[7] 劉超, 廖福成, 衛(wèi)宏儒. 對MIBS算法的中間相遇攻擊[J]. 內(nèi)蒙古大學(xué)學(xué)報(自然科學(xué)版), 2013, 44(3): 308-315.

LIU Chao, LIAO Fucheng, and WEI Hongru. Meet-in- the-middle attacks on MIBS[J].(), 2013, 44(3): 308-315.

[8] 栗許, 關(guān)杰. 對輕量級密碼算法MIBS的零相關(guān)線性分析[J]. 信息工程大學(xué)學(xué)報, 2015, 16(1):20-24.

LI Xu and GUAN Jie. Zero correlation linear cryptanalysis of lightweight block cipher MIBS[J].,2015, 16(1):20-24.

[9] 陳平, 廖福成, 衛(wèi)宏儒. 對輕量級密碼算法MIBS的相關(guān)密鑰不可能差分攻擊[J]. 通信學(xué)報, 2014, 35(2): 190-193.

CHEN Ping, LIAO Fucheng, and Wei Hongru. Related-key impossible differential attack on a lightweight block cipher MIBS[J]., 2014, 35(2): 190-193.

[11] BIHAM E, BIRYUKOV A, and SHAMIR A. Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials[C]. Advances in CryptologEUROCRYPT'99, Prague, 1999: 2-23. doi: 10.1007/3-540-48910-X_2.

[12] 胡弘堅, 金晨輝, 李信然. 改進的 7 輪 AES-128 的不可能差分攻擊[J]. 密碼學(xué)報, 2015, 2(1): 92-100. doi: 10.13868/j. vcnki.jcr.000063.

HU Hongjian, JIN Chenhui, and LI Xinran. Improved impossible differential attack on 7-round AES-128[J]., 2015, 2(1): 92-100. doi: 10.13868 /j.vcnki.jcr.000063.

[13] LI Xinran, FU Fangwei, and GUANG Xi. Multiple impossible differential cryptanalysis on reduced FOX[J]., 2015, E98-A(3): 906-911. doi: 10.1587/transfun.E98.A.906.

[14] GUO Rui and JIN Chenhui. Impossible differential cryptanalysis on Lai-Massey scheme[J]., 2014, 36(6): 1032-1040. doi: 10.4218/etrij.14.0113.1335.

[15] WU Wenling, ZHANG Wentao, and FENG Dengguo. Impossible differential cryptanalysis of reduced-round ARIA and Camellia[J]., 2007, 22(3): 449-456. doi: 10.1007/s11390-007- 9056-0.

[16] WU Wenling, ZHANG Lei, and ZHANG Wentao. Improved impossible differential cryptanalysis of reduced-round Camellia[C]. Selected Areas in Cryptography16th Annual International Workshop, SAC 2009, Calgary,Canada, 2009: 442-456. doi: 10.1007/978-3-642-04159-4_29.

[17] MALA H, DAKHILALIAN M, RIJMEN V,. Improved impossible differential cryptanalysis of 7-round AES-128[C]. The 11th International Conference on Cryptology, Hyderabad, India, 2010: 282-291. doi: 10.1007/978-3-642- 17401-8_20.

[18] LIU Ya, GU Dawu, and LIU Zhiqiang. Improved results on impossible differential cryptanalysis of reduced-round Camellia-192/256[J]., 2012, 85(11): 2451-2458. doi: 10.1016/j.jss.2012.05.051.

[19] BAI Dongxia and LI Leibo. New impossible differential attacks on Camellia[C]. International Conference on Information Security Practice and Experience 2012, Hangzhou, 2012: 80-96. doi: 10.1007/978-3-642-29101-2_6.

[20] 張慶貴. 不可能差分攻擊中的明文對篩選方法[J]. 計算機工程, 2010, 36(2): 127-129.

ZHANG Qinggui. Plaintext pair sieve methods in impossible differential attack[J]., 2010, 36(2): 127-129.

[21] BOURA C, NAYA PLASENCIA M, and SUDER V. Scrutinizing and improving impossible differential attacks: applications to CLEFIA, Camellia, LBlock and Simon (Full Version)[C]. Advances in Cryptology20th Annual International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, 2014: 179-199. doi: 10.1007/978-3-662-45611-8_10.

[22] 謝作敏, 陳少真, 魯林真. 11輪3D密碼的不可能差分攻擊[J]. 電子與信息學(xué)報, 2014, 36(5): 1215-1220. doi: 10.3724/SP.J. 1146.2013.00948.

XIE Zuomin, CHEN Shaozhen, and LU Linzhen. Impossible differential cryptanalysis of 11-round 3D cipher[J].&, 2014, 36(5): 1215-1220. doi: 10.3724/SP.J.1146.2013.00948.

付立仕： 女，1989 年生，博士生，研究方向為分組密碼.

金晨輝： 男，1965年生，教授，博士生導(dǎo)師，主要研究方向為密碼學(xué).

Foundation Items: The National Natural Science Foundation of China (61272488, 61402523)

Impossible Differential Cryptanalysis on 13-round MIBS-80

FU Lishi JIN Chenhui

(The Information Engineering University of PLA, Zhengzhou 450001, China)

This paper presents the 13-round impossible differential cryptanalysis on MIBS-80 for the first time. Firstly, this paper filters the plaintexts based on the impossible differentia of S-box in MIBS-80. Secondly, by taking advantage of the restrict relation between key in the first round and in the second round, the restrict relation between key in the first round and in the 13thround, the number of plaintexts is further reduced. To sum up,times can be eliminated as big as the number of plaintexts eliminated in former impossible attacks, therefore both the time complexity and memory complexity are saved. Besides, by looking up various tables to get the needed key bits in the attack, the time complexity and memory complexity are thereafter reduced. Finally, 80 independent key bit are used to recover the main key, which ensures that only the right key is kept. The presented attack needschosen plaintexts,13-round encryptions and64 bit blocks, which is the best result of impossible differential attack on MIBS so far.

Lightweight block cipher; MIBS-80 algorithm; Impossible differential cryptanalysis; Restrict relation between keys

TN918.1

A

1009-5896(2016)04-0848-08

10.11999/JEIT150673

2015-06-04；改回日期：2015-11-25；網(wǎng)絡(luò)出版：2016-01-14

付立仕 15036018167@163.com

國家自然科學(xué)基金(61272488, 61402523)