改進(jìn)的減輪MIBS-80密碼的中間相遇攻擊

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

(戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450001)

1 引言

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

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

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

Dunkelman等人[16]在亞密會(huì)(ASIACRYPT)2010年分析高級(jí)加密標(biāo)準(zhǔn)(Advanced Encryption Standard， AES)時(shí)，引入多重集并利用有效的差分枚舉手段，大大降低了中間相遇攻擊預(yù)計(jì)算階段涉及的參數(shù)數(shù)量。此外還發(fā)現(xiàn)存儲(chǔ)差分篩選集合的有效方法，降低了存儲(chǔ)復(fù)雜度?？偟膩?lái)說(shuō)，文獻(xiàn)[16]對(duì)AES中間相遇攻擊的思想具有里程碑式的進(jìn)步。2013年歐密會(huì)，Derbez等人[17]在Dunkelman基礎(chǔ)上，借鑒“rebound-like”思想，證明了文獻(xiàn)[16]預(yù)計(jì)算階段滿足截?cái)嗖罘致窂降亩嘀丶瘏?shù)不會(huì)全部取遍，進(jìn)而再次降低了區(qū)分器涉及的參數(shù)，給出了7輪AES-128和8輪AES-192中間相遇攻擊的最好結(jié)果。隨后，文獻(xiàn)[18]利用有效的密鑰橋和差分枚舉技術(shù)，給出了對(duì)10輪AES-256的中間相遇攻擊，是目前為止針對(duì)AES-256攻擊輪數(shù)最長(zhǎng)的單密鑰攻擊。近年來(lái)，隨著自動(dòng)化搜索技術(shù)的發(fā)展，文獻(xiàn)[19，20]給出了中間相遇攻擊一般化的搜索模型，可以快速有效地給出典型結(jié)構(gòu)分組密碼最優(yōu)中間相遇區(qū)分器。

本文主要研究了針對(duì)MIBS密碼的中間相遇攻擊，首先利用MIBS算法Feistel結(jié)構(gòu)的特點(diǎn)，構(gòu)造了8輪多重集，多重集的相關(guān)位置比特由28個(gè)半字節(jié)決定，超過(guò)窮舉的計(jì)算復(fù)雜度。接著通過(guò)研究MIBS算法S盒和截?cái)嗖罘值男再|(zhì)，利用有效的枚舉技術(shù)，剔除中間重復(fù)計(jì)算的變量，將預(yù)計(jì)算的參數(shù)由28個(gè)減少到15個(gè)，降低預(yù)計(jì)算復(fù)雜度，構(gòu)造了8輪中間相遇區(qū)分器。最后給出MIBS算法差分傳遞的性質(zhì)，結(jié)合輪密鑰與主密鑰的關(guān)系，首次實(shí)現(xiàn)了13輪MIBS-80算法的中間相遇攻擊，需要的數(shù)據(jù)復(fù)雜度為253個(gè)選擇明文，時(shí)間復(fù)雜度為262次13輪加密運(yùn)算。此外，利用8輪中間相遇區(qū)分器，結(jié)合MIBS算法的部分差分傳遞性質(zhì)，攻擊了12輪MIBS-80算法，所需時(shí)間復(fù)雜度為253.2次12輪加密運(yùn)算。表1列出了針對(duì)MIBS-80算法單密鑰攻擊的主要結(jié)果。

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

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

2 MIBS密碼算法

2.1 MIBS加密算法

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

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

設(shè)80 bit的主密鑰K=(k79，k78，...，k0)， state0是初始密鑰K，s tatei表示第i輪的密鑰擴(kuò)展?fàn)顟B(tài)，statei[a～b] 表 示s tatei從 高 比 特a到 低 比 特b的a-b+1bit。則由主密鑰生成32個(gè)32 bit的輪子密鑰Ki(1≤i ≤32)的具體過(guò)程為

3 MIBS密碼算法8輪中間相遇區(qū)分器

本節(jié)首先針對(duì)MIBS中間狀態(tài)的半字節(jié)運(yùn)算，給出MIBS算法δ-集的定義，再按照其Feistel結(jié)構(gòu)特點(diǎn)構(gòu)造多重集得到定理1，其相關(guān)位置比特由28個(gè)半字節(jié)決定，超過(guò)了窮舉的計(jì)算復(fù)雜度。接著研究MIBS算法S盒的性質(zhì)，利用有效的差分枚舉技術(shù)得出定理2，構(gòu)造了有效的8輪中間相遇區(qū)分器。

圖1 第i輪符號(hào)說(shuō)明示意圖

圖2 8輪MIBS算法的截?cái)嗖罘致窂?/p>

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

本節(jié)利用第3節(jié)構(gòu)造的8輪中間相遇區(qū)分器，前面加2輪，后面加3輪，構(gòu)成13輪的攻擊路徑，如圖3所示。為了減少?gòu)?fù)雜度，首先利用MIBS算法的差分傳遞特征，分別從加密方向和解密方向給出性質(zhì)2和性質(zhì)3，篩選滿足截?cái)嗖罘值拿魑?；接著利用MIBS-80密鑰擴(kuò)展算法中輪密鑰與主密鑰的關(guān)系，減少密鑰的猜測(cè)量。

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

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

4.1 預(yù)計(jì)算階段

4.2 在線階段

4.3 復(fù)雜度分析

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

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

6 結(jié)束語(yǔ)

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