对8轮mCrypton-96的中间相遇攻击

王高丽　　　甘　楠

1(华东师范大学计算机科学与软件工程学院　上海　200062)

2　　　(东华大学计算机科学与技术学院　上海　201620)

(glwang@sei.ecnu.edu.cn)



对8轮mCrypton-96的中间相遇攻击

王高丽1,2甘楠2

1(华东师范大学计算机科学与软件工程学院上海200062)

2(东华大学计算机科学与技术学院上海201620)

(glwang@sei.ecnu.edu.cn)

A Meet-in-the-Middle Attack on 8-Round mCrypton-96

Wang Gaoli1,2and Gan Nan2

1(SchoolofComputerScienceandSoftwareEngineering,EastChinaNormalUniversity,Shanghai200062)

2(SchoolofComputerScienceandTechnology,DonghuaUniversity,Shanghai201620)

AbstractmCrypton is a lightweight block cipher introduced in Information Security Application 2006 by Lim and Korkishko. mCrypton-6496128 denote 3 versions of the cipher with 6496128 b keys respectively. In this paper, we apply the meet-in-the-middle (MITM) attack on 8-round mCrypton-96, which improves the best MITM attack result on mCrypton-96 by 1 round.When analyzing the security of block ciphers, using key relations to reduce the time complexity, memory complexity and data complexity is a common method. From the property of the key schedule of mCrypton-96, we know that each round key could calculate some information of the internal register by the algebraic structure of the key schedule, and some round keys could be deduced from the other round keys. By using the relationship of key schedule and the properties of S-box, we present a MITM attack on 8-round mCrypton-96 based on the 4-round distinguisher by adding 1 round on the top and 3 rounds at the bottom. The time, memory and data complexities of the attack are 293.5encryptions, 247B and 257chosen plaintexts respectively. It is illustrated that mCrypton-96 not only has an efficient performance but also possesses strong security.

Key wordscryptanalysis; meet-in-the-middle (MITM) attack; block ciphers; mCrypton; relationship of keys

摘要在分析分组密码算法的安全性时，利用密钥关系来降低时间、存储和数据复杂度是一个常用的手段.在4轮mCrypton-96性质的基础上，利用密钥生成算法的弱点和S盒的性质，降低了攻击过程中需要猜测的密钥比特数，提出了对8轮mCrypton-96算法的中间相遇攻击，攻击的时间复杂度约为2(93.5)次8轮mCrypton-96加密运算，存储复杂度为2(47)B，数据复杂度为2(57)个选择明文.

关键词密码算法分析；中间相遇攻击；分组密码；mCrypton；密钥关系

分组密码算法在现代密码学中有着举足轻重的地位，1997—2000年美国高级加密标准(advance encryption stand, AES)算法征集活动大大促进了分组密码算法的设计和分析.继美国新一代加密算法标准确定之后，欧洲、日本和韩国等多国都开始各自征集密码算法标准，这将分组密码的分析和设计推向了一个高潮.最近，轻量级分组密码算法由于它的密钥关系更简单、使用的电脑硬件资源更少、加密速度优于一般的分组密码算法而广泛用于资源受限的环境，如射频识别卡(radio frequency identification, RFID)和嵌入式环境.轻量级分组密码算法LED，Zorro，mCrypton，PRESENT，Piccolo，Klein，XTEA，DESL，HIGHT，CLEFIA，Twine，KATAN，轻量级流密码算法Grain和Trivium，以及基于PRESENT 的轻量级杂凑函数等算法的出现大大促进了轻量级密码的发展.与此同时，出现了许多对于轻量级分组密码算法的分析方法.

1977年Diffie和Hellman[1]首次提出了中间相遇攻击方法.Henri和Minier[2]在2000年改进了对于AES算法的中间相遇攻击结果，根据4轮AES算法的性质，给出了7轮AES算法的中间相遇攻击.Demirci，Selcuk[3]在2008年在5轮AES算法差分性质的基础上，用中间相遇攻击方法进一步改进了对8轮AES-256的分析结果.其中，5轮AES算法的性质是由4轮性质发展而来的.2010年，Dunkelman，Keller等人[4]改进了对于78轮AES-192和AES-256的分析结果.2013年，Derbez, Fouque, Jean[5]改进了对于7轮AES-128的中间相遇攻击结果，并且给出了对于8轮AES-192，AES-256的攻击.2014年，李雷波、王小云等人[6]利用密钥生成算法的性质改进了5轮AES的性质，给出了对AES-192的9轮中间相遇攻击.另外，文献[7-12]给出了对于其他分组密码算法的中间相遇攻击.

