輕量級密碼算法MIBS的零相關(guān)和積分分析

伊文壇 魯林真 陳少真

?

輕量級密碼算法MIBS的零相關(guān)和積分分析

伊文壇*魯林真 陳少真

(數(shù)學(xué)工程與先進計算國家重點實驗室 鄭州 450001)

MIBS是適用于RFID和傳感資源受限環(huán)境的輕量級分組算法。該文構(gòu)造了一些關(guān)于MIBS的8輪零相關(guān)線性逼近，結(jié)合密鑰擴展算法的特點和部分和技術(shù)，對13輪MIBS-80進行了多維零相關(guān)分析。該分析大體需要262.1個已知明文和274.9次加密。此外，利用零相關(guān)線性逼近和積分區(qū)分器之間的內(nèi)在聯(lián)系，推導(dǎo)出8輪的積分區(qū)分器，并且對11輪的MIBS-80進行了積分攻擊，大體需要260個選擇明文和259.8次加密。

分組密碼；MIBS；零相關(guān)分析；積分攻擊

1 引言

MIBS[1]是在2009年提出的一個輕量級分組密碼算法，具有資源占用量較少的優(yōu)點，主要適用于RFID(Radio Frequency IDentification)、無線傳感技術(shù)等設(shè)備資源和計算能力有限的設(shè)備和環(huán)境中。該算法整體采用Feistel結(jié)構(gòu)，分組長度為64 bit，密鑰長度可以為64 bit和80 bit，分別記作MIBS-64和MIBS-80，都迭代32輪。目前針對MIBS的分析有差分分析、線性分析、不可能差分分析、積分分析、中間相遇分析以及相關(guān)密鑰條件下的不可能差分分析等。

文獻[2]給出了13輪MIBS-64的差分分析；之后，文獻[3]改進了關(guān)于14輪MIBS-64的差分分析結(jié)果，需要的時間復(fù)雜度為237.2次加密，數(shù)據(jù)復(fù)雜度為240個選擇明文；文獻[3]對MIBS算法的抗線性分析的能力進行了估計，結(jié)果顯示對18輪MIBS-80的線性分析大體需要260.9個已知明文和276.1次加密；文獻[3]給出了12輪MIBS-80的不可能差分分析。隨后文獻[4]指出文獻[3]工作中存在錯誤，并重新給出了12輪MIBS-80的不可能差分分析結(jié)果；文獻[5]首次利用積分分析方法分析了8輪MIBS-64和9輪MIBS-80；隨后，文獻[6]和文獻[7]分別給出了10輪MIBS-80關(guān)于積分分析的結(jié)果；2013年，文獻[8]發(fā)現(xiàn)了MIBS的6輪中間相遇區(qū)分器，結(jié)合密鑰擴展算法的特點，給出了11輪MIBS-80的中間相遇分析結(jié)果，大體需要224.9個選擇明文，266.2次加密和250次預(yù)計算；2014年，文獻[9]構(gòu)造了相關(guān)密鑰條件下的10輪的不可能差分特征，并對14輪MIBS- 80進行了攻擊，大體需要254個選擇明文和256次加密。

可以看出，評估MIBS算法的安全性一直是研究的熱點問題。然而，MIBS算法關(guān)于最近提出的零相關(guān)分析方法的分析結(jié)果還是空白。零相關(guān)線性分析方法由文獻[10]在2012年提出。該方法是利用相關(guān)系數(shù)為零的線性逼近來區(qū)分密碼算法和隨機函數(shù)，從而進行密鑰恢復(fù)攻擊的工作。最初，零相關(guān)線性分析方法利用一條零相關(guān)線性逼近，至少需要選擇一半明密文空間。多重零相關(guān)[11]利用多條零相關(guān)線性逼近，在一定程度上降低了數(shù)據(jù)量，但是要求線性逼近的輸入掩碼和輸出掩碼獨立。多維零相關(guān)[12]的提出克服了線性逼近的獨立性條件，所需數(shù)據(jù)量和多重零相關(guān)相當。最近，零相關(guān)線性分析方法在AES[10], TEA[11], CAST-256[12], LBlock[13], E2[14], Camellia[15]以及CLEFIA[15]等密碼算法的分析中取得了很好的結(jié)果。另外，文獻[12]還揭示了零相關(guān)線性逼近和積分區(qū)分器之間的關(guān)系。

