MIBS 分組密碼的改進積分攻擊

毛永霞 吳文玲 張 麗

（中國科學(xué)院軟件研究所 北京 100190）

（中國科學(xué)院大學(xué) 北京 100049）（yongxia2018@iscas.ac.cn）

近20 年來，伴隨著物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，資源受限設(shè)備如低成本的RFID（radio frequency identification）標簽、無線傳感器、嵌入式系統(tǒng)等的應(yīng)用越來越廣泛.為資源受限設(shè)備研制低成本、低能耗的輕量級密碼算法是一項具有挑戰(zhàn)性的工作，吸引了許多密碼學(xué)者的關(guān)注.例如，Leander 等人[1]設(shè)計了DES（data encryption standard）加密算法的一個輕量級變體DESL；Poschmann 等人[2]設(shè)計了一個比DESL 更強的DES 的變體DESXL；Bogdanov 等人[3]提出了著名的輕量級密碼算法PRESENT；Banik 等人[4]設(shè)計了比PRESENT 更安全、高效的輕量級密碼算法GIFT.

MIBS 是一個適用于資源受限環(huán)境的輕量級分組密碼算法，由Izadi 等人[5]在CANS 2009 會議上提出.針對MIBS 分組密碼算法的現(xiàn)有分析結(jié)果包括差分分析[6]、線性分析[6]、積分分析、不可能差分分析[7]等.目前對于MIBS-64 最好的分析結(jié)果是14 輪的差分分析，成功概率為50.15%；對MIBS-80 最好的分析結(jié)果是18 輪的線性分析，成功概率為72.14%.

積分分析是由Knudsen 等人[8]在FSE 2002 上提出來的，由于它的思想原型首先被應(yīng)用于分組密碼Square[9]，因此也被稱為Square 攻擊.積分分析是當(dāng)前評估分組密碼算法安全性的基礎(chǔ)分析方法之一，已經(jīng)在許多分組密碼算法上得到了較好的攻擊結(jié)果，例如AES[10], PRESENT[11]等.可分性是積分分析的推廣，在EUROCRYPT 2015 上被Todo[12]提出.Todo 結(jié)合密碼算法非線性部件的代數(shù)次數(shù)，優(yōu)化了積分性質(zhì)，使得積分特征能夠用一種更精確的方式推導(dǎo).一個顯著的應(yīng)用是第一次在理論上對全輪的MISTY1進行了積分攻擊[13].在ASIACRYPT 2016 上，Xiang 等人[14]將基于混合整數(shù)線性規(guī)劃（mixed integer linear programming, MILP）建模的方法引入基于比特的可分性，進一步提高了積分區(qū)分器可自動化搜索的密碼算法的規(guī)模.2017 年，Todo 等人[15]對上述MILP 模型進行了補充，并將其應(yīng)用于多個流密碼算法的立方攻擊，得到了多個流密碼當(dāng)時最好的密鑰恢復(fù)攻擊.近幾年，對分組密碼算法的積分區(qū)分器搜索的改進主要圍繞改進非線性層[16-19]和線性層[19-24]的模型進行.

目前，對MIBS 算法的積分分析已經(jīng)存在一些結(jié)論.2013 年，于曉麗等人[25]基于一個5 輪的積分區(qū)分器，利用高階積分技術(shù)將該區(qū)分器向前擴展3 輪，分別對MIBS-64 和MIBS-80 進行了8, 9, 10 輪的積分攻擊.2014 年，潘志舒等人[26]構(gòu)造了MIBS 的5 輪積分區(qū)分器，利用Feistel 結(jié)構(gòu)的等價結(jié)構(gòu)以及MIBS 密鑰編排算法中主密鑰和輪密鑰的關(guān)系，給出10 輪MIBS 算法的積分攻擊.2016 年，伊文壇等人[27]利用零相關(guān)線性逼近和積分區(qū)分器之間的聯(lián)系，推導(dǎo)出MIBS 的8 輪積分區(qū)分器，進而對11 輪的MIBS-80 進行了攻擊.2021 年，李艷俊等人[28]基于5 輪的積分區(qū)分器，向前、向后各擴展3 輪，給出了一個11 輪MIBS-64 的積分攻擊.

