改進的MIBS-64 算法積分分析研究*

李艷俊, 孫啟龍, 歐海文, 汪 振

1. 北京電子科技學院, 北京100070

2. 密碼科學技術國家重點實驗室, 北京100878

1 引言

近年來, 為滿足RFID (radio frequency identification)、智能卡、無線傳感器等資源受限環境下的安全需求, 輕量級密碼隨之誕生, 而后倍受關注. 許多密碼學者提出一系列輕量分組密碼算法, 如PRESENT[1]、LED[2]、LBlock[3]、PRINT-cipher[4]、KLEIN[5]和SIMON[6]等.

MIBS[7]是一個輕量級分組密碼算法, 由Izadi M 等人在CANS 2009 會議上提出. 針對MIBS 分組密碼算法的現有分析結果包括線性分析[8]、積分分析[9]、差分分析[8]和不可能差分分析[10]等. 目前對于MIBS-64 最好的分析結果是14 輪差分分析[8], 數據復雜度為240個選擇明文, 數據復雜度為237.2, 成功概率為50.15%; 對于MIBS-80 最好的分析結果是18 輪線性分析[8], 數據復雜度為260.98個已知明文,時間復雜度為276.13, 成功概率為72.14%. 雖然差分分析和線性分析的輪數較高, 但是成功率相對積分分析偏低.

積分分析是由Square 攻擊發展而來的, Square 攻擊[11]是對AES 最有效的攻擊之一. 近年來, 積分分析廣泛發展,已經應用于很多密碼算法,如Rijndael[12]、ARIA[13]、Serpent[14]、AES[15]、Simeck[16]、TWINE[17]、Camellia[18,19]等. 2016 年, 隨著可分性自動化搜索工具的逐漸成熟[20,21], 積分分析又一次占據了分析方法的主導位置. 于曉麗等人都對MIBS 算法進行了10 輪積分分析[9,22]. 本文基于MIBS-64 算法的密鑰編排特點, 給出一類5 輪積分區分器, 并前向和向后分別擴展3 輪, 首次對MIBS-64 算法進行了11 輪的積分攻擊, 攻擊數據復雜度為258, 時間復雜度為259.75次11 輪加密, 攻擊成功概率為100%.

2 預備知識

2.1 MIBS 算法簡介

MIBS 算法整體結構使用傳統的Feistel 結構[1], 輪函數采用SPN 結構, 其分組長度為64 比特, 支持64 和80 比特的密鑰長度, 分別記為MIBS-64 和MIBS-80, 迭代輪數為32 輪. MIBS 中所有迭代操作都是基于半字節的, 也就是一個字有4 比特. 輪函數包括異或子密鑰,S盒(4×4 比特) 層和一個線性層P(分支數為5), 此處線性層是設計文檔中線性混淆和半字節置換的復合. MIBS 加密結構及輪函數結構見圖1 及圖2.

圖1 MIBS 算法一輪加密結構Figure 1 One round structure of MIBS

圖2 MIBS 算法輪函數結構Figure 2 Round function of MIBS

MIBS 的密鑰編排采用了與PRESENT 的密鑰編排相同的設計原則. MIBS-64 密鑰編排中, 通過64比特主密鑰K: (k63,k62,··· ,k0) 生成輪密鑰Ki, 其中0≤i ≤31. 若將密鑰編排算法中第i輪的密鑰狀態表示statei, 則密鑰編排算法的輪函數可以表示成如下的形式:

其中, ?表示循環右移操作, [i～j] 表示此項操作是針對第i至第j比特變量,|| 表示連接操作, 輪函數中使用的S盒與F函數中使用的S盒相同. 最終, 第i輪狀態statei的左側32 比特將作為第i輪輪密鑰Ki.

2.2 本文所使用的符號

現在我們介紹本文中使用的符號. 明文記為P= (X1,X0), 其中Xi= (xi,8,xi,7,··· ,xi,1),i=0,1,··· ,r ?1, 本文中出現的其他符號含義如下:

