對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).