2006年，Lim和Korkishko[13]提出了mCrypton算法，它是一个典型的轻量级分组密码算法.mCrypton是Crypton算法的缩减版，采用SPN结构，包含3个版本，密钥长度分别为64 b,96 b,128 b.

1符号说明

U:(U0,U1,U2,U3,U4,U5)，每个Ur表示16 b;

Ur[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]：16 b,Ur的第0位在最右边；

Kr：第r轮的轮密钥；

ur：表示第r轮的轮密钥经过转置和列混合之后的状态；

ur,k：表示ur的第k个半字节(4 b);

⊕：“异或”运算;

·：“与”运算;

ΔX：X⊕X′;

2mCrypton算法

2.1加密运算

mCrypton算法是基于代换-置换网络(substi-tution permutation network, SPN)结构的64 b的轻量级分组密码算法，包含3个版本，密钥长度分别为64 b，96 b，128 b，这3个版本都是12轮.如矩阵A所示，将64 b的明文分组排列成4×4的矩阵，其中每个ai为4 b.

S盒γ：mCrypton的S盒运算包含4个4×4 S盒：S0，S1，S2，S3，其中S0=S2-1，S1=S3-1.设S盒的输入为A,则其输出为

比特置换π：比特置换与算法的列混合运算有相同的功能，对于矩阵A的每一列分别做比特置换.设矩阵A=(A0,A1,A2,A3)，则经比特置换后的输出为π(A)=(π0(A0),π1(A1),π2(A2),π3(A3)).其中，πi定义如下：令a=(a0,a1,a2,a3)=Ai(0≤i≤3)，则经过πi变换后的输出为b=(b0,b1,b2,b3)，其中：

m0=11102,m1=11012,m2=10112,m3=01112.

密钥加：设输入为(A,K)，其中:

则经过密钥加运算后的输出为

A⊕K=

其中,ai，ki(0≤i≤15)的长度都是4 b.

综上所述，mCrypton算法的1轮加密过程为：ρkr(x)=σkr∘τ∘π∘γ(x).经过12轮运算后，再经过τ∘π∘τ运算，即可得密文.

2.296位密钥生成规则

首先，U=(U0,U1,U2,U3,U4,U5)=K，其中K为主密钥，则轮密钥Kr的生成过程如下：

1) T=S(U0)⊕Cr,Ti=T·Mi,

其中,M0=0xf000，M1=0x0f00，M2=0x00f0，M3=0x000f.

3中间相遇攻击

3.1经典的中间相遇攻击

将分组密码算法分成2个部分E1和E2.E1所用的密钥为K1，E2所用的密钥为K2，遍历K1，将明文P经过E1加密得到E1(P)，并将其存入表T1.遍历K2，将相应的密文C经过E2解密，得到D2(C).检测D2(C)的值是否存在表T1中，如果存在，则密钥(K1，K2)为候选密钥.重新选取明文，继续上述步骤，直到候选密钥唯一确定.

3.2对AES的中间相遇攻击

由于mCrypton算法和AES类似，对AES中间相遇攻击的研究可以作为参考.文献[3]给出4轮AES性质，并在4轮性质前加1轮，后面加2轮，给出了7轮AES的中间相遇攻击.

定义1.δ集是x除去某个特定单元(特定单元值遍历0,1,…,2n-1)，其他单元都是常数的2n个明文组成的集合，其中n为数据单元的二进制长度.

预计算过程：

攻击过程：

Fig. 1　Meet in the middle attack on 7-round AES in Ref [3].图1　文献[3]对7轮AES的攻击

2013年，Derbez, Fouque, Jean[5]在4轮性质中利用S盒的差分性质降低了计算多重集所需的参数个数，将多重集可能的取值由2128降低到280.因此将攻击7轮AES-128的时间、空间和数据复杂度都降低到2100以下，并成功地改进了对8轮AES-192，AES-256的分析结果.

2014年，李雷波、王小云等人[6]利用密钥关系，提出了对5轮AES-192，AES-256的性质，并在此基础上首次给出了对9轮AES-192的中间相遇攻击，同时改进了对9轮AES-256的分析结果.