3 MIBS-64 的密鑰性質和積分區分器

MIBS-64 密鑰編排算法中使用了循環移位、S盒查詢、輪常數加等變換, 相鄰兩輪之間的32 比特密鑰有17 比特重復或等價, 基于這個性質可以對MIBS-64 進行多輪攻擊. 本節首先介紹MIBS-64 的密鑰性質, 然后提出MIBS 算法的一類5 輪積分區分器.

3.1 MIBS-64 的密鑰性質

根據MIBS-64 密鑰編排算法, 第1 輪至第11 輪之間的密鑰存在部分重復和等價關系, 本文主要使用下述密鑰編排性質.

本文根據我院醫療設備管理的現狀和要求，設計出一套適合醫院自身管理流程的醫療設備全生命周期管理系統，有效地提高了醫院的工作效率和經濟效益。該系統基本涵蓋了醫療設備管理的全過程，滿足我院醫學工程科對醫療設備管理的實際需求，提高了我院醫療設備信息化管理的整體水平。

3.2 一類5 輪積分區分器

基于輪密鑰之間的關系, 選取合適的5 輪積分區分器, 向前解密3 輪, 向后加密3 輪, 可以攻擊11 輪MIBS-64. 這類5 輪積分區分器需要具備以下特點:

(1) 選擇X0= (C,C,x0,6,x0,5,x0,4,x0,3,x0,2,x0,1), 其中x0,1～x0,6任意兩個活躍, 為不增加猜測多余密鑰的計算量x0,7～x0,8被設置為常量.

圖3 輪密鑰之間的關系Figure 3 Relationship between round keys

(2) 5 輪積分區分器輸出X6經過S盒后得到Y6= (y6,8,y6,7,y6,6,y6,5,y6,4,y6,3,u,u), 其中y6,8～y6,3共6 個半字節可能為平衡半字節, 為不增加猜測多余密鑰的計算量y6,2～y6,1被設置為未知的半字節u. 若存在i個半字節的每個值出現偶數次, 則猜測密鑰中錯誤密鑰通過的的概率小于2?12.68i[9,19].

根據上述特點, 通過搜索得表1 中13 個5 輪積分區分器.

下述引理2 將證明表1 中區分器1 的正確性, 引理3 將證明表1 中區分器5 中y6,3半字節平衡的正確性, 其余平衡半字節的證明方法相似, 從略. 根據密鑰編排特點, 為降低猜測多余密鑰的計算量, 上述區分器中的平衡字節y6,2和y6,1并不會被使用.

表1 MIBS-64 算法5 輪積分區分器Table 1 5 rounds integral distinguishers of MIBS-64

引理2 如果選擇明文結構為(X1,X0) = (CCCCCCCC,CCCCCCA2A1), 也就是x0,2,x0,1是活躍的半字節, (X1,X0) 的其余半字節都為常數, 記t1=P?1(X7)7⊕y6,7,t2=P?1(X7)8⊕y6,8, 則每個ti的值都會出現偶數次.

證明: 如圖4 所示, 根據Feistel 結構特點, 得到X7=X1⊕Z2⊕Z4⊕Z6, 在選擇明文攻擊中, 明文(X1,X0) 和密文(X7,X6) 已知, 故有:

圖4 MIBS 算法5 輪積分區分器Figure 4 5 round integral distinguisher of MIBS

根據方程(1)我們知道P?1(X7⊕X1)=Y2⊕Y4⊕Y6, 故P?1(X7)i ⊕P?1(X1)i=y2,i ⊕y4,i ⊕y6,i

所以t1=P?1(X7)7⊕y6,7=P?1(X1)7⊕y2,7⊕y4,7, 其中y2,7=S(x2,7⊕k2,7),x2,7=x0,7⊕z1,7,而x0,7,x1,7是常數, 故x2,7是常數, 由于P?1(x1)7也是常數, 故此t1的取值規律與y4,7的取值規律是相同的, 下面分析y4,7的取值規律:

考慮x4,7得:

令y=y2,1⊕y2,2, 對于y的每一個值,y2,2都是活躍的, 所以y4,7的每個值都出現16 次, 即滿足y4,7的每個值都出現偶數次.

同理, 可證t2的每個值也出現偶數次.

引理3 如果選擇明文結構為(X1,X0) = (CCCCCCCC,CCCA5A4CCC), 也就是x0,5,x0,4是活躍的半字節, (X1,X0) 的其余半字節都為常數, 記t3=P?1(X7)3⊕y6,3, 則t3的每個值出現偶數次.

證明: 前部推導過程與引理2 證明相似, 可得t3的取值規律與y4,3的取值規律是相同的, 下面分析y4,3的取值規律:

將x4,3帶入方程(5)得

與引理2 證明不同, 此處y4,3的表達式中同時出現了S(y2,5⊕c3) 和S(y2,4⊕c6). 令y=y2,4⊕y2,5, 則對于y的每一個值,y2,5是活躍的. 又

所以S(y2,5⊕c3)⊕S(y ⊕y2,5⊕c6) 的每個值出現偶數次, 因此結論成立.

4 MIBS 的11 輪積分攻擊

4.1 積分區分器選取

在針對11 輪的MIBS 攻擊中使用第3.2 節表1 中的5 輪積分區分器, 因為需要用t值過濾錯誤密鑰,t值的比特數越多, 錯誤密鑰被過濾掉的概率越大. 因此根據密鑰性質和5 輪區分器的平衡比特數量, 選用第8 個區分器進行下述恢復密鑰攻擊. 選擇x3,5,x3,2活躍, 具體過程如圖5 所示.

圖5 MIBS 算法11 輪攻擊Figure 5 Attack on 11 rounds MIBS

第4 輪至第8 輪為區分器, 輸入表示成(X4,X3), 滿足:

x3,5,x3,2活躍, 則y7,[8,7,6,4,3]每個值出現偶數次, 表達式為:

與引理類似, 有:

由此, 對于上述t1～t5每個值都出現偶數次, 即這5 個半字節位置t1||t2||t3||t4||t5的每個值出現偶數次. 對于隨機置換, 根據文獻[9] 和[19], 這20 個比特位置的值出現偶數次的概率小于2?12.68×5=2?63.40.

4.2 攻擊步驟

Step.1 定義如下由28個64 比特構成的一個結構, 可以表示成(X3,X2) 的形式, 并滿足:

4.3 復雜度分析

在11 輪恢復密鑰攻擊中, 共猜測主密鑰第63～32、21～0 共54 比特, 隨機密鑰通過5 輪積分區分器的概率為2?63.40,即只有1 個正確的54 比特密鑰被保留. Step.1—2 需要計算250×28×2.25÷11≈255.75次11 輪加密. Step.3 需要計算258次11 輪加密. Step.4 需要計算250×28×24×2.3÷11≈259.75次11 輪加密. Step.5 得到254×2?63.40+1≈1 個54 比特密鑰, 猜測剩余的10 比特密鑰, 只需要進行210次11 輪解密.

因此, 上述攻擊的整體時間復雜度由Step.4 決定, 共需時間復雜度259.75次11 輪加密, 數據復雜度為258.

5 結束語

本文對分組密碼算法MIBS-64 進行了積分分析, 基于密鑰編排算法構建一類5 輪積分區分器, 向前加3 輪, 向后加3 輪, 11 輪的密鑰恢復攻擊數據復雜度為258, 時間復雜度為259.75. 與差分分析、線性分析、截斷差分分析等方法相比, 雖然密鑰恢復的輪數較少, 但是這種攻擊方法成功的概率為100%, 在算法實際攻擊中具有重要意義. 本攻擊結果適用于MIBS-64, 類似地可以推廣至MIBS-80. 由此可見, 輪密鑰之間的關系對算法安全性有重要影響, 若能考慮這些關系對S盒的作用, 將會改進現有分析效果, 這也是我們下一步的工作.