轻量级密码算法MIBS的零相关和积分分析

伊文坛 鲁林真 陈少真



轻量级密码算法MIBS的零相关和积分分析

伊文坛*鲁林真 陈少真

(数学工程与先进计算国家重点实验室 郑州 450001)

MIBS是适用于RFID和传感资源受限环境的轻量级分组算法。该文构造了一些关于MIBS的8轮零相关线性逼近，结合密钥扩展算法的特点和部分和技术，对13轮MIBS-80进行了多维零相关分析。该分析大体需要262.1个已知明文和274.9次加密。此外，利用零相关线性逼近和积分区分器之间的内在联系，推导出8轮的积分区分器，并且对11轮的MIBS-80进行了积分攻击，大体需要260个选择明文和259.8次加密。

分组密码；MIBS；零相关分析；积分攻击

1 引言

MIBS[1]是在2009年提出的一个轻量级分组密码算法，具有资源占用量较少的优点，主要适用于RFID(Radio Frequency IDentification)、无线传感技术等设备资源和计算能力有限的设备和环境中。该算法整体采用Feistel结构，分组长度为64 bit，密钥长度可以为64 bit和80 bit，分别记作MIBS-64和MIBS-80，都迭代32轮。目前针对MIBS的分析有差分分析、线性分析、不可能差分分析、积分分析、中间相遇分析以及相关密钥条件下的不可能差分分析等。

文献[2]给出了13轮MIBS-64的差分分析；之后，文献[3]改进了关于14轮MIBS-64的差分分析结果，需要的时间复杂度为237.2次加密，数据复杂度为240个选择明文；文献[3]对MIBS算法的抗线性分析的能力进行了估计，结果显示对18轮MIBS-80的线性分析大体需要260.9个已知明文和276.1次加密；文献[3]给出了12轮MIBS-80的不可能差分分析。随后文献[4]指出文献[3]工作中存在错误，并重新给出了12轮MIBS-80的不可能差分分析结果；文献[5]首次利用积分分析方法分析了8轮MIBS-64和9轮MIBS-80；随后，文献[6]和文献[7]分别给出了10轮MIBS-80关于积分分析的结果；2013年，文献[8]发现了MIBS的6轮中间相遇区分器，结合密钥扩展算法的特点，给出了11轮MIBS-80的中间相遇分析结果，大体需要224.9个选择明文，266.2次加密和250次预计算；2014年，文献[9]构造了相关密钥条件下的10轮的不可能差分特征，并对14轮MIBS- 80进行了攻击，大体需要254个选择明文和256次加密。

可以看出，评估MIBS算法的安全性一直是研究的热点问题。然而，MIBS算法关于最近提出的零相关分析方法的分析结果还是空白。零相关线性分析方法由文献[10]在2012年提出。该方法是利用相关系数为零的线性逼近来区分密码算法和随机函数，从而进行密钥恢复攻击的工作。最初，零相关线性分析方法利用一条零相关线性逼近，至少需要选择一半明密文空间。多重零相关[11]利用多条零相关线性逼近，在一定程度上降低了数据量，但是要求线性逼近的输入掩码和输出掩码独立。多维零相关[12]的提出克服了线性逼近的独立性条件，所需数据量和多重零相关相当。最近，零相关线性分析方法在AES[10], TEA[11], CAST-256[12], LBlock[13], E2[14], Camellia[15]以及CLEFIA[15]等密码算法的分析中取得了很好的结果。另外，文献[12]还揭示了零相关线性逼近和积分区分器之间的关系。

本文利用零相关线性分析和积分分析方法评估MIBS-80密码算法的安全性。根据线性层的特点，构造了一些8轮MIBS密码算法的零相关线性逼近；利用多维零相关线性分析方法，结合密钥扩展算法的特点和部分和技术，对13轮的MIBS-80密码算法做安全性分析；利用零相关区分器和积分区分器之间的联系，推导出一些8轮的积分区分器；进一步，作为应用，对11轮的MIBS-80密码算法进行积分分析。

