分組密碼TWIS的三子集中間相遇攻擊

鄭雅菲，衛宏儒

(北京科技大學 數理學院，北京 100083)

1 引言

TWIS是由Ojha等人于2009年提出的輕量級分組密碼算法[1]，設計思想基于 CLEFIA[2]，采用廣義Feistel結構，設計者稱其分組長度與密鑰長度均為128 bit，加密輪數為10輪。算法的設計文章未給出任何密鑰恢復攻擊。Su Bozhan等人首先對其進行了安全性分析，通過構造10輪差分區分器，給出全10輪TWIS不抵抗差分分析的結論[3]。隨后，Onur Kocak 與Nese Oztop給出了TWIS安全性的進一步研究，差分分析全10輪的TWIS，恢復12 bit末輪輪密鑰的計算復雜度為221；構造了9.5輪的不可能差分區分器與線性區分器；指出 TWIS的實際密鑰長度僅為62 bit，而不是設計者宣稱的128 bit[4]。

中間相遇攻擊(meet-in-the-middle attack)由Diffie與Hellman于1977年針對DES的安全性提出[5]。其基本思想為尋找輪數盡可能長的獨立密鑰，對已知明密文對分別進行加密與解密操作，再選定中間變量進行匹配，篩選正確密鑰。中間相遇攻擊對算法結構、密鑰生成策略有較嚴格的要求，具有數據復雜度極低的優點。中間相遇攻擊目前已應用于DES、AES、Keeloq等分組密碼算法的安全性分析中，詳細過程與結果可參見文獻[6～10]。

基于傳統的中間相遇攻擊，產生了很多改進后的攻擊方法，例如，三子集中間相遇攻擊。三子集中間相遇攻擊由Andrey Bogdanov等人在輕量級分組密碼KTANTAN[11]的安全性分析中首次提出，通過改進密鑰子集合的選取與部分匹配技術的應用，增加了傳統中間相遇攻擊可分析的輪數。將三子集中間相遇攻擊應用于全輪KTANTAN32、KTANTAN48，攻擊的數據復雜度分別為3/2個明密文對，計算復雜度分別為275.044/275.584[12]。三子集中間相遇攻擊有效地拓寬了中間相遇攻擊在分組密碼安全性分析中的應用。其他應用可參見Gautham Sekar等人對XTEA算法的安全性分析[13]。

本文通過研究分組密碼TWIS輪密鑰生成的缺陷，對忽略后期白化過程的全10輪TWIS應用三子集中間相遇攻擊。恢復實際全部62 bit密鑰信息的計算復雜度為245，數據復雜度僅為一個已知明密文對，攻擊結果表示TWIS算法不抵抗三子集中間相遇攻擊。本文的計算復雜度與數據復雜度均優于TWIS現有的安全性分析結果。

2 分組密碼TWIS介紹

2.1 符號說明

A(l)：A的長度為l bit。

＜＜＜ i：左循環移位i bit。

＞＞＞j：右循環移位j bit。

A⊕B：A和B按比特取異或和。

A∧B：A和B按比特取與。

|A|：集合A中的元素個數。

φi,j：第i輪到第j輪的加密過程。

2.2 分組密碼TWIS

TWIS是輕量級分組密碼，其分組長度與密鑰長度均為128 bit，算法結構為2-分支的廣義Feistel結構，迭代輪數為10，每輪的輪密鑰長度為32 bit。令 P(128)=(P0,P1,P2,P3)表示128 bit明文輸入，C(128)=(C0,C1,C2,C3)表示128 bit密文輸出，RKi(i=0,1,…,10)表示輪密鑰，則TWIS的加密過程如下

其中，輪函數G的輸入為3個32 bit的分組，包括2個32 bit分支及一個32 bit輪密鑰，輸出為2個32 bit的分組。

F函數實現算法的密鑰混合，本文攻擊不涉及其具體計算，故不進行詳細介紹，可參見文獻[1]。