部分和（partial sum technique）技術(shù)是Ferguson 等人[10]在分析Rijndael 時提出的一種降低攻擊復(fù)雜度的方法，是改進積分攻擊的有效方法.該方法主要利用積分攻擊需要對中間狀態(tài)進行求和的特點，通過壓縮密鑰恢復(fù)過程中的數(shù)據(jù)量來有效減少計算時間，例如，將對6 輪Rijndael 的密鑰恢復(fù)時間復(fù)雜度從272降低為 249[10].

本文研究MIBS-64 和MIBS-80 的積分分析，主要貢獻有4 個方面：

1） 針對密鑰編排算法，利用密鑰搭橋技術(shù)，得到了輪密鑰之間的一些相關(guān)性質(zhì)；

2） 構(gòu)造了MIBS 的8 輪和9 輪積分區(qū)分器；

3） 對于MIBS-64，基于8 輪的積分區(qū)分器，在區(qū)分器末尾增加4 輪，給出了12 輪的密鑰恢復(fù)攻擊；

4） 對于MIBS-80，基于9 輪積分區(qū)分器，在末尾增加5 輪，給出了14 輪的密鑰恢復(fù)攻擊.

3）和4）這2 個攻擊是目前對MIBS-64 和MIBS-80 已知的最好的積分攻擊，與已有積分攻擊結(jié)果的對比如表1 所示.

Table 1 The Integral Attack Results on MIBS表1 對MIBS 的積分攻擊結(jié)果

1 預(yù)備知識

1.1 符號說明

C[i:j]: 密文的第j比 特 到 第i比特；

Xt,[i:j]: 第t輪中間狀態(tài)的第j比特到第i比特；

Xti: 第t輪中間狀態(tài)的第i個半字節(jié)；

skt,[i:j]: 第t輪密鑰的第j比特到第i比特；

skit: 第t輪密鑰的第i個半字節(jié)；

state[i:j]: 中間狀態(tài)的第j比特至第i比特；

S/St: S 盒函數(shù)/第t個S 盒函數(shù)；

a/c: 一個活躍比特/常數(shù)比特；

A / C: 一個活躍半字節(jié)/常數(shù)半字節(jié)；

B / U: 一個平衡半字節(jié)/未知半字節(jié)；

＞＞＞: 右循環(huán)移位操作；

||: 字符串的連接操作；

? 函數(shù)的復(fù)合符號.

1.2 MIBS 加密算法簡介

分組密碼MIBS 整體采用Feistel 結(jié)構(gòu)，輪函數(shù)使用SP 結(jié)構(gòu)，其分組長度64 b，MIBS 支持64 b 和80 b這2 種密鑰長度，分別記為MIBS-64 和MIBS-80，迭代輪數(shù)為32 輪.MIBS 中所有的運算都是基于半字節(jié)的.

設(shè)MIBS 的輪函數(shù)為F，第i輪的輪密鑰為Ki，輸入 為 (Xi,Xi-1)， 那 么 輸 出 為 (Xi+1,Xi)， 其 中Xi+1=F(Xi,Ki)⊕Xi-1.輪函數(shù)F由異或子密鑰層AK、S 盒層（4×4的S 盒）和線性變換P組成，記為F=P?S?AK，具體如圖1 所示.

Fig.1 Round function of MIBS圖1 MIBS 的輪函數(shù)

設(shè)線性變換P:(F42)8→(F42)8的 輸入為y=(y7,y6,y5,y4,y3,y2,y1,y0)， 輸出為y′=(y′7,y′6,y′5,y′4,y′3,y′2,y′1,y′0)，那么

1.3 MIBS 密鑰編排算法簡介

MIBS 的密鑰編排采用了與PRESENT 的密鑰編排相同的設(shè)計原則.

1）MIBS-64 的密鑰編排算法

設(shè)MK64是 長度為64 b 的主密鑰，記為MK64=(k63,k62,…,k0).設(shè)密鑰編排算法第i輪的中間狀態(tài)為statei.由主密鑰生成長度為32 b 的輪密鑰Ki（ 1 ≤i≤32）的過程為：