本文的结构大致安排如下：在第2节中，约定一些记号，简单介绍MIBS密码算法、零相关分析方法和积分攻击方法；在第3节中，构造了一些8轮MIBS密码算法零相关线性逼近并对13轮MIBS-80进行了多维零相关分析；在随后的小节中，推导出一个8轮的积分区分器，并且利用积分分析方法分析了MIBS-80密码算法的安全性；最后，对比了单密钥下MIBS-80密码算法的主要分析结果并总结本文的工作。

2 预备知识

2.1 一些记号

2.2 MIBS算法介绍

分组密码算法MIBS总体采用了Feistel密码结构，分组长度为64 bit，并且迭代32轮。密钥长度接受64 bit和80 bit，仅仅是在密钥扩展算法上有区别，分别记为MIBS-64和MIBS-80。轮函数采用了典型的SPN(Substitution Permutation Network)结构，包括轮子密钥加运算、S盒变换和线性层运算。所有的操作都是在4 bit的半个字节上完成的。

本文工作主要针对MIBS-80，这里只介绍MIBS-80的密钥扩展算法。MIBS-80的密钥扩展算法受到PRESENT算法[16]的密钥扩展算法的启发。设为长度为80 bit长主密钥，则由主密钥生成32个32 bit的轮密钥的过程如下：

其中，轮常数Round_counter 是所在轮序号的4 bit二进制表示。关于MIBS-64的密钥扩展算法见文献[1]。

2.3 多维零相关分析方法和积分分析介绍

多维零相关线性分析方法[12]选取个零相关线性逼近，并且这些线性逼近由的基线向量通过线性关系扩展。不妨记作为。攻击者选择对明密文对，并建立计数器，其中是bit长的向量。通过在线性逼近前后加轮，穷举部分子密钥并部分加解密所选取的明密文对，得到线性掩码首尾对应的中间状态，为了方便记作。然后, 对于选择的每一个明密文对经过部分加解密得到，计算，进而，得到向量的值。更新相应的对应的计数器。然后，计算统计量：

2.3.2 积分分析方法 积分分析是一种选择明文攻击方法，主要利用积分区分器来恢复密钥信息。积分区分器是根据轮函数的性质构造而成的。比如选择某些特定结构的明文，经过若干轮迭代之后，所有对应的输出的某些或者全部bit异或之后为零等。不妨设轮密码算法的前轮是满足上述性质的区分器，设是相应的选择明文空间，则有。

在具体攻击过程中，攻击者在区分器的一端或者两端添加若干轮，猜测涉及到的子密钥，在根据区分器的性质进行密钥筛选。不妨在后面添加了剩余的轮，表示对应的密文空间，攻击者穷举涉及到的子密钥，计算并判断，是否成立。若成立，则认为穷举的密钥是正确密钥；这一小节中，表示轮迭代中涉及到的轮子密钥。

3 MIBS密码8轮零相关线性逼近和密钥扩展算法的一些性质

本节主要介绍构造关于MIBS的8轮零相关线性逼近和密钥扩展算法的一些性质。对密码算法做分析是在零相关线性逼近的基础上往前和往后添加轮数，并做部分加解密，在此过程中应该最大限度地利用密钥扩展算法的性质减少密钥的穷举量，进而减少复杂度。这就涉及到寻找合适的零相关线性逼近的问题。通过分析，我们构造下面的零相关线性逼近。

3.1 MIBS算法8轮零相关线性逼近

本文主要通过线性掩码在相关系数非零的条件下从前和从后两个方向从中间传播，最后在中间某个位置相遇，并且产生相关系数为零的矛盾状态的方式来构造零相关线性逼近。在非线性部件，比如S盒等部件，线性掩码的传播有下面的规律。

命题 1[10]设是可逆函数，输入掩码为，输出掩码为。若，则可得,同时为零或者同时不为零。

命题 2[10]设是一个矩阵并且线性函数定义为。若输入掩码为，输出掩码为，则当且仅当。

上面两个命题给出了非零相关系数条件下，线性掩码在非线性和线性部件的传播规律。利用这些规律，我们可以得到关于MIBS的8轮的零相关线性逼近。

图1 MIBS算法8轮零相关线性逼近

3.2 MIBS-80密钥扩展算法的一些性质

