對8輪mCrypton-96的中間相遇攻擊

王高麗　　　甘　楠

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

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

(glwang@sei.ecnu.edu.cn)

?

對8輪mCrypton-96的中間相遇攻擊

王高麗1,2甘楠2

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

2(東華大學(xué)計算機科學(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

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

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

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

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

2006年，Lim和Korkishko[13]提出了mCrypton算法，它是一個典型的輕量級分組密碼算法.mCrypton是Crypton算法的縮減版，采用SPN結(jié)構(gòu)，包含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輪的輪密鑰經(jīng)過轉(zhuǎn)置和列混合之后的狀態(tài)；

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

⊕：“異或”運算;

·：“與”運算;

ΔX：X⊕X′;

2mCrypton算法

2.1加密運算

mCrypton算法是基于代換-置換網(wǎng)絡(luò)(substi-tution permutation network, SPN)結(jié)構(gòu)的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.設(shè)S盒的輸入為A,則其輸出為

比特置換π：比特置換與算法的列混合運算有相同的功能，對于矩陣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)過密鑰加運算后的輸出為

A⊕K=

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

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

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

3.2對AES的中間相遇攻擊

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

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

預(yù)計算過程：

攻擊過程：

Fig. 1　Meet in the middle attack on 7-round AES in Ref [3].圖1　文獻[3]對7輪AES的攻擊

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

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

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

4.14輪mCrypton的性質(zhì)

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

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

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

證畢.

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

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

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

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

因為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的表達(dá)式為

將K7進行轉(zhuǎ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)系，給出對8輪mCrypton-96的中間相遇攻擊，攻擊過程如圖3所示:

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

預(yù)計算過程：

攻擊過程：

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

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

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

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

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

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

5總結(jié)

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

參考文獻

[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

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