其中RC表示輪計數(shù)，第i輪 狀態(tài)statei的左32 b 作為第i輪的輪密鑰.

2）MIBS-80 的密鑰編排算法

設(shè)MK80是 長度為80 b 的主密鑰，記為MK80=(k80,k79,…,k0).設(shè)密鑰編排算法第i輪的中間狀態(tài)為statei.由主密鑰生成長度為32 b 的輪密鑰Ki（ 1 ≤i≤32）的過程為：

其中第i輪狀態(tài)statei的左32 b作為第i輪的輪密鑰.

1.4 密鑰搭橋技術(shù)

密鑰搭橋技術(shù)最早是在文獻[29]中針對AES-192 提出的.該技術(shù)的主要作用是根據(jù)密鑰編排算法，推導(dǎo)出某些輪密鑰之間存在的依賴關(guān)系，即：從某些輪密鑰字節(jié)中計算出其他的輪密鑰字節(jié)，即使這些字節(jié)距離很多的擴散步驟.在FSE 2016 上，Lin 等人[30]提出了一個高效的比特迭代型密鑰搭橋自動搜索算法，這個算法可以改進幾乎所有對分組密碼攻擊的復(fù)雜度.

比特迭代型密鑰搭橋自動搜索算法的輸入為一個表示密鑰編排算法的方程系統(tǒng)和一個想要找到其中變量關(guān)系的密鑰變量集合 K0，輸出是密鑰變量集合 K0中存在的密鑰橋，具體過程可以劃分為2 個階段：

1）知識傳播階段，主要利用Gauss-Jordan 消元法處理方程系統(tǒng)的系數(shù)矩陣；

2）關(guān)系導(dǎo)出階段，根據(jù)1）處理之后矩陣的秩，導(dǎo)出密鑰間的線性關(guān)系，即密鑰橋.

2 MIBS 的密鑰編排性質(zhì)和積分區(qū)分器

2.1 MIBS 密鑰編排的相關(guān)性質(zhì)

針對MIBS-64 和MIBS-80 的密鑰編排算法，利用文獻[30]的密鑰搭橋技術(shù)搜索輪密鑰之間可能存在的相關(guān)關(guān)系，即密鑰橋.算法1 描述了這一過程.設(shè)K表示MIBS 密鑰編排算法的所有中間密鑰變量的集合， K0表示MIBS-64 第9～12 輪的部分輪密鑰集合和MIBS-80 第10～14 輪的部分輪 密 鑰 集 合， K1表 示K0可 以擴張到的集合， S表示S 盒的輸入輸出比特變量集合，Mkey表 示由密鑰編排算法生成的密鑰方程系統(tǒng)E的系數(shù)矩陣.矩陣中變量的順序為(K-S-K1,S,K1,c)， 其 中 K-S-K1表 示 S 和 K1在 K 中的 補 集，c表示常數(shù)的列.G(Mkey)表示利用Gauss-Jordan 消元法將Mkey變 為對角矩陣；Gn(Mkey)表示利用Gauss-Jordan消元法將Mkey的 前n列變?yōu)閷蔷仃?算法1 的目標是找到 K0間潛在的關(guān)系式.

算法1.MIBS 輪密鑰關(guān)系搜索算法.

輸入：輪數(shù)r、種子密鑰K、待測試密鑰集 K0；

輸出：密鑰橋集合R.

①Generate_key_equation（r,K,sk）：/*生成種子密鑰K與輪密鑰sk之間的具體關(guān)系式，忽略常數(shù)加操作*/

② foriin range （ 0 ,r） do

③E(K,sk)←key_schedule（i,ski）；/*ski是第i輪密鑰，sk0=K，E是關(guān)于K和sk的密鑰方程系統(tǒng)*/

④ end for

⑤ returnE(K,sk).

⑥ functionPropagation（ K,K0,S,Mkey）：/*知識傳播階段，擴展 K0到所有可表出的密鑰*/

⑦M←GK-K1-S(M)；/*M表示 K-K1-S對應(yīng)的系數(shù)矩陣*/

⑧ forrowinMkeydo