TWIS算法通過密鑰生成策略由128 bit的初始密鑰K得到11個32 bit的輪密鑰 RKi(i=0,1,…,10)，其中RK0與RK1為初始白化密鑰，RK2與RK3為最后的白化密鑰。

各輪輪密鑰的具體生成過程為

其中，S與F函數中用到的S盒相同，M為混淆矩陣。

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

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

如圖1所示，令l為密鑰長度，K=k0k1…kl-1表示初始密鑰。定義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。

圖1 三子集中間相遇結構

當R-β+1=α時，三子集中間相遇攻擊等價于中間相遇攻擊。

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

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

1)猜測A1中密鑰的所有可能值，計算v=φ1，α(P)；

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

該步的計算復雜度為

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

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

該步的計算復雜度為

羅譯：...since he is almost of the same age and as erudite as another man...[6]64

綜上所述，完整三子集中間相遇攻擊的計算復雜度可表示為

在對密鑰子集合的劃分中，只要|A1|+|A2|＞2，即可得到優于窮舉搜索的計算復雜度。

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

TWIS算法的設計者稱其密鑰長度為128 bit，但是觀察其密鑰生成策略可以發現，每輪變換循環移位僅3 bit，值改變的量僅為24 bit。這使得初始密鑰的混淆速度非常慢。經過推導可發現其實際密鑰長度僅為62 bit，且忽略后期白化后，算法首尾兩端可找到較長輪數的獨立密鑰。

本文攻擊利用該特點，通過推測各輪的輪密鑰，對忽略后期白化過程的全10輪TWIS應用三子集中間相遇攻擊。

表1 TWIS各輪輪密鑰

4.1 輪密鑰推導

三子集中間相遇攻擊利用TWIS一些密鑰比特在連續的多輪加密過程中未被使用的特點。所以為了建立TWIS的三子集中間相遇結構，首先推導各輪加密使用的輪密鑰。根據TWIS密鑰生成策略得到的各輪輪密鑰的使用情況如表1所示。

觀察各輪輪密鑰的使用情況可以發現，雖然TWIS的設計者稱其密鑰長度為128 bit，但實際有效的密鑰長度僅為62 bit，即在輪密鑰生成過程中，僅使用了初始密鑰的{k0,k1,…,k32,k99,k100,…,k127}這62 bit，而其他66 bit無效。這使得對TWIS的窮舉搜索復雜度由 2128降為262。記實際密鑰空間為K′={k0,k1,…,k32,k99,k100,…,k127}。

4.2 10輪TWIS的三子集中間相遇攻擊

在TWIS實際密鑰長度l=62的基礎上應用三子集中間相遇攻擊，使得復雜度進一步降低。

考慮初始白化密鑰，忽略后期白化密鑰，觀察各輪輪密鑰可有如下發現。

從第0輪至第4輪的輪密鑰涉及的密鑰比特集合為{k0,k1,…,k14,k99,k100,…,k127}，未使用實際密鑰的18個比特集合為{k15,k16,…,k31,k32}。

從第7輪至第10輪的輪密鑰涉及的密鑰比特集合為{k0,k1,…,k32,k117,k118,…,k127}，未使用實際密鑰的18比特集合為{k99,k100,…,k115,k116}。

利用TWIS輪密鑰的上述2個重要特點，根據第 3節中對三子集中間相遇攻擊思想與過程的介紹，選取α=4，β=7，即可將實際密鑰空間劃分為3個子集合A0、A1和A2，劃分方式如下

利用這些參數即可得到10輪TWIS的三子集中間相遇結構，并對密鑰進行初步篩選。具體過程如下。

已知一個明密文對(P,C)，對A0的 226種可能值。

1)猜測A1中密鑰的所有 218種可能值，計算v=φ1,4(P)。

3)選擇第5輪為中間匹配輪數，得到第5輪處的v’與u’，具體推導過程如圖2所示。圖中黑色部分表示受獨立密鑰A1、A2影響，白色部分表示不受影響。對v’與u’均不受獨立密鑰影響的32個比特值進行匹配，若 32個比特值不完全相同，則認為是錯誤密鑰，篩選概率為2-32。

