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

鄭雅菲，衛(wèi)宏儒

(北京科技大學(xué) 數(shù)理學(xué)院，北京 100083)

1 引言

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

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

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

本文通過研究分組密碼TWIS輪密鑰生成的缺陷，對(duì)忽略后期白化過程的全10輪TWIS應(yīng)用三子集中間相遇攻擊?；謴?fù)實(shí)際全部62 bit密鑰信息的計(jì)算復(fù)雜度為245，數(shù)據(jù)復(fù)雜度僅為一個(gè)已知明密文對(duì)，攻擊結(jié)果表示TWIS算法不抵抗三子集中間相遇攻擊。本文的計(jì)算復(fù)雜度與數(shù)據(jù)復(fù)雜度均優(yōu)于TWIS現(xiàn)有的安全性分析結(jié)果。

2 分組密碼TWIS介紹

2.1 符號(hào)說明

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

＜＜＜ i：左循環(huán)移位i bit。

＞＞＞j：右循環(huán)移位j bit。

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

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

|A|：集合A中的元素個(gè)數(shù)。

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

2.2 分組密碼TWIS

TWIS是輕量級(jí)分組密碼，其分組長度與密鑰長度均為128 bit，算法結(jié)構(gòu)為2-分支的廣義Feistel結(jié)構(gòu)，迭代輪數(shù)為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的加密過程如下

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

F函數(shù)實(shí)現(xiàn)算法的密鑰混合，本文攻擊不涉及其具體計(jì)算，故不進(jìn)行詳細(xì)介紹，可參見文獻(xiàn)[1]。

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

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

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

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

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

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

圖1 三子集中間相遇結(jié)構(gòu)

當(dāng)R-β+1=α?xí)r，三子集中間相遇攻擊等價(jià)于中間相遇攻擊。

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

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

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

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

該步的計(jì)算復(fù)雜度為

接下來，進(jìn)一步對(duì)剩余所有密鑰進(jìn)行篩選。

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

該步的計(jì)算復(fù)雜度為

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

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

在對(duì)密鑰子集合的劃分中，只要|A1|+|A2|＞2，即可得到優(yōu)于窮舉搜索的計(jì)算復(fù)雜度。

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

TWIS算法的設(shè)計(jì)者稱其密鑰長度為128 bit，但是觀察其密鑰生成策略可以發(fā)現(xiàn)，每輪變換循環(huán)移位僅3 bit，值改變的量僅為24 bit。這使得初始密鑰的混淆速度非常慢。經(jīng)過推導(dǎo)可發(fā)現(xiàn)其實(shí)際密鑰長度僅為62 bit，且忽略后期白化后，算法首尾兩端可找到較長輪數(shù)的獨(dú)立密鑰。

本文攻擊利用該特點(diǎn)，通過推測(cè)各輪的輪密鑰，對(duì)忽略后期白化過程的全10輪TWIS應(yīng)用三子集中間相遇攻擊。

表1 TWIS各輪輪密鑰

4.1 輪密鑰推導(dǎo)

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

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

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

在TWIS實(shí)際密鑰長度l=62的基礎(chǔ)上應(yīng)用三子集中間相遇攻擊，使得復(fù)雜度進(jìn)一步降低。

考慮初始白化密鑰，忽略后期白化密鑰，觀察各輪輪密鑰可有如下發(fā)現(xiàn)。

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

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

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

利用這些參數(shù)即可得到10輪TWIS的三子集中間相遇結(jié)構(gòu)，并對(duì)密鑰進(jìn)行初步篩選。具體過程如下。

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

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

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

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

圖2 中間匹配過程

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

該步的計(jì)算復(fù)雜度為

觀察上式可發(fā)現(xiàn)，對(duì)TWIS只需要一步篩選即可期待淘汰所有錯(cuò)誤密鑰，得到唯一的正確密鑰。

4.3 復(fù)雜度分析

根據(jù)第3節(jié)中對(duì)三子集中間相遇攻擊復(fù)雜度計(jì)算的介紹，恢復(fù)10輪TWIS實(shí)際全部62 bit密鑰信息的計(jì)算復(fù)雜度為

5 結(jié)束語

如表2所示，針對(duì)TWIS算法密鑰生成策略中存在的缺陷，本文首次對(duì)忽略后期白化的全10輪TWIS應(yīng)用了三子集中間相遇攻擊?；謴?fù)實(shí)際密鑰的全部62 bit密鑰信息的數(shù)據(jù)復(fù)雜度僅為一個(gè)明密文對(duì)，計(jì)算復(fù)雜度為245，分析結(jié)果表明忽略后期白化的全10輪TWIS算法不抵抗三子集中間相遇攻擊。本文結(jié)果優(yōu)于文獻(xiàn)[4]中Onur Kocak等人差分攻擊10輪TWIS得到的結(jié)果。

表2 TWIS安全性分析結(jié)果

[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.