⑨ if 在前 | K-K1-S|行 有1 個row屬 于casethen

⑩ 移動x,S(x) ,或者x與S(x)所對應(yīng)的列；

? ( K1,S)←(K1,S)∪{x}({S(x)},{x,S(x)})；/*添加新變量*/

? end if

? end for

? return K1,Mkey.

? functionDerivation（ K0, K1,A）：/*關(guān)系導(dǎo)出階段，對系數(shù)矩陣Mkey中 變量 K1對應(yīng)的分塊矩陣A進行處理*/

?A←GK1-K0-S(A)；

? forrowinB1do /*B1為 矩陣A中 變量 S對應(yīng)的分塊矩陣*/

? ifRank(B1)≥4-Nthen/*N為 S 中元素在K0中出現(xiàn)的個數(shù)*/

? 向A中 增加與φ和x+φ′相應(yīng)的新行和新列；

? ifRank(B1)＞4-Nthen

? 向A中 增加與ψ 和 ψ′相應(yīng)的新行和新列；

? end if

? end if

? end for

?A←GK1-K0-S(A)；

? forrowinB2do /*B2是 矩 陣A中 變 量 K0對應(yīng)的分塊矩陣*/

?R←導(dǎo)出所有密鑰橋；

? end for

? returnR.

行⑨case={case1,case2}，其中：

case1=(0,…,0,ex,0,…,0,eS(x),0,…,0,e|K-K1-S|,…,en)；

case2={(0,…,0,et,ex,0,…,0,e|K-K1-S|,…,en),(0,…,0,es,eS(x),0,…,0,e′|K-K1-S|,…,e′n),t≠s,et=es=0,ej=c·e′j,j=|K-K1-S|,…,n-1}.

行?的 φ 為 S 中剩余的 8-Rank(B1)-N個變量，φ′是關(guān)于 φ的線性組合.

行?的 ψ 為 S 中剩余的Rank(B1)-4+N個變量，ψ′是關(guān)于 ψ的線性組合，它們用于表示可以由S擴展得到的密鑰比特.

利用算法1，搜索到了MIBS-64 和MIBS-80 的密鑰編排的相關(guān)性質(zhì)——性質(zhì)1 和性質(zhì)2.此外，我們也通過密鑰編排算法推導(dǎo)驗證了性質(zhì)1 和性質(zhì)2.

性質(zhì)1.根據(jù)MIBS-64 的密鑰編排算法，第11 輪的密鑰sk11,[31:17]可 由第12 輪密鑰sk12,[16:02]得到；第10輪密鑰sk10,[31:30]可 由第12 輪密鑰sk12,[01:00]得到；第10輪密鑰sk10,[31:15]可 由第11 輪密鑰sk11,[16:00]得到；第9 輪的輪密鑰sk9,[12:00]可 由第12 輪輪密鑰sk12,[31:19]得到，第9 輪的輪密鑰sk9,[31:15]可 由第10 輪的輪密鑰sk10,[16:00]得到.

性質(zhì)2.根據(jù)MIBS-80 的密鑰編排算法，第13 輪的輪密鑰sk13,[31:19]可 由第14 輪的輪密鑰sk14,[12:00]得到；第12 輪密鑰sk12,[31:19]可 由第13 輪的輪密鑰sk13,[12:00]得到；第11 輪的密鑰sk11,[31:19]可 由第12 輪密鑰sk12,[12:00]得 到；第11 輪 的 密 鑰sk11,[08:00]可 由 第14 輪 密 鑰sk14,[31:23]得 到；第10 輪 密 鑰sk10,[31:19]可 由 第11 輪 密 鑰sk11,[12:00]得 到；第10 輪 密 鑰sk10,[27:00]可 由 第14 輪 密 鑰sk14,[31:04]得到.

