MIBS-64 算法的三子集中間相遇攻擊*

許星霖, 李艷俊, 歐海文, 孫啟龍

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

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

3. 中國電子科技集團公司第十五研究所, 北京 100083

1 引言

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

MIBS[7]是由Izadi 等在CANS 2009 上提出一個輕量級分組密碼算法. 針對該算法的現(xiàn)有分析結果包括Bay 等提出的線性分析[8]和差分分析[8]、Liu 等提出的中間相遇攻擊[9]、Yu 等提出的積分分析[10]等. 目前對于MIBS-64 最好的分析結果是14 輪差分分析[8], 數(shù)據(jù)復雜度為240個選擇明文, 時間復雜度為237.2, 成功概率為50.15%; 對于MIBS-80 最好的分析結果是18 輪線性分析[8], 數(shù)據(jù)復雜度為260.98個已知明文, 時間復雜度為276.13, 成功概率為72.14%. 雖然差分分析和線性分析的輪數(shù)較高, 但是成功率相對中間相遇攻擊偏低.

中間相遇攻擊是1977 年Diffie 和Hellman 為分析DES 算法安全性提出的一種攻擊方法. 近年來,中間相遇攻擊廣泛發(fā)展, 已經應用于很多密碼算法, 如ARIA[11]、AES[12]、TWINE[13]、Camellia[14]等. 基于傳統(tǒng)的中間相遇攻擊, 產生了很多改進后的攻擊方法, 例如, 三子集中間相遇攻擊. 三子集中間相遇攻擊由Bogdanov 等[15]在輕量級分組密碼KTANTAN 的安全性分析中首次提出, 通過使用部分匹配技術和優(yōu)化密鑰子集合的選取, 增加了傳統(tǒng)中間相遇攻擊可分析的輪數(shù). 三子集中間相遇攻擊有效地拓寬了中間相遇攻擊在分組密碼安全性分析中的應用. 其他應用可參見Sasaki 等[16]對XTEA 算法的安全性分析. 目前, 三子集中間相遇攻擊有較為完備的自動化搜索方法, 例如Sasaki[17]在IWSEC 2018 上提出使用ILP 對GIFT 算法進行三子集中間相遇攻擊自動化搜索, Bao 等[18]在Eurocrypt 2021 上提出對AES-like 哈希的中間相遇原像攻擊的自動搜索, 2021 年Dong 等[19]提出著重于密鑰恢復和碰撞分析的中間相遇攻擊.

本文針對MIBS-64 算法的密鑰編排特點, 使用三子集技術、剪切–拼接技術和MIBS 的等價結構, 首次對MIBS-64 進行了11 輪的中間相遇攻擊, 數(shù)據(jù)復雜度為247, 存儲復雜度為24764-bit, 時間復雜度為262.25次11 輪加密.

本文結構如下: 第2 節(jié)簡單介紹MIBS 算法和所使用的符號. 第3 節(jié)介紹三子集中間相遇攻擊.第4 節(jié)給出MIBS-64 的密鑰編排性質、MIBS-64 的11 輪的攻擊與復雜度分析. 第5 節(jié)為結論及工作展望.

2 預備知識

2.1 MIBS 算法簡介

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

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

圖2 MIBS 算法輪函數(shù)結構Figure 2 Round function of MIBS

在攻擊中, 線性層P很重要, 令(y1,y2,··· ,y8) 為線性層P的輸入, 則輸出(y′1,y′2,··· ,y′8) 可以如下表示:

令(y1,y2,··· ,y8) 為線性層P的輸出, 則輸入(y′1,y′2,··· ,y′8) 線性層P的逆P-1可以如下表示:

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

2.2 符號說明

首先說明本文中使用的符號. 明文記為P= (X1,X0), 其中Xi= (x8,x7,··· ,x1),i= 0,1, 其中xj(j=1,2,··· ,8) 為4 bit 的半字節(jié), 本文中出現(xiàn)的其他符號含義如下:

3 三子集中間相遇攻擊簡介

3.1 三子集中間相遇攻擊

三子集中間相遇攻擊是中間相遇攻擊的一種改進方法, 通過放寬選取密鑰子集合的嚴格要求, 使得攻擊的應用范圍變廣. 與傳統(tǒng)中間相遇攻擊將密鑰空間劃分為2 個完全獨立的子密鑰集合不同, 三子集中間相遇攻擊將密鑰空間劃分為3 個子密鑰集合.

