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

1. 北京電子科技學(xué)院, 北京 100070

2. 密碼科學(xué)技術(shù)國家重點實驗室, 北京 100878

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

1 引言

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

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

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

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

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

2 預(yù)備知識

2.1 MIBS 算法簡介

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

圖1 MIBS 算法一輪加密結(jié)構(gòu)Figure 1 One round structure of MIBS

圖2 MIBS 算法輪函數(shù)結(jié)構(gòu)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 的密鑰編排相同的設(shè)計原則. 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 三子集中間相遇攻擊

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

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

圖3 三子集中間相遇結(jié)構(gòu)Figure 3 3-subset meet-in-the-middle structure attack

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

首先建立三子集中間相遇結(jié)構(gòu).

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

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

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

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

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

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

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

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

3.2 剪切-拼接技術(shù)

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

圖4 剪切–拼接技術(shù)Figure 4 Splice-and-cut technique

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

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

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

對A0的每種猜測值:

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

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

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

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

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

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

4.1 MIBS-64 的密鑰性質(zhì)

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

引理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]可由主密鑰相應(yīng)比特查詢S 盒得到;第1、2 輪共實際使用密鑰32+15=47比特; 第10、11 輪另存在7 比特額外密鑰.

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

表1 輪密鑰之間的關(guān)系Table 1 Relationship between round keys

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

4.2 MIBS 算法的一種等價結(jié)構(gòu)

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

圖5 4 輪MIBS 及其等價結(jié)構(gòu)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é)中對三子集中間相遇攻擊和剪切–拼接技術(shù)的介紹, 選取H1為第10、11 輪密鑰,H2為第1、2 輪密鑰,G為第7 輪至第9 輪密鑰, 即可將實際密鑰空間劃分為3 個子集合A0、A1和A2, 劃分方式如下:

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

圖6 基于MIBS 的8 輪等價結(jié)構(gòu)Figure 6 8-round equivalent structure based on MIBS

A0有252種可能, 假設(shè)第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′, 具體推導(dǎo)過程如表2 所示, 其中將4 bit 視為一個塊, 對于正向(反向) 而言, 0 代表不受A2(A1) 的影響, 1 代表受到A2(A1) 的影響, 可以看到僅第5 輪右支輸入的第5 個塊輸入不受影響?yīng)毩⒚荑€A2、A1影響. 對v′與u′均不受獨立密鑰影響的4 個比特值進行匹配, 若4 個比特值不完全相同, 則認(rèn)為是錯誤密鑰, 篩選概率為2-4.

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

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

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

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

4.4 11 輪MIBS-64 的復(fù)雜度分析

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

5 結(jié)束語

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

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