文獻[26]提出了一個關(guān)于MIBS-64 的輪密鑰和主密鑰之間關(guān)系的性質(zhì).與密鑰搭橋技術(shù)考慮所有輪密鑰之間的具體關(guān)系式不同，文獻[26]通過密鑰編排算法的循環(huán)移位操作來判斷輪密鑰可能涉及的所有主密鑰位置.例如，考慮性質(zhì)1 的密鑰橋sk12,[16:02]→-sk11,[31:17].根據(jù)文獻[26]，猜測sk12,[16:02]需 要猜 測 主 密 鑰K[39:20]， 猜 測sk11,[31:17]需 要 猜 測 主 密 鑰K[36:21]， 因 此 輪 密 鑰sk12,[16:02]與sk11,[31:17]之 間 似 乎 并 不能互相獨立推導(dǎo)得出.事實上，根據(jù)密鑰編排算法寫出它們之間的表達式，發(fā)現(xiàn)二者是可以互相推導(dǎo)的，而這恰好是密鑰搭橋技術(shù)的思想.密鑰搭橋技術(shù)通過處理輪密鑰之間的具體關(guān)系式，精準地判斷出所有潛在的密鑰橋.

文獻[26]也提出了MIBS-80 的輪密鑰和主密鑰之間關(guān)系的性質(zhì).類似地，考慮密鑰橋sk14,[12:00]→-sk13,[31:19].那么，根據(jù)文獻[26]，猜測sk14,[12:00]需要猜測主密鑰K[79:74,09:00]， 猜測sk13,[31:19]需要猜測主密鑰K[79:71,06:00].因 此sk14,[12:00]和sk13,[31:19]似 乎 不 能 完 全 互相推導(dǎo)得出.事實上，根據(jù)輪密鑰之間的關(guān)系式，sk14,[12:00]和sk13,[31:19]也 是 可 以 互相推導(dǎo)出的.

2.2 MIBS 的積分區(qū)分器

目前，MIBS 最長的積分區(qū)分器為5 輪，都是基于加密算法的結(jié)構(gòu)特點推導(dǎo)求得的[25,28].結(jié)合文獻[14,31]的基于比特自動化建模方法，分別對線性變換和S盒生成約束條件，建立MIBS 的MILP 模型，搜索更長的積分區(qū)分器.具體過程為：首先，對MIBS 加密算法的每一個基本操作建模；然后，生成MIBS 的r輪可分性傳播的線性不等式系統(tǒng)；接著，給定輸入和輸出可分性；最后，利用求解器求解r輪可分性傳播系統(tǒng).

MIBS 的加密算法僅包含S 盒、線性變換P、異或操作、置換操作.對于S 盒，利用文獻[31]的方法，使用Quine-Mclusky 方法建立約束條件.首先，求出S盒的所有可分跡，然后利用Logic Friday 軟件生成約束這些可分跡的合取范式，最后將合取范式轉(zhuǎn)換為線性不等式（具體約束如附錄A 所示）.

對于置換操作，僅需要改變變量的位置即可.對于異或操作b=a0⊕a1，使用的建模規(guī)則為：

另外，還需使用復(fù)制操作b→(a0,a1)，使用的建模規(guī)則為：

線性層中異或操作和復(fù)制操作的建模比較簡單，只需根據(jù)建模規(guī)則，直接代入狀態(tài)變量即可.對于線性變換P，對應(yīng)的基于半字節(jié)的矩陣在附錄B 中給出.根據(jù)此矩陣和異或操作、復(fù)制操作的建模規(guī)則，可以直接寫出其對應(yīng)的基于比特的約束不等式（具體參考附錄B）.

按照式（1）（2）的建模方式迭代r次，MIBS 的r輪可分性傳播的線性不等式系統(tǒng)即可生成.然后，挑選僅有幾比特為常數(shù).其余比特全活躍的輸入狀態(tài)，確定輸入可分性，并且將輸出對應(yīng)的變量寫成目標函數(shù)，添加到不等式系統(tǒng)中，完成對MILP 模型的建模過程.最后，通過求解不等式系統(tǒng)判斷積分區(qū)分器的存在性.

根據(jù)上面的自動化建模搜索方法，可以構(gòu)造MIBS 的8 輪積分區(qū)分器：從明文集的最高32 比特選擇4 比特為常數(shù)，其余比特都活躍，那么經(jīng)過8 輪MIBS 加密之后，輸出的最低32 比特都是平衡的.例如，當(dāng)明文的最高4 比特為常數(shù)時，對應(yīng)的輸入和輸出可分性表示

