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

付立仕 金晨辉



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

付立仕*金晨辉

(解放军信息工程大学 郑州 450001)

该文首次对13轮MIBS-80算法进行了不可能差分分析。首先基于MIBS-80中S盒的不可能差分筛选明文对，其次通过第1轮轮密钥与第2轮轮密钥、第1轮轮密钥与第13轮轮密钥之间的制约关系进一步筛选明文对。该文的攻击排除掉的明文对数量是已有的不可能差分攻击排除掉的明文对数量的倍，因而同时降低了攻击的存储复杂度和时间复杂度。此外，该文多次利用查表的方法求出攻击中涉及的密钥，进一步降低了攻击所需的时间复杂度和存储复杂度。最后，该文利用独立的80 bit轮密钥来恢复主密钥，确保得到正确密钥。该文的攻击需要个选择明文，次13轮加密，存储量为个64 bit，该结果优于已有的不可能差分攻击。

轻量级分组密码；MIBS-80算法；不可能差分分析；密钥制约关系

1 引言

近年来，随着微型计算设备如RFID、无线传感等技术的广泛应用，轻量级分组密码成为了密码学的一个研究热点。许多轻量级分组密码算法也被研制出来，如PRESENT, LED, KLEIN, LBlock和MIBS等。2009年，文献[1]在CANS会议上首次提出了MIBS算法，MIBS占用资源少，适合应用于计算能力受限的微型计算设备上。自MIBS算法被提出以来，其安全性受到广泛重视，目前已有基于不可能差分分析[2,3]、差分分析[2,4]、线性分析[2]、积分攻击[5]、多维线性攻击[6]、中间相遇攻击[7]、多维零相关线性分析[8]、相关密钥不可能差分分析[9]的分析结果。

不可能差分攻击是于1999年在文献[10]和文献[11]中分别提出来的。它的攻击原理是利用差分转移概率为0的差分对应排除错误的密钥，进而恢复出正确的密钥。若密钥使得密钥中存在不可能差分对应，则该密钥为错误的密钥。2010年，文献[12]基于快速排序给出了明文对的筛选方法，降低了筛选明文对所占的时间复杂度。在2014年的亚密会上，文献[13]提出了状态检测技术来进一步降低不可能差分攻击过程中所要猜测的密钥数，进而降低了不可能攻击的时间复杂度。目前，不可能差分攻击已是攻击密码算法的有效方法之一，其中不可能差分攻击对AES[14,15], FOX[16,17], ARIA[18], Camellia, 3D[22]已取得了显著效果。

本文主要研究不可能差分分析对MIBS算法的攻击效果。2010年CANS会议上文献[2]首次给出了MIBS算法中存在的8轮不可能差分对应，并对MIBS-80进行了12轮的不可能差分攻击。2012年，文献[3]指出了文献中[2]不可能差分分析的错误，并进一步改进了对12轮MIBS-80算法的不可能差分攻击。2014年，文献[6]修正了文献[2]中不可能差分的攻击结果，但并没有给出具体的攻击算法。需要指出的是，文献[3]利用连续的80 bit轮子密钥进而恢复出主密钥，但连续的80 bit轮密钥之间有至少13 bit的冗余信息，因此在文献[3]给出的时间复杂度之内并不能得出正确密钥。本文利用独立的80 bit子密钥恢复出主密钥，确保能够得到正确的密钥。

为了降低时间复杂度和存储复杂度，本文在对13轮MIBS-80算法进行攻击时尽可能早和尽可能多地排除明文对，并结合查表方法穷举尽可能少的密钥。首先，基于MIBS算法中S盒的不可能差分对应，本文比文献[2,3]中的不可能差分攻击多过滤倍的明文对，降低了明文对的数量。在攻击过程中，基于第1轮密钥与第2轮密钥，第13轮密钥和第1轮密钥之间的密钥制约关系，本文进一步对明文对进行过滤。通过以上过滤，本文过滤掉的明文对数量是文献[2,3]中过滤掉的明文对数量的倍，因而降低了攻击所需要的时间复杂度和存储复杂度。本文多次利用查表技术给出攻击过程中所涉及的密钥，进一步降低了攻击的时间复杂度和存储复杂度。此外，为了降低存储复杂度，本文在具体攻击时，依次对每个明文结构中的明文对进行过滤，故只需存储当前结构中保留的明文对，而在对下一个结构进行攻击时，释放上一个结构所占用的存储空间，由此降低了存储复杂度。本文还给出了MIBS-80算法第1, 2, 12, 13轮的轮密钥与主密钥之间的关系，在攻击过程中利用密钥之间的制约关系进一步降低了攻击的时间复杂度。基于此本文首次提出了对13轮MIBS-80的不可能差分攻击，该文的结果优于文献[2,3]中对MIBS-80的不可能差分攻击。

