王高麗　　　甘　楠

1(華東師范大學(xué)計(jì)算機(jī)科學(xué)與軟件工程學(xué)院　上?！?00062)

2　　　(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　上?！?01620)

(glwang@sei.ecnu.edu.cn)

?

對(duì)8輪mCrypton-96的中間相遇攻擊

王高麗1,2甘楠2

1(華東師范大學(xué)計(jì)算機(jī)科學(xué)與軟件工程學(xué)院上海200062)

2(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院上海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

摘要在分析分組密碼算法的安全性時(shí)，利用密鑰關(guān)系來降低時(shí)間、存儲(chǔ)和數(shù)據(jù)復(fù)雜度是一個(gè)常用的手段.在4輪mCrypton-96性質(zhì)的基礎(chǔ)上，利用密鑰生成算法的弱點(diǎn)和S盒的性質(zhì)，降低了攻擊過程中需要猜測(cè)的密鑰比特?cái)?shù)，提出了對(duì)8輪mCrypton-96算法的中間相遇攻擊，攻擊的時(shí)間復(fù)雜度約為2(93.5)次8輪mCrypton-96加密運(yùn)算，存儲(chǔ)復(fù)雜度為2(47)B，數(shù)據(jù)復(fù)雜度為2(57)個(gè)選擇明文.

關(guān)鍵詞密碼算法分析；中間相遇攻擊；分組密碼；mCrypton；密鑰關(guān)系

分組密碼算法在現(xiàn)代密碼學(xué)中有著舉足輕重的地位，1997—2000年美國高級(jí)加密標(biāo)準(zhǔn)(advance encryption stand, AES)算法征集活動(dòng)大大促進(jìn)了分組密碼算法的設(shè)計(jì)和分析.繼美國新一代加密算法標(biāo)準(zhǔn)確定之后，歐洲、日本和韓國等多國都開始各自征集密碼算法標(biāo)準(zhǔn)，這將分組密碼的分析和設(shè)計(jì)推向了一個(gè)高潮.最近，輕量級(jí)分組密碼算法由于它的密鑰關(guān)系更簡(jiǎn)單、使用的電腦硬件資源更少、加密速度優(yōu)于一般的分組密碼算法而廣泛用于資源受限的環(huán)境，如射頻識(shí)別卡(radio frequency identification, RFID)和嵌入式環(huán)境.輕量級(jí)分組密碼算法LED，Zorro，mCrypton，PRESENT，Piccolo，Klein，XTEA，DESL，HIGHT，CLEFIA，Twine，KATAN，輕量級(jí)流密碼算法Grain和Trivium，以及基于PRESENT 的輕量級(jí)雜湊函數(shù)等算法的出現(xiàn)大大促進(jìn)了輕量級(jí)密碼的發(fā)展.與此同時(shí)，出現(xiàn)了許多對(duì)于輕量級(jí)分組密碼算法的分析方法.

1977年Diffie和Hellman[1]首次提出了中間相遇攻擊方法.Henri和Minier[2]在2000年改進(jìn)了對(duì)于AES算法的中間相遇攻擊結(jié)果，根據(jù)4輪AES算法的性質(zhì)，給出了7輪AES算法的中間相遇攻擊.Demirci，Selcuk[3]在2008年在5輪AES算法差分性質(zhì)的基礎(chǔ)上，用中間相遇攻擊方法進(jìn)一步改進(jìn)了對(duì)8輪AES-256的分析結(jié)果.其中，5輪AES算法的性質(zhì)是由4輪性質(zhì)發(fā)展而來的.2010年，Dunkelman，Keller等人[4]改進(jìn)了對(duì)于78輪AES-192和AES-256的分析結(jié)果.2013年，Derbez, Fouque, Jean[5]改進(jìn)了對(duì)于7輪AES-128的中間相遇攻擊結(jié)果，并且給出了對(duì)于8輪AES-192，AES-256的攻擊.2014年，李雷波、王小云等人[6]利用密鑰生成算法的性質(zhì)改進(jìn)了5輪AES的性質(zhì)，給出了對(duì)AES-192的9輪中間相遇攻擊.另外，文獻(xiàn)[7-12]給出了對(duì)于其他分組密碼算法的中間相遇攻擊.

2006年，Lim和Korkishko[13]提出了mCrypton算法，它是一個(gè)典型的輕量級(jí)分組密碼算法.mCrypton是Crypton算法的縮減版，采用SPN結(jié)構(gòu)，包含3個(gè)版本，密鑰長度分別為64 b,96 b,128 b.

1符號(hào)說明

U:(U0,U1,U2,U3,U4,U5)，每個(gè)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輪的輪密鑰經(jīng)過轉(zhuǎn)置和列混合之后的狀態(tài)；

ur,k：表示ur的第k個(gè)半字節(jié)(4 b);

⊕：“異或”運(yùn)算;

·：“與”運(yùn)算;

ΔX：X⊕X′;

2mCrypton算法

2.1加密運(yùn)算