當(dāng)選擇的明文集只有1 個比特為常數(shù)時，可以構(gòu)造9輪積分區(qū)分器，具體如定理1 所示.

定理1.選擇明文集X，滿足最高32 比特中的任一比特為常數(shù)，其余比特都為活躍比特，即對于一個固定的i∈{0,1,…,31}，xi=c；對于任意j≠i，xj=a.那么，該明文集經(jīng)過9 輪MIBS 加密之后，輸出的最低32 比特都是平衡的，即輸出值的求和有形式為：

設(shè)每一輪的輸入可分性 D=D[63:32]||D[31:00], 表2展示了當(dāng)最高比特為常數(shù)時，9 輪積分區(qū)分器每一輪中間狀態(tài)對應(yīng)的可分性.

Table 2 Division Property of Intermediate States for the 9-Round Integral Distinguisher of MIBS表2 MIBS 9 輪積分區(qū)分器中間狀態(tài)的可分性

3 12 輪MIBS-64 的密鑰恢復(fù)攻擊

本節(jié)利用2.2 節(jié)中MIBS 的8 輪積分區(qū)分器：最高4 位是常數(shù)，其余位均活躍，8 輪之后輸出的最低32 位是平衡的，在區(qū)分器末尾增加4 輪，完成了對12 輪MIBS-64 的密鑰恢復(fù)攻擊，如圖2 所示.

Fig.2 Key recovery attack of MIBS-64圖2 MIBS-64 的密鑰恢復(fù)攻擊

3.1 攻擊過程

整個密鑰恢復(fù)過程分為6 步，具體攻擊步驟為：

Step1.選 擇 明 文 集X=X1||X0，X共 260個 明 文，滿足明文的第1 個半字節(jié)為常數(shù)，其余半字節(jié)都是活躍的，查詢其12 輪MIBS-64 加密之后的密文C=C[63:32]||C[31:00].

Step2.已知密文C，猜測第12 輪的密鑰sk12,[31:00]，解密計算X11=P?S(C[63:32]⊕sk12) ⊕C[31:00].

Step3.已知密文和X11，猜測第11 輪的輪密鑰sk11,[31:00]， 計算X10=P?S(X11⊕sk11)⊕C[63:32].根據(jù)性質(zhì)1，部分密鑰可以根據(jù)12 輪的輪密鑰直接得到，因此實際只需猜測15 b，即sk11,[14:00].

Step4.已 知X11和X10，猜 測 第10 輪 的 輪 密 鑰sk10,[31:00]， 計 算X9=P?S(X10⊕sk10)⊕X11.根 據(jù) 性 質(zhì)1，部分密鑰可以根據(jù)第12,11 輪的輪密鑰直接得到，因此實際只需猜測15b，即sk10,[14:00].

Step5.已知X10和X9， 猜測第9 輪的輪密鑰sk9,[31:00]，計算X8=P?S(X9⊕sk9)⊕X10.根據(jù)性質(zhì)1，部分密鑰可以根據(jù)第12,11,10 輪的輪密鑰直接得到，因此實際只需猜測15b，即sk9,[14:00].

Step6.根 據(jù)2.2 節(jié)，X經(jīng)8 輪MIBS 加 密 之 后 的低32 比特都是平衡比特.因此，滿足Xi,8=0 的密鑰可能為正確密鑰.篩選概率為 2-32，共得到232+15+15+15×2-32=245個候選密鑰.

3.2 利用密鑰搭橋與部分和技術(shù)降低復(fù)雜度

3.1 節(jié)的攻擊過程已經(jīng)根據(jù)密鑰橋調(diào)整了需要猜測的密鑰個數(shù)，下面介紹利用部分和技術(shù)降低復(fù)雜度.

對于Step2，利用部分和技術(shù)，逐個計算X11中每半字節(jié)的值.由于S(C[63:32]⊕sk12)=S7(C[63:60]⊕sk12,[31:28])||…||S0(C[35:32]⊕sk12,[03:00])， 根據(jù)線性變換P，有式（3）～（10）成立：