2 MIBS算法简介

MIBS算法是嵌套SP网络的Feistel结构的分组密码算法，其消息分组长度为64 bit，加密轮数为32轮。MIBS算法的密钥规模有64 bit和80 bit两种，分别记为MIBS-64和MIBS-80，本文针对MIBS-80进行了13轮的不可能差分攻击。

由于本文分析的是MIBS-80算法，因此本文只介绍MIBS-80的密钥生成算法，MIBS-64算法的密钥生成算法详见文献[1], MIBS-80的密钥生成算法如下所示。

3 约减至13轮的不可能差分攻击

3.1 预备知识

证明 性质(1)在在文献[14]中已有证明。下面我们来证明性质(2)。令

故性质2得证。

引理3[2]在MIBS-80算法中，相邻两轮的轮密钥之间具有线性关系，即

引理4可由MIBS-80算法的密钥扩展算法直接得到，在此不再证明。在已知时，可直接通过S盒的逆运算求出共53 bit密钥。

推论 MIBS-80算法中第13轮密钥与第1轮密钥之间有如下关系：

3.2 对13轮MIBS-80的不可能差分攻击

在对MIBS-80算法的不可能差分攻击中，本文主要利用文献[2]给出的8轮不可能差分，并在该8轮不可能差分的基础上向前扩展3轮，向后扩展2轮，由此攻击了13轮MIBS-80算法(如图1)。由文献[2]知，若输入差分对应为，输出差分对应为，当时，差分对应的转移概率为零。

本节我们首先给出对13轮MIBS-80进行不可能差分的攻击流程图，如图2所示。接下来给出具体攻击过程如下：

步骤1 选择由满足下面形式的明文组成的结构：

步骤2 对每个结构中的明文对，选择密文差分满足如下形式的明文对：即

由MIBS算法扩散层可知：

则有

图1 13轮MIBS-80的不可能差分攻击

图2 13轮MIBS-80的不可能差分攻击流程图

3.3 攻击复杂度分析

该攻击的算法复杂度主要集中在步骤2~步骤8之中，下面分析每个步骤的时间复杂度。

步骤2的时间复杂度主要为两次筛选明文对所占用的时间复杂度，第1次筛选所占的时间为次比较运算，所占用的空间为bit。

4 结束语

本文对MIBS-80算法进行了攻击，首次提出了对其13轮的不可能差分攻击，得到了目前不可能差分攻击对MIBS-80算法最好的分析结果。本文在攻击过程中利用S盒的不可能差分对应和轮密钥之间的制约关系尽早地排除错误的明文对，省掉了错误明文对所占用的时间复杂度和存储复杂度。同时，本文多次利用查表技术给出在攻击中所需要猜测的密钥，进一步降低了攻击所需的时间复杂度。此外，我们在攻击中对2个结构依次执行第2~4步骤，因

表1 MIBS-80攻击结果比较

备注：“—”指参考文献中没有给出相应的存储复杂度

此只需存储当前结构中通过过滤的明文对，在第4步骤结束后释放当前结构占用的存储空间，继而对下个结构执行第2~4步骤，由此将存储空间降低了倍。本文的攻击充分利用MIBS-80算法扩散层的性质和各轮的轮密钥之间的制约关系，如何将这些性质和制约关系用到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]. 山东大学学报(理学版), 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]. 山东大学学报(理学版), 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]. 小型微型计算机系统, 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] 刘超, 廖福成, 卫宏儒. 对MIBS算法的中间相遇攻击[J]. 内蒙古大学学报(自然科学版), 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] 栗许, 关杰. 对轻量级密码算法MIBS的零相关线性分析[J]. 信息工程大学学报, 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] 陈平, 廖福成, 卫宏儒. 对轻量级密码算法MIBS的相关密钥不可能差分攻击[J]. 通信学报, 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]. 密码学报, 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]. 电子与信息学报, 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年生，教授，博士生导师，主要研究方向为密码学.

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；网络出版：2016-01-14

付立仕 15036018167@163.com

国家自然科学基金(61272488, 61402523)