改進的減輪MIBS-80密碼的中間相遇攻擊

任炯炯 侯澤洲 李曼曼 林東東 陳少真

(戰略支援部隊信息工程大學 鄭州 450001)

1 引言

隨著物聯網新技術的突破式發展，萬物聯網的需求使得無線傳感器、智能卡和射頻識別(Radio Frequency IDentification， RFID)標簽等受限設備的應用越來越廣泛。輕量級分組密碼廣泛應用于這類資源受限環境下的數據安全和隱私保護，成為密碼學研究的熱點。MIBS密碼算法是Izadi等人[1]在2009年提出的一個整體采用Feistel型，輪函數為代換置換網絡(Substitution-Permutation Network，SPN)型結構的輕量級分組密碼。其分組長度為64 bit，密鑰長度有64 bit和80 bit兩種，迭代輪數均為32輪。由于MIBS算法涉及的運算便于硬件實現，占用資源少，MIBS算法廣泛適用于物聯網和傳感器網絡等環境，對MIBS密碼的分析已備受關注。

對MIBS密碼的安全性分析主要集中在傳統的差分與線性分析、不可能差分攻擊、積分攻擊、相關密鑰攻擊和故障分析等。楊林等人[2]首先以0.99的成功概率給出了13輪MIBS差分分析的結果。Bay等人[3]對MIBS抗差分和線性攻擊的能力進行了新的評估。但是，杜承航等人[4]發現文獻[3]不可能差分分析的錯誤并重新給出了12輪不可能差分分析的結果。文獻[5]首次利用積分攻擊分析了8輪MIBS-64和9輪MIBS-80，隨后文獻[6，7]給出了10輪MIBS-80積分攻擊的結果。劉超等人[8]利用MIBS算法Feistel結構的等價性，構造出6輪中間相遇區分器，并結合輪子密鑰與主密鑰的關系，首次給出11輪MIBS-80算法的中間相遇攻擊。付立仕等人[9]基于MIBS-80中S盒不可能差分和密鑰間的制約關系篩選明文對，并利用獨立的80-bit輪密鑰來恢復主密鑰，對13輪MIBS-80進行了不可能差分分析。文獻[10，11]從側信道的角度，分別對MIBS密碼進行故障分析和旁路立方攻擊。

中間相遇攻擊是一種時空折中的攻擊方法，首先由Diffie等人[12]在1977年分析雙重DES(TWO-DES)時提出，廣泛應用于很多主流分組密碼的分析[13–15]。其主要思想是將密碼算法分解成兩部分，首先建立選擇明文經過前半部分加密對應的篩選集合，接著猜測相關的密鑰，正向加密和逆向解密明密文對的若干字節和比特，判斷是否構成中間數據的碰撞，進而形成有效的攻擊。中間相遇攻擊需要大量的預計算和時間復雜度，雖然預計算只需要計算1次，但如果涉及的猜測密鑰太多，就會超過窮舉復雜度。因此如何減少預計算的參數個數，減少需要猜測的密鑰量，降低時間復雜度，是亟需解決的問題。

Dunkelman等人[16]在亞密會(ASIACRYPT)2010年分析高級加密標準(Advanced Encryption Standard， AES)時，引入多重集并利用有效的差分枚舉手段，大大降低了中間相遇攻擊預計算階段涉及的參數數量。此外還發現存儲差分篩選集合的有效方法，降低了存儲復雜度。總的來說，文獻[16]對AES中間相遇攻擊的思想具有里程碑式的進步。2013年歐密會，Derbez等人[17]在Dunkelman基礎上，借鑒“rebound-like”思想，證明了文獻[16]預計算階段滿足截斷差分路徑的多重集參數不會全部取遍，進而再次降低了區分器涉及的參數，給出了7輪AES-128和8輪AES-192中間相遇攻擊的最好結果。隨后，文獻[18]利用有效的密鑰橋和差分枚舉技術，給出了對10輪AES-256的中間相遇攻擊，是目前為止針對AES-256攻擊輪數最長的單密鑰攻擊。近年來，隨著自動化搜索技術的發展，文獻[19，20]給出了中間相遇攻擊一般化的搜索模型，可以快速有效地給出典型結構分組密碼最優中間相遇區分器。