2）根據(jù)式（4）計算X111.由于在1）中已經(jīng)猜測了，因此這里只需再猜測和的值.通過猜測的密鑰，統(tǒng)計X111的所有可能值出現(xiàn)次數(shù)的奇偶性.

3）以此類推，根據(jù)猜測的密鑰和式（5）～（10），計算X11其他半字節(jié)的值.

對于Step3，只需要猜測sk11,[14:00].與Step2 類似，首先猜測，計算接著猜測，sk11,[14:12]， 計算X10每個半字節(jié)的值.

Step4, Step5 的過程與Step3 類似.圖2 也展示了第9輪利用部分和與密鑰搭橋技術(shù)恢復(fù)X80的過程，即與X9′之 間 的 虛 線 表示：為了計算X80，從第10 輪X9中選取部分狀態(tài)， 即參與計算.

3.3 復(fù)雜度分析

3.1 節(jié)的攻擊過程的時間復(fù)雜度主要來自于Step2～5.

Step2 的時間復(fù)雜度約為 260×28+260×24×6次S盒查表；Step3 的時間復(fù)雜度約為260×28+260×24×1.75次S 盒查表；Step4 和Step5 的時間復(fù)雜度都為260×28+260×24×1.75次 S 盒查表.因此總的時間復(fù)雜度為260×28×4/（12×8）≈263.42次12 輪MIBS-64 解密計算.數(shù)據(jù)復(fù)雜度為 260的選擇明文.

4 14 輪MIBS-80 的密鑰恢復(fù)攻擊

利用2.2 節(jié)中MIBS 的任意一個9 輪積分區(qū)分器，在末尾增加5 輪，都能完成一個對14 輪MIBS-80 的密鑰恢復(fù)攻擊.本節(jié)以MIBS 所示的一個區(qū)分器為例，介紹詳細的攻擊過程如圖3 所示.

Fig.3 Key recovery attack of MIBS-80圖3 MIBS-80 的密鑰恢復(fù)攻擊

4.1 攻擊過程

Step1.選擇明文集X，X中共有 263個明文，滿足明文的第1 個比特為常數(shù)，其余比特都是活躍的，查詢其14 輪MIBS-80 加密之后的密文C=C[63:32]||C[31:00].

Step2.已知密文C，猜測第14 輪的密鑰sk14，解密計算X13=P?S(C[63:32]⊕sk14)⊕C[31:00].

Step3.猜測第13 輪的輪密鑰sk13， 解密計算X12=P?S(X13⊕sk13)⊕X14.根據(jù)性質(zhì)2，部分密鑰比特可以根據(jù)sk14,[12:00]直接得到，因此實際只需猜測19 b，即sk13,[18:00].

Step4.猜 測 第12 輪 的 輪 密 鑰sk12，解 密 計 算X11=P?S(X12⊕sk12)⊕X13.根據(jù)性質(zhì)2，部分密鑰可以根據(jù)sk13,[12:00]直接得到，因此實際只需猜測19 b，即sk12,[18:00].

Step5.猜 測 第11 輪 的 輪 密 鑰sk11，解 密 計 算X10=P?S(X11⊕sk11)⊕X12.根據(jù)性質(zhì)2，部分密鑰可以根據(jù)13,12 輪的輪密鑰得到，實際上只需要猜測10 b，即sk11,[18:09].

Step6.根 據(jù) 性 質(zhì)2，sk10可 由sk11,[12:00]和sk14,[31:04]得到，解密計算X9=P?S(X10⊕sk10)⊕X11.

Step7.根據(jù)定理1，X經(jīng)9 輪MIBS 加密之后的低32 比特都是平衡比特.因此，滿足Xi,9=0的密鑰可能為正確密鑰.篩選概率為 2-32，共得到232+19+19+10×2-32=248個候選密鑰.

4.2 利用密鑰搭橋與部分和技術(shù)降低復(fù)雜度

4.1 節(jié)中的攻擊過程已經(jīng)根據(jù)密鑰橋調(diào)整了需要猜測的密鑰個數(shù)，下面介紹利用部分和技術(shù)降低復(fù)雜度.