本文利用零相關(guān)線性分析和積分分析方法評估MIBS-80密碼算法的安全性。根據(jù)線性層的特點，構(gòu)造了一些8輪MIBS密碼算法的零相關(guān)線性逼近；利用多維零相關(guān)線性分析方法，結(jié)合密鑰擴展算法的特點和部分和技術(shù)，對13輪的MIBS-80密碼算法做安全性分析；利用零相關(guān)區(qū)分器和積分區(qū)分器之間的聯(lián)系，推導(dǎo)出一些8輪的積分區(qū)分器；進一步，作為應(yīng)用，對11輪的MIBS-80密碼算法進行積分分析。

本文的結(jié)構(gòu)大致安排如下：在第2節(jié)中，約定一些記號，簡單介紹MIBS密碼算法、零相關(guān)分析方法和積分攻擊方法；在第3節(jié)中，構(gòu)造了一些8輪MIBS密碼算法零相關(guān)線性逼近并對13輪MIBS-80進行了多維零相關(guān)分析；在隨后的小節(jié)中，推導(dǎo)出一個8輪的積分區(qū)分器，并且利用積分分析方法分析了MIBS-80密碼算法的安全性；最后，對比了單密鑰下MIBS-80密碼算法的主要分析結(jié)果并總結(jié)本文的工作。

2 預(yù)備知識

2.1 一些記號

2.2 MIBS算法介紹

分組密碼算法MIBS總體采用了Feistel密碼結(jié)構(gòu)，分組長度為64 bit，并且迭代32輪。密鑰長度接受64 bit和80 bit，僅僅是在密鑰擴展算法上有區(qū)別，分別記為MIBS-64和MIBS-80。輪函數(shù)采用了典型的SPN(Substitution Permutation Network)結(jié)構(gòu)，包括輪子密鑰加運算、S盒變換和線性層運算。所有的操作都是在4 bit的半個字節(jié)上完成的。

本文工作主要針對MIBS-80，這里只介紹MIBS-80的密鑰擴展算法。MIBS-80的密鑰擴展算法受到PRESENT算法[16]的密鑰擴展算法的啟發(fā)。設(shè)為長度為80 bit長主密鑰，則由主密鑰生成32個32 bit的輪密鑰的過程如下：

其中，輪常數(shù)Round_counter 是所在輪序號的4 bit二進制表示。關(guān)于MIBS-64的密鑰擴展算法見文獻[1]。

2.3 多維零相關(guān)分析方法和積分分析介紹

多維零相關(guān)線性分析方法[12]選取個零相關(guān)線性逼近，并且這些線性逼近由的基線向量通過線性關(guān)系擴展。不妨記作為。攻擊者選擇對明密文對，并建立計數(shù)器，其中是bit長的向量。通過在線性逼近前后加輪，窮舉部分子密鑰并部分加解密所選取的明密文對，得到線性掩碼首尾對應(yīng)的中間狀態(tài)，為了方便記作。然后, 對于選擇的每一個明密文對經(jīng)過部分加解密得到，計算，進而，得到向量的值。更新相應(yīng)的對應(yīng)的計數(shù)器。然后，計算統(tǒng)計量：

2.3.2 積分分析方法 積分分析是一種選擇明文攻擊方法，主要利用積分區(qū)分器來恢復(fù)密鑰信息。積分區(qū)分器是根據(jù)輪函數(shù)的性質(zhì)構(gòu)造而成的。比如選擇某些特定結(jié)構(gòu)的明文，經(jīng)過若干輪迭代之后，所有對應(yīng)的輸出的某些或者全部bit異或之后為零等。不妨設(shè)輪密碼算法的前輪是滿足上述性質(zhì)的區(qū)分器，設(shè)是相應(yīng)的選擇明文空間，則有。