該步的計算復雜度為：226(218+218)=245。

圖2 中間匹配過程

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

該步的計算復雜度為

觀察上式可發現，對TWIS只需要一步篩選即可期待淘汰所有錯誤密鑰，得到唯一的正確密鑰。

4.3 復雜度分析

根據第3節中對三子集中間相遇攻擊復雜度計算的介紹，恢復10輪TWIS實際全部62 bit密鑰信息的計算復雜度為

5 結束語

如表2所示，針對TWIS算法密鑰生成策略中存在的缺陷，本文首次對忽略后期白化的全10輪TWIS應用了三子集中間相遇攻擊。恢復實際密鑰的全部62 bit密鑰信息的數據復雜度僅為一個明密文對，計算復雜度為245，分析結果表明忽略后期白化的全10輪TWIS算法不抵抗三子集中間相遇攻擊。本文結果優于文獻[4]中Onur Kocak等人差分攻擊10輪TWIS得到的結果。

表2 TWIS安全性分析結果

[1]OJHA S K,KUMAR N,JAIN K. TWIS–a lightweight block cipher[A].Information Systems Security[C]. Berlin: Springer Heidelberg,2009.280-291.

[2]SHIRAI T,SHIBUTANI K,AKISHITA T,et al. The 128 bit block cipher CLEFIA[A]. Fast Software Encryption[C]. Berlin: Springer Heidelberg,2007.181-195.

[3]SU B Z,WU W L,ZHANG L,et al. Full-round differential attack on TWIS block cipher[A]. Information Security Applications[C]. Berlin:Springer Heidelberg,2011.234-242.

[4]KOCAK O,OZTOP N. Cryptanalysis of TWIS block cipher[A]. Research in Cryptology[C]. Berlin: Springer Heidelberg,2012.109-121.

[5]DIFFIE W,HELLMAN M E. Special feature exhaustive cryptanalysis of the NBS data encryption standard[J]. Computer,1977,10(6): 74-84.

[6]CHAUM D,EVERTSE J H. Cryptanalysis of DES with a reduced number of rounds[A]. Cryptology-CRYPTO’85 Proceedings[C]. Berlin: Springer Heidelberg,1986.192-211.

[7]DEMIRCI H,SELCUK A A. A meet-in-the-middle attack on 8-round AES[A]. Fast Software Encryption[C]. Berlin: Springer Heidelberg,2008.116-126.

[8]DEMIRCI H,TASKM ?,COBAN M,et al. Improved meet-in-themiddle attacks on AES[A]. Progress in Cryptology- INDOCRYPT 2009[C]. Berlin: Springer Heidelberg,2009.144-156.

[9]DUNKELMAN O,SEKAR G,PRENEEL B. Improved meet-in-themiddle attacks on reduced-round DES[A]. Progress in Cryptology–INDOCRYPT 2007[C]. Berlin: Springer Heidelberg,2007.86-100.

[10]INDESTEEGE S,KELLER N,DUNKELMAN O,et al. A practical attack on keeloq[A]. Cryptology-EUROCRYPT 2008[C]. Berlin: Springer Heidelberg,2008.1-18.

[11]DE C C,DUNKELMAN O,KNEZEVIC M. KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers[A]. Cryptographic Hardware and Embedded Systems-CHES 2009[C]. Berlin: Springer Heidelberg,2009.272-288.

[12]BOGDANOV A,RECHBERGER C. A 3-subset meet-in-the-middle attack: cryptanalysis of the lightweight block cipher KTANTAN[A].Selected Areas in Cryptography[C]. Berlin: Springer Heidelberg,2011.229-240.

[13]SEKAR G,MOUHA N,VELICHKOV V,et al. Meet-in-the-middle attacks on reduced-round XTEA[A]. Topics in Cryptology–CT-RSA 2011[C]. Berlin: Springer Heidelberg,2011.250-267.