如圖3 所示, 令密鑰長度為l,K=kl-1···k1k0為初始密鑰. 定義K1={ki|應用于φ1,α的密鑰比特集合},K2={ki| 應用于φR-β+1,R的密鑰比特集合},A0=K1∩K2為加密過程中φ1,α與φR-β+1,R共有的密鑰比特集合, 則A1=K1K1∩K2與A2=K2K1∩K2為僅在φ1,α與φR-β+1,R中使用的密鑰比特集合, 并有K=K1∪K2.

圖3 三子集中間相遇結構Figure 3 3-subset meet-in-the-middle structure attack

三子集中間相遇攻擊的過程包括2 個步驟: 首先建立三子集中間相遇結構, 并利用該結構過濾部分錯誤密鑰, 減小密鑰空間; 然后通過進一步的密鑰篩選尋找正確密鑰[20].

首先建立三子集中間相遇結構.

(P,C) 為一個明密文對, 猜測A0中密鑰的所有可能值.

(1) 猜測A1中密鑰的所有可能值, 計算v=φ1,α(P), 將其結果存入表中;

(2) 猜測A2中密鑰的所有可能值, 計算u=(C);

(3) 確定進行中間匹配的輪數(shù), 對v與u分別進行加密與解密運算, 得到匹配輪數(shù)處對應的加密結果v′與解密結果u′的m(1≤m ≤b) 個比特, 并對m個比特值進行匹配, 若m個比特值不完全相同, 則認為是錯誤密鑰. 該步對密鑰的篩選概率為2-m, 即經過該步篩選后剩余密鑰數(shù)為2l-m. 該步的計算復雜度為2|A0|(2|A1|+2|A2|).

接下來, 進一步對剩余所有密鑰進行篩選.

窮舉搜索剩余的所有密鑰候選值, 利用明密文對(P,C) 計算中間匹配輪數(shù)處v′與u′的值, 并對其全部b比特值進行匹配, 若b比特值不完全相同, 則認為是錯誤密鑰. 一次匹配可刪除2b個錯誤密鑰. 對剩余的2l-m-b個可能密鑰候選值重復該過程, 直到得出唯一的正確密鑰.

該步的計算復雜度為2l-m+2l-m-b+2l-m-2b+···.

完整三子集中間相遇攻擊的計算復雜度為2|A0|(2|A1|+2|A2|)+(2l-m+2l-m-b+2l-m-2b+···).

3.2 剪切-拼接技術

剪切–拼接技術(splice-and-cut technique) 是Aoki 和Sasaki[21]在對SHA-0 和SHA-1 進行中間相遇攻擊時提出的. 剪切–拼接技術可以使得進行中間相遇攻擊時不再局限于以明文或密文為起點, 此時可以隨機選取某一輪的中間狀態(tài), 如果這個中間狀態(tài)選擇在前端的時候, 需要猜測中間狀態(tài)解密到明文的所有所需密鑰, 從而解密得到相應的明文, 進而通過加密機得到密文, 然后進行中間相遇攻擊. 同理, 中間狀態(tài)選擇尾端時, 也要猜測中間狀態(tài)加密到密文的所有所需密鑰, 從而加密得到相應的密文, 進而通過解密機得到明文, 然后進行中間相遇攻擊. 在使用剪切–拼接技術時, 需要建立明文–密文對的索引表, 以便在攻擊中可以找到密文對應的明文, 將整個過程連接起來. 剪切–拼接中間相遇攻擊結構如圖4 所示.

圖4 剪切–拼接技術Figure 4 Splice-and-cut technique

剪切–拼接技術通過建立明文和密文之間的查找表(LOOKUP 表) 將明密文連接起來, 通過猜測某一輪的中間狀態(tài)h,猜測從h加密到密文C中所需的密鑰H1,從h加密得到密文C,得到密文C之后,可以通過LOOKUP 表查找得到相對應的明文P, 猜測密鑰H2, 對明文P進行加密, 得到v; 猜測從h解密到中間狀態(tài)u中所需的密鑰G,從h解密得到中間狀態(tài)u,對于中間相遇攻擊則有H2(LOOKUP(H1(h)))=G-1(h).

