輕量級密碼算法MIBS的零相關和積分分析

伊文壇 魯林真 陳少真

?

輕量級密碼算法MIBS的零相關和積分分析

伊文壇*魯林真 陳少真

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

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

分組密碼；MIBS；零相關分析；積分攻擊

1 引言

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

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

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

本文利用零相關線性分析和積分分析方法評估MIBS-80密碼算法的安全性。根據線性層的特點，構造了一些8輪MIBS密碼算法的零相關線性逼近；利用多維零相關線性分析方法，結合密鑰擴展算法的特點和部分和技術，對13輪的MIBS-80密碼算法做安全性分析；利用零相關區分器和積分區分器之間的聯系，推導出一些8輪的積分區分器；進一步，作為應用，對11輪的MIBS-80密碼算法進行積分分析。

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

2 預備知識

2.1 一些記號

2.2 MIBS算法介紹

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

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

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

2.3 多維零相關分析方法和積分分析介紹

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

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

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

3 MIBS密碼8輪零相關線性逼近和密鑰擴展算法的一些性質

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

3.1 MIBS算法8輪零相關線性逼近

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

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

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

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

圖1 MIBS算法8輪零相關線性逼近

3.2 MIBS-80密鑰擴展算法的一些性質

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

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

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

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

4 13輪MIBS-80的多維零相關分析

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

圖2 13輪MIBS-80的多維零相關分析

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

5 11輪MIBS-80的積分分析

文獻[12]揭示了零相關線性逼近和積分區分器之間的關系，并且利用推導出的積分區分器對31輪Skipjack-BABABABA密碼算法做了積分分析。它們之間的數學聯系可以概括成下面的定理。

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

若是隨機情況下，推論2出現的概率為

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

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

數器8 bit夠用。

6 結束語

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

表1 單密鑰MIBS-80的主要分析結果

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

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

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

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；網絡出版：2016-02-18

伊文壇 nlwt89@sina.com