在具體攻擊過程中，攻擊者在區(qū)分器的一端或者兩端添加若干輪，猜測涉及到的子密鑰，在根據(jù)區(qū)分器的性質(zhì)進行密鑰篩選。不妨在后面添加了剩余的輪，表示對應(yīng)的密文空間，攻擊者窮舉涉及到的子密鑰，計算并判斷，是否成立。若成立，則認為窮舉的密鑰是正確密鑰；這一小節(jié)中，表示輪迭代中涉及到的輪子密鑰。

3 MIBS密碼8輪零相關(guān)線性逼近和密鑰擴展算法的一些性質(zhì)

本節(jié)主要介紹構(gòu)造關(guān)于MIBS的8輪零相關(guān)線性逼近和密鑰擴展算法的一些性質(zhì)。對密碼算法做分析是在零相關(guān)線性逼近的基礎(chǔ)上往前和往后添加輪數(shù)，并做部分加解密，在此過程中應(yīng)該最大限度地利用密鑰擴展算法的性質(zhì)減少密鑰的窮舉量，進而減少復(fù)雜度。這就涉及到尋找合適的零相關(guān)線性逼近的問題。通過分析，我們構(gòu)造下面的零相關(guān)線性逼近。

3.1 MIBS算法8輪零相關(guān)線性逼近

本文主要通過線性掩碼在相關(guān)系數(shù)非零的條件下從前和從后兩個方向從中間傳播，最后在中間某個位置相遇，并且產(chǎn)生相關(guān)系數(shù)為零的矛盾狀態(tài)的方式來構(gòu)造零相關(guān)線性逼近。在非線性部件，比如S盒等部件，線性掩碼的傳播有下面的規(guī)律。

命題 1[10]設(shè)是可逆函數(shù)，輸入掩碼為，輸出掩碼為。若，則可得,同時為零或者同時不為零。

命題 2[10]設(shè)是一個矩陣并且線性函數(shù)定義為。若輸入掩碼為，輸出掩碼為，則當且僅當。

上面兩個命題給出了非零相關(guān)系數(shù)條件下，線性掩碼在非線性和線性部件的傳播規(guī)律。利用這些規(guī)律，我們可以得到關(guān)于MIBS的8輪的零相關(guān)線性逼近。

圖1 MIBS算法8輪零相關(guān)線性逼近

3.2 MIBS-80密鑰擴展算法的一些性質(zhì)

本節(jié)主要介紹MIBS-80算法的密鑰擴展算法的一些特點。該密鑰擴展算法受到PRESENT算法的密鑰擴展算法的影響。在密鑰生成的過程中，若不計移位操作，每一輪僅改變12 bit主密鑰，所以輪子密鑰之間存在很多關(guān)系。充分利用輪子密鑰之間的關(guān)系，減少攻擊過程中的需要猜測的密鑰量，從而減少復(fù)雜度。

命題 3[7]對于MIBS-80而言，若需要猜測輪子密鑰，則只要猜測4 bit主密鑰，其中。若時，則分別取值為,,和這4 bit值。

命題3結(jié)論是正確的，但是文獻[7]的證明不太清楚。異或輪常數(shù)運算輸出的每個bit僅僅和輸入的相應(yīng)bit有關(guān)系，所以沒有擴散效果，然而S盒是每一個輸出bit都和輸入的每一個bit有關(guān)，也就具有一定的擴散效果。但是由于主密鑰長度80 bit和循環(huán)左移位參數(shù)19 bit的設(shè)置，每經(jīng)過4輪移位打亂的4 bit半個字又重新組成半個字。然而做過S盒變換的半字節(jié)必須經(jīng)過4輪的倍數(shù)(包括4)之后才有可能再做S盒操作。所以擴散也僅僅在最初分組的4 bit半字節(jié)中。