對于Step2，利用部分和技術(shù)，逐個計算X13每半字節(jié)的值.根據(jù)線性變換P，有式（11）（12）成立：

1）根據(jù)式（11），計算X103.首先猜測sk104和sk114的值，由于密文已知，解密計算S0(C[031:00]⊕sk014)⊕S1(C[131:00]⊕sk114)出 現(xiàn)的次數(shù)；接著猜測sk134，計算第0, 1, 3 個S 盒的求和值出現(xiàn)的次數(shù)；以此類推，依次猜測sk414，sk164，sk174， 最終計算得到X103每個可能值出現(xiàn)次數(shù)的奇偶性.

2）根據(jù)式（12），計算X113.由于在1）中已經(jīng)猜測了，因此這里只需再猜測sk124和sk154的值.通過猜測的密鑰，統(tǒng)計X113每個可能值出現(xiàn)次數(shù)的奇偶性.

3）類似于1）和2），根據(jù)猜測的密鑰及線性變換P計算X13其他半字節(jié)的值.

Step3～6 的過程與Step2 類似，區(qū)別在于需要猜測的密鑰長度小于32 b.

4.3 復(fù)雜度分析

4.1 節(jié)中的攻擊過程的時間復(fù)雜度主要來自于Step2～5.Step2 的時間復(fù)雜度約為263×28+263×24×6次S 盒查表，Step3 和Step4 的時間復(fù)雜度都為263×28+263×24×2.75次S 盒查表，Step5 的時間復(fù)雜度約為263×27+263×24×0.75次S 盒查表，因此總的時間約為 263×28×3.5/14×8 ≈266次14 輪的MIBS-80 解密計算，數(shù)據(jù)復(fù)雜度為 263的選擇明文.

5 總 結(jié)

本文對分組密碼算法MIBS 進行了積分分析.對于MIBS-64，在8 輪積分區(qū)分器的末尾增加4 輪進行了12 輪MIBS-64 的密鑰恢復(fù)攻擊；對于MIBS-80，在9 輪積分區(qū)分器的末尾增加5 輪進行了14 輪MIBS-80 的密鑰恢復(fù)攻擊.在MIBS 的密鑰恢復(fù)過程中，我們利用密鑰搭橋技術(shù)與部分和技術(shù)，有效地降低了時間復(fù)雜度.MIBS 的密鑰編排算法比較簡單，例如，MIBS-64 的2 輪實際上只用了47 b 互不相關(guān)的輪密鑰.因此，利用密鑰搭橋技術(shù)可以極大降低猜測的密鑰量.由此可見，輪密鑰之間的關(guān)系對算法的安全性具有重要的影響.

作者貢獻聲明：毛永霞提出實驗方案并撰寫論文；吳文玲提出指導(dǎo)意見并修改論文；張麗負責(zé)修改論文.

附錄A.S 盒的線性約束條件.

設(shè)(a,b,c,d)→(e,f,g,h)表示S 盒的一條可分跡，那么下面的24 個不等式可以充分描述可分性在MIBS 的S 盒上的傳播：

附錄B.線性變換 P的線性約束條件.

MIBS 的線性變換P對應(yīng)的矩陣M為

根據(jù)矩陣M，以及復(fù)制和異或的建模規(guī)則，可以直接寫出比特級線性約束條件.以第1 行和第1 列為例.設(shè)線性變換P的輸入可分性 (ai+28,ai+24,ai+20,ai+16,ai+12,ai+8,ai+4,ai)， 0 ≤i≤3， 輸出可分性(bi+28,bi+24,bi+20,bi+16,bi+12,bi+8,bi+4,bi)， 0 ≤i≤3.

遍歷i, 0 ≤i≤3， 得到線性變換P最高4 比特輸入所對應(yīng)復(fù)制操作的約束條件.同理，遍歷所有列，可得到線性變換P所有輸入位置對應(yīng)復(fù)制操作的約束條件.

遍歷i, 0 ≤i≤3， 得到線性變換P最高4 比特輸出所對應(yīng)異或操作的約束條件.同理，遍歷所有行，可得到線性變換P所有輸出位置對應(yīng)異或操作的約束條件.