本节主要介绍MIBS-80算法的密钥扩展算法的一些特点。该密钥扩展算法受到PRESENT算法的密钥扩展算法的影响。在密钥生成的过程中，若不计移位操作，每一轮仅改变12 bit主密钥，所以轮子密钥之间存在很多关系。充分利用轮子密钥之间的关系，减少攻击过程中的需要猜测的密钥量，从而减少复杂度。

命题 3[7]对于MIBS-80而言，若需要猜测轮子密钥，则只要猜测4 bit主密钥，其中。若时，则分别取值为,,和这4 bit值。

命题3结论是正确的，但是文献[7]的证明不太清楚。异或轮常数运算输出的每个bit仅仅和输入的相应bit有关系，所以没有扩散效果，然而S盒是每一个输出bit都和输入的每一个bit有关，也就具有一定的扩散效果。但是由于主密钥长度80 bit和循环左移位参数19 bit的设置，每经过4轮移位打乱的4 bit半个字又重新组成半个字。然而做过S盒变换的半字节必须经过4轮的倍数(包括4)之后才有可能再做S盒操作。所以扩散也仅仅在最初分组的4 bit半字节中。

从密钥扩展算法和上面的命题，我们可以得到下面关于轮子密钥之间的关系。

4 13轮MIBS-80的多维零相关分析

本节主要利用上面构造的8轮(3-10)零相关线性逼近，往前扩展2轮并且往后扩展3轮，结合轮子密钥之间的关系和部分和技术，对13轮MIBS-80做多维零相关线性分析，如图2所示。具体攻击过程如下：

图2 13轮MIBS-80的多维零相关分析

(14)以上过程中猜测了55 bit密钥，然后穷举并验证其他25 bit密钥。

5 11轮MIBS-80的积分分析

文献[12]揭示了零相关线性逼近和积分区分器之间的关系，并且利用推导出的积分区分器对31轮Skipjack-BABABABA密码算法做了积分分析。它们之间的数学联系可以概括成下面的定理。

定理2[12]设，函数是上的向量布尔函数，并且,以及是正整数，则下面两个条件等价。

若是随机情况下，推论2出现的概率为

下面我们给出11轮MIBS-80的积分分析。见图3，其中表示相应的半字节跑遍所有状态。具体攻击过程如下。

图3 11轮MIBS-80的积分分析

数器8 bit够用。

6 结束语

本文主要评估了MIBS-80密码算法关于多维零相关方法和积分攻击方法的安全性。首先利用MIBS算法结构的特点和密钥扩展算法的特点，构造出了一些合适的28个8轮零相关线性逼近和揭示了一些轮子密钥之间的关系。结合部分和技术，我们对13轮的MIBS-80进行了多维零相关分析，结果显示比穷举具有bit的优势。另外，我们利用零相关线性逼近和积分区分器之间的关系，推导出一个积分区分器，并对11轮MIBS-80进行了积分攻击，将积分攻击的结果改进一轮。值得注意的是，本文选择的零相关线性逼近是最优的，这并不能保证转化过来的积分区分器最优，所以可能存在很好的积分区分器和更好的积分分析结果。另外，这两个方法对MIBS-64同样适用。单密钥下的主要分析结果，见表1。尽管本文的两个结果都没有达到线性分析所能分析的18轮，但是它们从不同的角度反映密码设计的某些特点，也给出一个理解零相关分析和积分分析之间联系的例子。

表1 单密钥MIBS-80的主要分析结果

注：CPs 表示选择明文；KPs 表示已知明文。

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

[2] 杨林, 王美琴. 简约轮的MIBS算法的差分分析[J]. 山东大学学报(理学版), 2010, 45(4): 12-15.

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

[3] BAY A, NAKAJARA J, and VAUDENAY S. Cryptanalysis of reduced-round MIBS block cipher[C]. CANS 2010. Berlin: Springer, 2010: 1-19.

[4] 杜承航, 陈佳哲. 轻量级分组密码算法MIBS 不可能差分分析[J]. 山东大学学报(理学版), 2012, 47(7): 55-58.

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

, 王少辉. 对MIBS算法的Integral攻击[J]. 小型微型计算机系统, 2012, 33(4): 773-777. doi: 10.3969/j.issn. 1000-1220.2012.04.020

WANG G and WANG S. Integral cryptanalysis of reduced round MIBS block ciphe[J]., 2012, 33(4): 773-777. doi: 10.3969/j.issn.1000-1220. 2012.04.020.