mCrypton算法是基于代換-置換網(wǎng)絡(luò)(substi-tution permutation network, SPN)結(jié)構(gòu)的64 b的輕量級(jí)分組密碼算法，包含3個(gè)版本，密鑰長度分別為64 b，96 b，128 b，這3個(gè)版本都是12輪.如矩陣A所示，將64 b的明文分組排列成4×4的矩陣，其中每個(gè)ai為4 b.

S盒γ：mCrypton的S盒運(yùn)算包含4個(gè)4×4 S盒：S0，S1，S2，S3，其中S0=S2-1，S1=S3-1.設(shè)S盒的輸入為A,則其輸出為

比特置換π：比特置換與算法的列混合運(yùn)算有相同的功能，對(duì)于矩陣A的每一列分別做比特置換.設(shè)矩陣A=(A0,A1,A2,A3)，則經(jīng)比特置換后的輸出為π(A)=(π0(A0),π1(A1),π2(A2),π3(A3)).其中，πi定義如下：令a=(a0,a1,a2,a3)=Ai(0≤i≤3)，則經(jīng)過πi變換后的輸出為b=(b0,b1,b2,b3)，其中：

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

密鑰加：設(shè)輸入為(A,K)，其中:

則經(jīng)過密鑰加運(yùn)算后的輸出為

A⊕K=

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

綜上所述，mCrypton算法的1輪加密過程為：ρkr(x)=σkr°τ°π°γ(x).經(jīng)過12輪運(yùn)算后，再經(jīng)過τ°π°τ運(yùn)算，即可得密文.

2.296位密鑰生成規(guī)則

首先，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經(jīng)典的中間相遇攻擊

將分組密碼算法分成2個(gè)部分E1和E2.E1所用的密鑰為K1，E2所用的密鑰為K2，遍歷K1，將明文P經(jīng)過E1加密得到E1(P)，并將其存入表T1.遍歷K2，將相應(yīng)的密文C經(jīng)過E2解密，得到D2(C).檢測(cè)D2(C)的值是否存在表T1中，如果存在，則密鑰(K1，K2)為候選密鑰.重新選取明文，繼續(xù)上述步驟，直到候選密鑰唯一確定.

3.2對(duì)AES的中間相遇攻擊

由于mCrypton算法和AES類似，對(duì)AES中間相遇攻擊的研究可以作為參考.文獻(xiàn)[3]給出4輪AES性質(zhì)，并在4輪性質(zhì)前加1輪，后面加2輪，給出了7輪AES的中間相遇攻擊.

定義1.δ集是x除去某個(gè)特定單元(特定單元值遍歷0,1,…,2n-1)，其他單元都是常數(shù)的2n個(gè)明文組成的集合，其中n為數(shù)據(jù)單元的二進(jìn)制長度.

預(yù)計(jì)算過程：

攻擊過程：

Fig. 1　Meet in the middle attack on 7-round AES in Ref [3].圖1　文獻(xiàn)[3]對(duì)7輪AES的攻擊

2013年，Derbez, Fouque, Jean[5]在4輪性質(zhì)中利用S盒的差分性質(zhì)降低了計(jì)算多重集所需的參數(shù)個(gè)數(shù)，將多重集可能的取值由2128降低到280.因此將攻擊7輪AES-128的時(shí)間、空間和數(shù)據(jù)復(fù)雜度都降低到2100以下，并成功地改進(jìn)了對(duì)8輪AES-192，AES-256的分析結(jié)果.

2014年，李雷波、王小云等人[6]利用密鑰關(guān)系，提出了對(duì)5輪AES-192，AES-256的性質(zhì)，并在此基礎(chǔ)上首次給出了對(duì)9輪AES-192的中間相遇攻擊，同時(shí)改進(jìn)了對(duì)9輪AES-256的分析結(jié)果.

48輪mCrypton-96的中間相遇攻擊

4.14輪mCrypton的性質(zhì)

性質(zhì)2.S盒性質(zhì)[20].如果S盒的輸入差分唯一確定，輸出差分唯一確定，則S盒輸入對(duì)和輸出對(duì)平均都只有1個(gè)值.

Fig. 2　the 4-round differential characteristic.圖2　4輪mCrypton的性質(zhì)

4輪mCrypton的性質(zhì)證明如下：

證畢.

說明：該有序序列最多有244種可能的取值，而在隨機(jī)情況下，其有264種取值.

4.2輪密鑰之間的關(guān)系

性質(zhì)4. 令主密鑰為K，中間變量值為U，將U初始化：U=K.則由K8可得u7第1位的值.

證明. 根據(jù)密鑰生成算法，可得K8的表達(dá)式為