48轮mCrypton-96的中间相遇攻击

4.14轮mCrypton的性质

性质2.S盒性质[20].如果S盒的输入差分唯一确定，输出差分唯一确定，则S盒输入对和输出对平均都只有1个值.

Fig. 2　the 4-round differential characteristic.图2　4轮mCrypton的性质

4轮mCrypton的性质证明如下：

证毕.

说明：该有序序列最多有244种可能的取值，而在随机情况下，其有264种取值.

4.2轮密钥之间的关系

性质4. 令主密钥为K，中间变量值为U，将U初始化：U=K.则由K8可得u7第1位的值.

证明. 根据密钥生成算法，可得K8的表达式为

因为S(U4<<<11)⊕C8·M0的低12 b的值为0，故U5<<<14⊕[S(U4<<<11)⊕C8·M0]低12 b的值等于U5<<<14低12 b的值，从而由K8可得：

U5[13，12，11，10;9，8，7，6;5，4，3，2].

同理，由K8可得：

U0[1，0，15，14;9，8，7，6;5，4，3，2]，

U1[4,3,2,1；0,15,14,13；8,7,6,5]，

U2[12，11，10，9;8，7，6，5;4，3，2，1].

另一方面，K7的表达式为

将K7进行转置、列混合运算，得u7,2为

证毕.

性质5. 由K8与K0,{2,6,10,14}都可求出U1[7，6，5，4]和U2[7，6，5，4]的值.

证明. 由密钥生成算法，可知K0的表达式如下：

从而由K0,{2,6,10,14}可推出U1[7，6，5，4]和U2[7，6，5，4].另一方面，由性质1的证明可知：由K8亦可推出U1[7，6，5，4]和U2[7，6，5，4].

证毕.

4.38轮mCrypton-96的攻击过程

本节充分利用密钥之间的关系，给出对8轮mCrypton-96的中间相遇攻击，攻击过程如图3所示:

Fig. 3　Meet in the middle attack on 8-round mCrypton-96.图3　对8轮mCrypton-96的攻击

预计算过程：

攻击过程：

1) 选择241个明文结构，每个明文结构包含216个明文，其遍历第2，6，10，14个半字节的值，其余半字节的值为常数.则一共有241×231=272对明文，计算其相应的密文.

2) 对于每个明密文对，猜测Δy6,{0,1,2,3}，经过比特置换和转置，因为其都是线性变化，所以能够计算出相应的Δx7，又由密文对经过相应的线性变化可以计算出Δy7，从而根据S盒性质，由(Δx7，Δy7)可计算出(x7,y7)，将y7经过线性变化得到w7，与x8进行异或运算可得K8.

3) 猜测Δy5，0，进行相应的线性运算，计算出Δx6,{0,1,2,3}，根据S盒的性质，计算出y6,{0,1,2,3}，然后将x7经过相应的线性变化，与y6,{0,1,2,3}进行异或，计算出相应的u7,{0,1,2,3}.再根据性质4，由u7,{0,1,2,3}和第2)步计算出的K8可排除掉2种情况.

4) 猜测w0,2，经过相应的线性变化，计算出Δy0,{2,6,10,14}，从明文对计算出Δx0,{2,6,10,14}，根据S盒的性质，计算出x0,{2,6,10,14}，再异或上明文，得到K0,{2,6,10,14}.则根据性质5，由K8与K0可排除掉28种情况.

6) 查Hash表T，如果表T中存在有序序列的值，则认为密钥猜测是正确的.穷举搜索其余未知的密钥.

根据攻击过程可知时间复杂度主要由攻击过程的步骤3～5构成.步骤1的复杂度是对257个明文进行8轮mCrypton加密.步骤2对每1对明文都猜测Δy6,{0,1,2,3}，所以步骤2的时间复杂度约为2722162-3次8轮mCrypton加密.步骤3在步骤2的基础上又猜测了Δy5，0，即增加了24种情况，每一种情况可以计算出1个u7,{0,1,2,3}，所以步骤3的时间复杂度约为272×220×2-3次8轮mCrypton加密运算.步骤4在步骤3的基础上又猜测了w0,2，每一种情况可以计算出1个K0，{2,6,10,14}，所以步骤4的时间复杂度约为272×224×2-4次8轮mCrypton加密运算.步骤5的时间复杂度约为272×219×24×2-2次8轮mCrypton加密运算.从而在线攻击的时间复杂度约为293.5.相对于在线攻击时间复杂度，预计算的时间复杂度可以忽略不计.预计算过程的存储复杂度是247B，在线攻击的存储复杂度忽略不计.数据复杂度为257个选择明文.