, 吴文玲, 李艳俊. 低轮MIBS分组密码的积分分析[J]. 计算机研究与发展, 2013, 50(10): 2117-2125.

YU X, WU W, and LI Y. Integral attack of reduced-round MIBS block ciper[J]., 2013, 50(10): 2117-2125.

[7] 潘志舒, 郭建胜, 曹进克, 等. MIBS算法的积分攻击[J]. 通信学报, 2014, 35(7): 157-163.

PAN Z, GUO J, CAO J,. Integral attack on MIBS block cipher[J].2014, 35(7): 157-163.

[8] 刘超, 廖福成, 卫宏儒. 对MIBS算法的中间相遇攻击[J]. 内蒙古大学学报(自然科学版), 2013, 44(3): 308-315.

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

[9] 陈平, 廖福成, 卫宏儒. 对轻量级MIBS算法的相关密钥不可能差分攻击[J]. 通信学报, 2014, 35(2): 190-193.

CHEN P, LIAO F, and WEI H. Related-key impossible differential attack on a lightweight block cipher MIBS[J]., 2014, 35(2): 190-193.

[10] BOGDANOV A and RIJMEN V. Linear hulls with correlation zero and linear cryptanalysis of block ciphers[J].,,2014, 70(3): 369-383. doi: 10.1007/s10623-012-9697-z.

[11] BOGDANOV A and WANG M. Zero correlation linear cryptanalysis with reduced data complexity[C]. FSE 2012, Washington, DC, USA, 2012: 29-48. doi: 10.1007/978-3- 642-34047-5_3.

[12] BOGDANOV A, LEANDER G, NYBERG K,. Integral and multidimensional linear distinguishers with correlation zero[C]. ASIACRYPT 2012, Beijing, China, 2012: 244-261. doi: 10.1007/978-3-642-34961-4_16.

[13] SOLEIMANY H and NYBERG K. Zero-correlation linear cryptanalysis of reduced-round LBlock[J],2014, 73(2): 683-698. doi: 10.1007/ s10623-014-9976-y.

[14] WEN L, WANG M, and BOGDANOV A. Multidimensional zero-correlation linear cryptanalysis of E2[C]. AFRICACRYPT 2014, Marrakesh, Morocco, 2014: 147-164. doi: 10.1007/978-3-319-06734-6_10.

[15] BOGDANOV A, GENG H, WANG M,. Zero-correlation linear cryptanalysis with FFT and improved attacks on ISO standards Camellia and CLEFIA[C]. SAC 2013, Burnaby, BC, Canada, 2013: 306-323. doi: 10.1007/ 978-3-662-43414-7_16.

[16] BOGDANOV A, KNUDSEN L,LEANDER G,PRESENT: an ultra-lightweight block cipher[C]. CHESS 2007, Vol. 4727: 450-466. doi: 10.1007/978-3-540-74735- 2_31.

伊文坛： 男，1989年生，博士生，研究方向为分组密码安全性分析.

鲁林真： 男，1985年生，博士生，研究方向为分组密码安全性分析.

陈少真： 女，1967年生，教授，研究方向为密码学与信息安全.

Integral and Zero-correlation Linear Cryptanalysis of Lightweight Block Cipher MIBS

YI Wentan LU Linzhen CHEN Shaozhen

(State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China)

MIBS is a light weight block cipher for constrained resources environments such as RFID tags and sensor networks. This paper investigates the construction of zero-correlation linear approximations of 8-round MIBS and presents an attack on 13-round MIBS-80 by means of zero-correlation linear cryptanalysis with the properties of key schedule and partial-sum technique, which needs 262.1known plaintexts and 274.9encryptions. Furthermore, an 8-round integral distinguisher is deduced from the zero-correlation linear approximations using the relations between them, and as an application, integral attack on 11-round MIBS-80 is conducted with 260chosen plaintexts and 259.8encryptions.

Block cipher; MIBS; Zero-correlation linear cryptanalysis; Integral attack

TP309

A

1009-5896(2016)04-0819-08

10.11999/JEIT150498

2015-04-30；改回日期：2016-01-06；网络出版：2016-02-18

伊文坛 nlwt89@sina.com