定義K1={ki|應用于H1與H2的密鑰比特集合},K2={ki|應用于G的密鑰比特集合},A0=K1∩K2,A1=K1K1∩K2,A2=K2K1∩K2, 并有K=K1∪K2.

剪切–拼接三子集中間相遇攻擊的步驟如下[22]:

對A0的每種猜測值:

(1) 猜測A1中密鑰的所有可能值, 計算v=H2(LOOKUP(H1(h))), 將其結果存入表T1中;

(2) 猜測A2中密鑰的所有可能值, 計算u=G-1(h);

(3) 確定進行中間匹配的輪數(shù), 對v與u分別進行加密與解密運算, 得到匹配輪數(shù)處對應的加密結果v′與解密結果u′的m(1≤m ≤b) 個比特, 并對m個比特值進行匹配, 若m個比特值不完全相同, 則認為是錯誤密鑰. 該步對密鑰的篩選概率為2-m, 即經過該步篩選后剩余密鑰數(shù)為2l-m, 再進一步對剩余所有密鑰進行篩選.

剪切–拼接三子集中間相遇攻擊的數(shù)據(jù)復雜度為H1中猜測密鑰的個數(shù), 存儲復雜度為LOOKUP 表與表T1之和. 普通的中間相遇攻擊僅僅需要知道明密文對即可, 而剪切–拼接三子集中間相遇攻擊則為選擇明密文攻擊.

4 MIBS 的三子集中間相遇攻擊

MIBS-64 密鑰編排算法中使用了循環(huán)移位、S 盒查詢、輪常數(shù)加等變換, 相鄰兩輪之間的32 比特密鑰有17 比特重復或等價, 基于這個性質可以對MIBS-64 進行多輪攻擊. 本節(jié)將首先介紹MIBS-64 的密鑰性質.

4.1 MIBS-64 的密鑰性質

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

引理1 根據(jù)MIBS-64 密鑰編排算法,k11,[10,9,8,7]可由k2,[3,2,1,0]查S 盒得到, 同理,k11,[32,31],k11,[30,29,28,27],k11,[26,25,24,23]可由主密鑰相應比特查詢S 盒得到;第1、2 輪共實際使用密鑰32+15=47比特; 第10、11 輪另存在7 比特額外密鑰.

證明: 根據(jù)密鑰編排算法state1經過循環(huán)右移15 bit、S 盒和異或輪常量即可得到state2, 考慮到S 盒以及異或輪常量不會引入未知量, 則可以通過上述性質詳細刻畫state1與state2之間的關系. 因為Ki=, 則可以通過state1與state2之間的關系得出K1與K2之間的關系. 迭代上述過程即可得到K1:K11之間的密鑰相關性, 具體性質如表1 所示.

表1 輪密鑰之間的關系Table 1 Relationship between round keys

三子集中間相遇攻擊利用MIBS 一些密鑰比特在連續(xù)的多輪加密過程中未被使用的特點. 所以為了建立MIBS 的三子集中間相遇結構, 首先推導各輪加密使用的輪密鑰. 根據(jù)MIBS 密鑰生成策略得到的各輪輪密鑰的使用情況如圖表1 所示. 可以看出, MIBS 中第1、2 輪密鑰與第10、11 輪密鑰存在較多重復比特.

4.2 MIBS 算法的一種等價結構

文獻[23] 利用線性變換的性質給出了輪函數(shù)為SPN 結構的Feistel 密碼的3 個等價結構, 利用不同結構對算法實施攻擊時可以得到不同的改進效果. 同樣地, 記MIBS 算法加密過程中輪密鑰加操作為K,非線性代替變換為S, 線性變換為T, 則四輪MIBS 算法的加密結構可描述為圖5 中的左圖. 根據(jù)MIBS算法加密結構中線性變換的性質, 可以相應地給出四輪MIBS 的一個等價加密結構為圖5 中的右圖[9].

圖5 4 輪MIBS 及其等價結構Figure 5 4-round MIBS and its equivalent structure

4.3 11 輪MIBS-64 的三子集中間相遇攻擊

觀察MIBS-64 各輪輪密鑰可有如下發(fā)現(xiàn).