本文主要研究了針對MIBS密碼的中間相遇攻擊，首先利用MIBS算法Feistel結構的特點，構造了8輪多重集，多重集的相關位置比特由28個半字節決定，超過窮舉的計算復雜度。接著通過研究MIBS算法S盒和截斷差分的性質，利用有效的枚舉技術，剔除中間重復計算的變量，將預計算的參數由28個減少到15個，降低預計算復雜度，構造了8輪中間相遇區分器。最后給出MIBS算法差分傳遞的性質，結合輪密鑰與主密鑰的關系，首次實現了13輪MIBS-80算法的中間相遇攻擊，需要的數據復雜度為253個選擇明文，時間復雜度為262次13輪加密運算。此外，利用8輪中間相遇區分器，結合MIBS算法的部分差分傳遞性質，攻擊了12輪MIBS-80算法，所需時間復雜度為253.2次12輪加密運算。表1列出了針對MIBS-80算法單密鑰攻擊的主要結果。

表1 MIBS-80算法單密鑰攻擊結果比較

本文的結構安排如下：第2節簡要介紹MIBS密碼算法；第3節給出2個定理，構造8輪中間相遇區分器；第4節給出差分傳遞和密鑰擴展算法的相關性質，具體描述13輪MIBS-80密碼中間相遇攻擊的過程；第5節利用第3節和第4節的部分結果，簡要介紹12輪MIBS-80密碼中間相遇攻擊的結果；第6節總結全文。

2 MIBS密碼算法

2.1 MIBS加密算法

分組密碼MIBS算法[1]是Feistel結構的密碼體制，分組長度為64 bit，支持的密鑰長度有64 bit和80 bit兩種，加密輪數均為32輪。MIBS中間狀態的操作以4 bit為1個單位，稱為半字節。輪函數F函數為SPN型，包括密鑰加、S盒變換以及線性P置換。

2.2 MIBS-80算法的密鑰生成算法

設80 bit的主密鑰K=(k79，k78，...，k0)， state0是初始密鑰K，s tatei表示第i輪的密鑰擴展狀態，statei[a～b] 表 示s tatei從 高 比 特a到 低 比 特b的a-b+1bit。則由主密鑰生成32個32 bit的輪子密鑰Ki(1≤i ≤32)的具體過程為

3 MIBS密碼算法8輪中間相遇區分器

本節首先針對MIBS中間狀態的半字節運算，給出MIBS算法δ-集的定義，再按照其Feistel結構特點構造多重集得到定理1，其相關位置比特由28個半字節決定，超過了窮舉的計算復雜度。接著研究MIBS算法S盒的性質，利用有效的差分枚舉技術得出定理2，構造了有效的8輪中間相遇區分器。

圖1 第i輪符號說明示意圖

圖2 8輪MIBS算法的截斷差分路徑

4 13輪MIBS-80密碼算法的中間相遇攻擊

本節利用第3節構造的8輪中間相遇區分器，前面加2輪，后面加3輪，構成13輪的攻擊路徑，如圖3所示。為了減少復雜度，首先利用MIBS算法的差分傳遞特征，分別從加密方向和解密方向給出性質2和性質3，篩選滿足截斷差分的明文；接著利用MIBS-80密鑰擴展算法中輪密鑰與主密鑰的關系，減少密鑰的猜測量。

圖3 13輪MIBS-80密碼的中間相遇攻擊路徑

性質2 對MIBS算法，若第i+ 1輪輸入差分ΔAi=(0000000γ)， ΔBi=(00000000)， 則第i+3輪的輸出差分滿足關系式

4.1 預計算階段

4.2 在線階段

4.3 復雜度分析

5 12輪MIBS-80密碼算法的中間相遇攻擊

本節在第3節定理2的8輪中間相遇區分器基礎上，前面加1輪，后面加3輪，進行12輪MIBS-80算法的中間相遇攻擊，攻擊路徑去掉圖3中13輪路徑的第1輪。與第4節13輪的攻擊過程相比，其明文的差分特征不再滿足性質3，密文的差分特征依然滿足性質2。

6 結束語

本文評估了適用于物聯網的密碼MIBS算法抵抗中間相遇攻擊的安全性。與其他針對Feistel結構的密碼分析工作相比，本文充分利用MIBS算法的結構特點，構造8輪多重集。進一步，利用MIBS算法S盒的性質和有效的差分枚舉技術，減少了8輪中間相遇區分器的參數，從而首次實現了對12輪和13輪MIBS-80密碼的中間相遇攻擊。攻擊過程利用差分傳遞的性質篩選明文對，利用輪密鑰與主密鑰的關系，減少了密鑰猜測量，降低了時間復雜度。該攻擊方法明顯優于文獻[8]中間相遇攻擊的結果。與其他攻擊方法相比，在時間復雜度和選擇明文量上也有整體優勢。本文的攻擊思想同樣適用于其他Feistel-SP結構的典型密碼算法的分析，如 Camellia，E2算法等。如何結合自動化搜索算法構造較長輪數的區分器，并加大密鑰篩選的力度將是下一步值得研究的工作。