因?yàn)镾(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的表達(dá)式為

將K7進(jìn)行轉(zhuǎn)置、列混合運(yùn)算，得u7,2為

證畢.

性質(zhì)5. 由K8與K0,{2,6,10,14}都可求出U1[7，6，5，4]和U2[7，6，5，4]的值.

證明. 由密鑰生成算法，可知K0的表達(dá)式如下：

從而由K0,{2,6,10,14}可推出U1[7，6，5，4]和U2[7，6，5，4].另一方面，由性質(zhì)1的證明可知：由K8亦可推出U1[7，6，5，4]和U2[7，6，5，4].

證畢.

4.38輪mCrypton-96的攻擊過程

本節(jié)充分利用密鑰之間的關(guān)系，給出對(duì)8輪mCrypton-96的中間相遇攻擊，攻擊過程如圖3所示:

Fig. 3　Meet in the middle attack on 8-round mCrypton-96.圖3　對(duì)8輪mCrypton-96的攻擊

預(yù)計(jì)算過程：

攻擊過程：

1) 選擇241個(gè)明文結(jié)構(gòu)，每個(gè)明文結(jié)構(gòu)包含216個(gè)明文，其遍歷第2，6，10，14個(gè)半字節(jié)的值，其余半字節(jié)的值為常數(shù).則一共有241×231=272對(duì)明文，計(jì)算其相應(yīng)的密文.

2) 對(duì)于每個(gè)明密文對(duì)，猜測(cè)Δy6,{0,1,2,3}，經(jīng)過比特置換和轉(zhuǎn)置，因?yàn)槠涠际蔷€性變化，所以能夠計(jì)算出相應(yīng)的Δx7，又由密文對(duì)經(jīng)過相應(yīng)的線性變化可以計(jì)算出Δy7，從而根據(jù)S盒性質(zhì)，由(Δx7，Δy7)可計(jì)算出(x7,y7)，將y7經(jīng)過線性變化得到w7，與x8進(jìn)行異或運(yùn)算可得K8.

3) 猜測(cè)Δy5，0，進(jìn)行相應(yīng)的線性運(yùn)算，計(jì)算出Δx6,{0,1,2,3}，根據(jù)S盒的性質(zhì)，計(jì)算出y6,{0,1,2,3}，然后將x7經(jīng)過相應(yīng)的線性變化，與y6,{0,1,2,3}進(jìn)行異或，計(jì)算出相應(yīng)的u7,{0,1,2,3}.再根據(jù)性質(zhì)4，由u7,{0,1,2,3}和第2)步計(jì)算出的K8可排除掉2種情況.

4) 猜測(cè)w0,2，經(jīng)過相應(yīng)的線性變化，計(jì)算出Δy0,{2,6,10,14}，從明文對(duì)計(jì)算出Δx0,{2,6,10,14}，根據(jù)S盒的性質(zhì)，計(jì)算出x0,{2,6,10,14}，再異或上明文，得到K0,{2,6,10,14}.則根據(jù)性質(zhì)5，由K8與K0可排除掉28種情況.

6) 查Hash表T，如果表T中存在有序序列的值，則認(rèn)為密鑰猜測(cè)是正確的.窮舉搜索其余未知的密鑰.

根據(jù)攻擊過程可知時(shí)間復(fù)雜度主要由攻擊過程的步驟3～5構(gòu)成.步驟1的復(fù)雜度是對(duì)257個(gè)明文進(jìn)行8輪mCrypton加密.步驟2對(duì)每1對(duì)明文都猜測(cè)Δy6,{0,1,2,3}，所以步驟2的時(shí)間復(fù)雜度約為2722162-3次8輪mCrypton加密.步驟3在步驟2的基礎(chǔ)上又猜測(cè)了Δy5，0，即增加了24種情況，每一種情況可以計(jì)算出1個(gè)u7,{0,1,2,3}，所以步驟3的時(shí)間復(fù)雜度約為272×220×2-3次8輪mCrypton加密運(yùn)算.步驟4在步驟3的基礎(chǔ)上又猜測(cè)了w0,2，每一種情況可以計(jì)算出1個(gè)K0，{2,6,10,14}，所以步驟4的時(shí)間復(fù)雜度約為272×224×2-4次8輪mCrypton加密運(yùn)算.步驟5的時(shí)間復(fù)雜度約為272×219×24×2-2次8輪mCrypton加密運(yùn)算.從而在線攻擊的時(shí)間復(fù)雜度約為293.5.相對(duì)于在線攻擊時(shí)間復(fù)雜度，預(yù)計(jì)算的時(shí)間復(fù)雜度可以忽略不計(jì).預(yù)計(jì)算過程的存儲(chǔ)復(fù)雜度是247B，在線攻擊的存儲(chǔ)復(fù)雜度忽略不計(jì).數(shù)據(jù)復(fù)雜度為257個(gè)選擇明文.

5總結(jié)

本文通過研究發(fā)現(xiàn)了mCrypton-96密鑰生成算法的漏洞，利用密鑰生成算法的弱點(diǎn)并結(jié)合4輪mCrypton-96算法的性質(zhì)[14]，給出了8輪mCrypton-96算法的中間相遇攻擊，比之前的分析結(jié)果增加了1輪.攻擊的時(shí)間復(fù)雜度為293.5次加密運(yùn)算，數(shù)據(jù)復(fù)雜度為257個(gè)選擇明文，空間復(fù)雜度為247B.關(guān)于mCrypton算法的分析結(jié)果如表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.

參考文獻(xiàn)

[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]

中圖法分類號(hào)TP309

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61572125,61373142)；東華大學(xué)碩士研究生學(xué)位論文創(chuàng)新資助項(xiàng)目(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).