從第1、2、10、11 輪的輪密鑰涉及的密鑰比特集合為{k0,k1,··· ,k21,k32,··· ,k63}, 未使用實際密鑰的集合為{k22,k23,··· ,k31}. 從第7 輪至第9 輪的輪密鑰涉及的密鑰比特集合為{k0,k1,··· ,k55,k58,··· ,k63}, 未使用實際密鑰的集合為{k56,k57}.

根據(jù)第3 節(jié)中對三子集中間相遇攻擊和剪切–拼接技術的介紹, 選取H1為第10、11 輪密鑰,H2為第1、2 輪密鑰,G為第7 輪至第9 輪密鑰, 即可將實際密鑰空間劃分為3 個子集合A0、A1和A2, 劃分方式如下:

利用這些參數(shù)和圖6 的MIBS 算法8 輪的等價加密結構即可得到11 輪MIBS-64 的三子集中間相遇結構, 并對密鑰進行初步篩選. 具體過程如下:

圖6 基于MIBS 的8 輪等價結構Figure 6 8-round equivalent structure based on MIBS

A0有252種可能, 假設第10 輪的輸入數(shù)據(jù)為h:

(1) 猜測A1中密鑰的所有22種可能值, 計算v=φ1,2°LOOKUP°φ10,11(h), 將v存儲進表T1;

(2) 猜測A2中密鑰的所有210種可能值, 計算u=(h);

(3) 選擇第5 輪輸入為中間匹配輪數(shù), 得到第5 輪輸入處的v′與u′, 具體推導過程如表2 所示, 其中將4 bit 視為一個塊, 對于正向(反向) 而言, 0 代表不受A2(A1) 的影響, 1 代表受到A2(A1) 的影響, 可以看到僅第5 輪右支輸入的第5 個塊輸入不受影響獨立密鑰A2、A1影響. 對v′與u′均不受獨立密鑰影響的4 個比特值進行匹配, 若4 個比特值不完全相同, 則認為是錯誤密鑰, 篩選概率為2-4.

表2 中間匹配過程Table 2 Intermediate matching process

該步的計算復雜度為252(22+210)=262.

接下來, 窮舉搜索剩余2l-m= 260個密鑰候選值, 利用明密文對(P,C) 重新計算v′與u′的值, 并對其64 bit 值進行匹配, 若64 bit 值不完全相同, 則認為是錯誤密鑰, 該步的篩選概率為2-64. 重復該步驟, 直到得到滿足v′=u′的唯一正確密鑰.

該步的計算復雜度為2l-m+2l-m-b+2l-m-2b+···=260+2-4+···≈260. 觀察該式可發(fā)現(xiàn), 對MIBS-64 只需要一步篩選即可期待淘汰所有錯誤密鑰, 得到唯一的正確密鑰.

4.4 11 輪MIBS-64 的復雜度分析

根據(jù)第3 節(jié)中對三子集中間相遇攻擊復雜度計算的結果, 恢復11 輪MIBS-64 實際全部64 bit 密鑰信息的計算復雜度為2|A0|(2|A1|+2|A2|)+(2l-m+2l-m-b+2l-m-2b+···)=252(22+210)+260+2-4≈262.25, 數(shù)據(jù)復雜度為247, 存儲復雜度為24764-bit.

5 結束語

本文對分組密碼算法MIBS-64 進行了三子集中間相遇攻擊, 11 輪的密鑰恢復攻擊數(shù)據(jù)復雜度為247,時間復雜度為262.25, 存儲復雜度為24764-bit. 表3 給出了一些針對MIBS-64 的攻擊結果, 同現(xiàn)有的攻擊成功率為100% 的密碼分析方法相比, 使用三子集中間相遇攻擊增加了攻擊輪數(shù), 且具有較低的數(shù)據(jù)復雜度. 本攻擊結果適用于MIBS-64, 類似地可以推廣至MIBS-80. 由分析結果可見, 輪密鑰之間的關系對算法安全性有重要影響. 若能使用自動化搜索工具, 則可能搜索出更優(yōu)的密鑰子集合的劃分, 從而改進現(xiàn)有分析效果, 這也是我們下一步的工作.

表3 MIBS-64 算法的攻擊結果比較Table 3 Comparison of attacked results of MIBS-64