從密鑰擴展算法和上面的命題，我們可以得到下面關(guān)于輪子密鑰之間的關(guān)系。

4 13輪MIBS-80的多維零相關(guān)分析

本節(jié)主要利用上面構(gòu)造的8輪(3-10)零相關(guān)線性逼近，往前擴展2輪并且往后擴展3輪，結(jié)合輪子密鑰之間的關(guān)系和部分和技術(shù)，對13輪MIBS-80做多維零相關(guān)線性分析，如圖2所示。具體攻擊過程如下：

圖2 13輪MIBS-80的多維零相關(guān)分析

(14)以上過程中猜測了55 bit密鑰，然后窮舉并驗證其他25 bit密鑰。

5 11輪MIBS-80的積分分析

文獻[12]揭示了零相關(guān)線性逼近和積分區(qū)分器之間的關(guān)系，并且利用推導(dǎo)出的積分區(qū)分器對31輪Skipjack-BABABABA密碼算法做了積分分析。它們之間的數(shù)學(xué)聯(lián)系可以概括成下面的定理。

定理2[12]設(shè)，函數(shù)是上的向量布爾函數(shù)，并且,以及是正整數(shù)，則下面兩個條件等價。

若是隨機情況下，推論2出現(xiàn)的概率為

下面我們給出11輪MIBS-80的積分分析。見圖3，其中表示相應(yīng)的半字節(jié)跑遍所有狀態(tài)。具體攻擊過程如下。

圖3 11輪MIBS-80的積分分析

數(shù)器8 bit夠用。

6 結(jié)束語

本文主要評估了MIBS-80密碼算法關(guān)于多維零相關(guān)方法和積分攻擊方法的安全性。首先利用MIBS算法結(jié)構(gòu)的特點和密鑰擴展算法的特點，構(gòu)造出了一些合適的28個8輪零相關(guān)線性逼近和揭示了一些輪子密鑰之間的關(guān)系。結(jié)合部分和技術(shù)，我們對13輪的MIBS-80進行了多維零相關(guān)分析，結(jié)果顯示比窮舉具有bit的優(yōu)勢。另外，我們利用零相關(guān)線性逼近和積分區(qū)分器之間的關(guān)系，推導(dǎo)出一個積分區(qū)分器，并對11輪MIBS-80進行了積分攻擊，將積分攻擊的結(jié)果改進一輪。值得注意的是，本文選擇的零相關(guān)線性逼近是最優(yōu)的，這并不能保證轉(zhuǎn)化過來的積分區(qū)分器最優(yōu)，所以可能存在很好的積分區(qū)分器和更好的積分分析結(jié)果。另外，這兩個方法對MIBS-64同樣適用。單密鑰下的主要分析結(jié)果，見表1。盡管本文的兩個結(jié)果都沒有達到線性分析所能分析的18輪，但是它們從不同的角度反映密碼設(shè)計的某些特點，也給出一個理解零相關(guān)分析和積分分析之間聯(lián)系的例子。

表1 單密鑰MIBS-80的主要分析結(jié)果

注：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]. 山東大學(xué)學(xué)報(理學(xué)版), 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]. 山東大學(xué)學(xué)報(理學(xué)版), 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]. 小型微型計算機系統(tǒng), 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]. 計算機研究與發(fā)展, 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]. 通信學(xué)報, 2014, 35(7): 157-163.

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

[8] 劉超, 廖福成, 衛(wèi)宏儒. 對MIBS算法的中間相遇攻擊[J]. 內(nèi)蒙古大學(xué)學(xué)報(自然科學(xué)版), 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] 陳平, 廖福成, 衛(wèi)宏儒. 對輕量級MIBS算法的相關(guān)密鑰不可能差分攻擊[J]. 通信學(xué)報, 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年生，教授，研究方向為密碼學(xué)與信息安全.

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；網(wǎng)絡(luò)出版：2016-02-18

伊文壇 nlwt89@sina.com