5总结

本文通过研究发现了mCrypton-96密钥生成算法的漏洞，利用密钥生成算法的弱点并结合4轮mCrypton-96算法的性质[14]，给出了8轮mCrypton-96算法的中间相遇攻击，比之前的分析结果增加了1轮.攻击的时间复杂度为293.5次加密运算，数据复杂度为257个选择明文，空间复杂度为247B.关于mCrypton算法的分析结果如表1所示:

Table 1　Summary of Attack Results on mCrypton

MIMT: meet-in-the-middle attack; CA: collision attack; RKIDC: relate key impossible differential cryptanalysis;

RKR: relate key rectangle attack.

参考文献

[1]Diffie W, Hellman M E. Special feature exhaustive cryptanalysis of the NBS Data Encryption Standard[J]. Computer, 1997, 10(6): 74-84

[2]Gilbert H, Minier M. A collision attack on 7 rounds of Rijndael[C]Proc of the 3rd AES Candidate Conf. Berlin: Springer, 2000: 230-241

[3]Demirci H, Selcuk A. A meet-in-the-middle attack on 8-round AES[G]LNCS 5922: Proc of Fast Software Encryption. Berlin: Springer, 2008: 116-126

[4]Dunkelman O, Keller N, Shamir A. Improved single key attack on 8-round AES-192 and AES-256[G]LNCS 6477: Proc of Advances in Cryptology—ASIACRYPT 2010. Berlin: Springer, 2010: 158-176

[5]Derbez P, Fouque P A, Jean J. Improved key recovery attacks on reduced-round AES in the single-key setting[G]LNCS 7881: Proc of Advances in Cryptology—EUROCRYPT 2013. Berlin: Springer, 2013: 371-387

[6]Li L, Jia K, Wang X. Improved single-key attacks on 9-round AES-192256[G]LNCS 8540: Proc of Fast Software Encryption. Berlin: Springer, 2015: 127-146

[7]Guo Jian, Peyrin T, Poschmann A, et al. The LED block cipher[G]LNCS 6917: Proc of Cryptographic Hardware and Embedded Systems (CHES 2011). Berlin: Springer, 2011: 326-341

[8]Gérard B, Grosso V. Block ciphers that are easier to mask: How far can we go?[G]LNCS 8086: Proc of Cryptographic Hardware and Embedded Systems—CHES 2013. Berlin: Springer, 2013: 383-399

[9]Sekar G, Mouha N, Velichkov V, et al. Meet-in-the-middle attacks on reduced-round XTEA[G]LNCS 6558: Proc of Topics in Cryptology-CT-RSA 2011. Berlin: Springer, 2011: 250-267

[10]Lu J, Wei Y, Pasalic E, et al. Meet-in-the-Middle attack on reduced versions of the camellia block cipher[G]LNCS 7631: Proc of Advances in Information and Computer Security. Berlin: Springer, 2012: 197-215

[11]Chen Jiazhe, Li Leibo. Low data complexity attack on reduced camellia-256[G]LNCS 7372: Proc of Australasian Conf on Information Security and Privacy. Berlin: Springer, 2012: 101-114

[12]Bogdanov A, Rechberger C. A 3-subset Meet-in-the-Middle Attack: Cryptanalysis of the lightweight block cipher KTANTAN[G]LNCS 6544: Proc of Selected Areas in Cryptography. Berlin: Springer, 2011: 229-240

[13]Lim C H, Korkishko T. mCrypton-A lightweight block cipher for security of low-cost RFID tags and sensors[G]

中图法分类号TP309

基金项目：国家自然科学基金项目(61572125,61373142)；东华大学硕士研究生学位论文创新资助项目(112-06-0019025)

收稿日期：2014-11-20；修回日期：2015-07-06

This work was supported by the National Natural Science Foundation of China (61572125,61373142) and the Postgraduate Dissertation Innovation Funds of Donghua University (112-06-0019025).