FOX密碼的不可能差分攻擊

魏悅川，孫兵，李超,,3

（1. 國(guó)防科技大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙410073；2. 國(guó)防科技大學(xué) 理學(xué)院，湖南 長(zhǎng)沙410073；3. 中國(guó)科學(xué)院研究生院 信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100049）

1 引言

FOX是Junod和Vaudenay基于Mediacrypt公司需求設(shè)計(jì)的系列分組密碼[1]，分組長(zhǎng)度可為64bit或128bit，密鑰長(zhǎng)度為8的倍數(shù)，在0～256bit之間可變。FOX64/k/r表示分組長(zhǎng)度為64，密鑰長(zhǎng)度為k，輪數(shù)為r，同理可以表示FOX128/k/r。對(duì)于FOX64/128/r和FOX128/256/r，設(shè)計(jì)者建議輪數(shù)r均為16。FOX密碼采用修正的Lai-Massey結(jié)構(gòu)，其輪函數(shù)為具有 3層密鑰加操作的 SPS結(jié)構(gòu)，利用可證明安全理論，這一結(jié)構(gòu)被證明了有很好的抗差分和線性分析的能力[2]，F(xiàn)OX擴(kuò)散層原始的設(shè)計(jì)思想源于文獻(xiàn)[3]。另外，F(xiàn)OX密碼的密鑰擴(kuò)展方案非常復(fù)雜，這一特點(diǎn)與整體結(jié)構(gòu)和輪函數(shù)一起，保證了 FOX密碼的可證明安全性。

根據(jù)算法S盒和擴(kuò)散層的密碼學(xué)性質(zhì)，可以估計(jì) FOX密碼關(guān)于差分密碼攻擊和線性密碼攻擊的安全性。文獻(xiàn)[1]給出了算法對(duì)截?cái)嗖罘址治觥⒏唠A差分分析、不可能差分分析和滑動(dòng)攻擊等攻擊方法的免疫能力，目前對(duì)于 FOX較為有效的攻擊是文獻(xiàn)[4]和文獻(xiàn)[5]中給出的積分攻擊，指出FOX存在3輪積分區(qū)分器，7輪FOX64/256和5輪FOX128/256對(duì)積分攻擊是不免疫的。

不可能差分分析是差分密碼分析的一個(gè)變種，這個(gè)概念由Biham和Knudsen分別獨(dú)立提出。通常的差分分析方法通過尋找高概率差分來恢復(fù)密鑰，不可能差分則與之相反，尋找的是不可能出現(xiàn)的差分，若某個(gè)猜測(cè)密鑰能使不可能差分出現(xiàn)，則一定是錯(cuò)誤密鑰，從而被淘汰。不可能差分攻擊是對(duì)分組密碼比較有效的攻擊之一[6～9]，它是當(dāng)前對(duì)簡(jiǎn)化輪數(shù)的Rijndael算法和Camellia算法最有效的攻擊手段。本文在研究 FOX密碼結(jié)構(gòu)性質(zhì)的基礎(chǔ)上，找到了4輪的不可能差分，利用不可能差分分析的方法，改進(jìn)了對(duì) 5輪、6輪和7輪FOX64和5輪FOX128的攻擊結(jié)果，使時(shí)間復(fù)雜度明顯降低。結(jié)果顯示7輪FOX64/256和 5輪 FOX128/192/256對(duì)本文的攻擊都是不免疫的。

2 FOX分組密碼介紹

FOX是基于字節(jié)的分組密碼，由于篇幅限制，僅詳細(xì)介紹分組長(zhǎng)度為 64bit的 FOX64，F(xiàn)OX128可看作2個(gè)FOX64密碼的并置。

2.1 輪函數(shù)

輪函數(shù) f主要包括 3個(gè)變換：代替變換sigma4，擴(kuò)散變換 MU4和密鑰加變換（如圖 1所示）。其定義如下。

f∶{ 0,1}32×{0,1}64→ { 0,1}32X(32)×K(64)→Y(32)，K(64)=KL(32)||KR(32)，Y(32)=sigma 4 (MU4(sigma 4(X(32)⊕ K0(32)))⊕K1(32))⊕K0(32)。

其中，sigma4由4個(gè)8× 8的S盒并置而成，MU4是將32bit的輸入劃分為4個(gè)8bit，將其乘以一個(gè)MDS矩陣，輸出仍然為32bit。

其中， z=α-1+1，α是 F2[x ]中不可約多項(xiàng)式m(x)=x8+x7+ x6+x5+x4+x3+ 1 在其擴(kuò)域中的一個(gè)根。

圖1 FOX64的輪函數(shù)

2.2 加解密流程

FOX64/k/r將64bit明文經(jīng)過r輪迭代得到64bit密文，其中，最后一輪沒有 or變換。一輪變換Imor64∶{0 ,1}64×{ 0,1}64→ { 0,1}64過程如下：

輸入為 X(64)=XL(32)||XR(32)，輸出為 Y(64)=or(XL(32)⊕Φ)||(XR(32)⊕Φ)，其中，Φ=f( XL(32)⊕XR(32),RK(64))，or變換將32bit輸入 X(32)=XL(16)||XR(16)映射為32bit輸出 Y(32)=YL(16)||YR(16)=XR(16)||(XL(16)⊕ XR(16))。r輪加密過程為：

其中，Imid64將Imor64中的or變換代替為恒等變換，輪密鑰 R K1(64)||RK2(64)||…||RKr(64)由種子密鑰經(jīng)密鑰擴(kuò)展得到。一輪加密過程如圖2(a)所示。

解密過程與加密過程的區(qū)別在于輪密鑰使用的順序剛好相反，or變換被or-1變換代替，Imo表示替換后的變換：

FOX128與FOX64加密流程基本相同，不同之處在于FOX128的輪函數(shù)是64bit輸入和64bit輸出，它類似于2個(gè)FOX64密碼的并置，此處僅給出加密流程，如圖2(b)所示，細(xì)節(jié)請(qǐng)參考文獻(xiàn)[1]。

圖2 1輪加密過程

3 4輪不可能差分

本節(jié)利用中間相遇法尋找FOX的不可能差分，所給出的不可能差分很大程度上基于擴(kuò)散層MU的性質(zhì)，F(xiàn)OX64和FOX128所使用的擴(kuò)散變換MU4和MU8都是MDS的[1]。

定理1 1) FOX64存在如下的4輪不可能差分：

2) FOX128存在如下的4輪不可能差分：

其中，標(biāo)注為粗體字處為非零差分。

證明 僅證明FOX64的一條差分(a,0 ,b,0 ,a,0,b,0)→(c,0,d,0,c,0,d,0)（其中，a≠0）是不可能的，其他不可能差分的證明類似，具體過程從略。差分的傳播過程如圖3所示。根據(jù)算法的結(jié)構(gòu)可以檢驗(yàn)，輸入差分(a , 0,b,0,a , 0,b,0)經(jīng)過 1輪之后必為以下形式：則= (a⊕b ,0,a,0)，于是weight(a ⊕b,0,a,0)≤2。將(a⊕b,0,a,0)和RK2輸入f2后，假設(shè)其輸出為(w1,w2,w3,w4)，由于S盒不會(huì)影響非零字節(jié)的位置，根據(jù)擴(kuò)散變換MU4的分支數(shù)Branch(MU4)=5這一事實(shí)，可以得出weight(a⊕ b,0,a ,0)⊕weight(w1,w2,w3,w4)≥5 ，進(jìn)而weight(w1, w2, w3, w4)≥ 5-2 = 3，即 w1，w2，w3，w4中至少有3byte非零。經(jīng)過第2輪迭代，可以驗(yàn)證

則，

利用同樣的方法，從第4輪往回解密，可以發(fā)現(xiàn)

根據(jù)算法結(jié)構(gòu)和加解密的關(guān)系，有

即，

進(jìn)而有 w2⊕w4=0，w2=0，所以w2= w4=0，這與 ( w1,w2,w3,w4)中至少有3byte不為零的事實(shí)相矛盾。

同理可證其他的不可能差分，其中，證明FOX128的不可能差分時(shí)利用的是 MU8的分支數(shù)為9。

4 FOX64密碼的不可能差分攻擊

利用上一節(jié)找到的不可能差分，本節(jié)給出對(duì)低輪 FOX密碼的不可能差分攻擊結(jié)果。為了計(jì)算攻擊復(fù)雜度，首先介紹文獻(xiàn)[6]中的一個(gè)命題。

命題1 對(duì)f函數(shù)而言，令(In, In')為2個(gè)32bit輸入，Δout為相應(yīng)的差分值，RK為包含在f函數(shù)中的輪密鑰，則計(jì)算RK只需要計(jì)算一次f函數(shù)。

圖3 FOX64的4輪不可能差分

該命題的實(shí)質(zhì)就是差分攻擊中的查表運(yùn)算，將相關(guān)結(jié)果存儲(chǔ)起來，避免了多次進(jìn)行復(fù)雜運(yùn)算，其本質(zhì)是犧牲存儲(chǔ)空間來降低時(shí)間復(fù)雜度。

4.1 5輪FOX64的不可能差分攻擊

利用4輪不可能差分，在末尾加一輪，可以對(duì)5輪FOX密碼進(jìn)行攻擊。僅就FOX64的一條不可能差分(a , 0,b, 0,a , 0,b,0)→(c, 0,d , 0,c, 0,d,0)給出詳細(xì)攻擊過程。攻擊示意圖如圖4所示。

圖4 對(duì)5輪FOX64的不可能差分攻擊

令φ= ( u1, u2, … ,u8)，ui∈F28(i= 1 ,…,8 )均為常數(shù)，Λ= (x, u2, y, u4, x, u6, y, u8)，其中，x遍歷 F28，y遍歷 F28。定義結(jié)構(gòu)一個(gè)結(jié)構(gòu)Γφ中含有(28- 1 )× 28≈ 216個(gè)元素，從同一個(gè)結(jié)構(gòu)中選擇的 2個(gè)明文差分形式為(a,0,b,0,a , 0,b,0)，每個(gè)結(jié)構(gòu)中約有個(gè)明文對(duì)。選取223個(gè)結(jié)構(gòu)，可以得到 239個(gè)明文和 254對(duì)明文。選擇具有如下差分形式的密文具有這種形式的密文對(duì)(C, C*)有N= 254× 2-16= 238對(duì)。為猜測(cè)最后一輪輪密鑰，用64bit密鑰的所有可能值對(duì)密文對(duì)進(jìn)行解密，如果解密得到f5變換后左右兩邊的差分為(c ⊕d,0,c,0)，則該密鑰被淘汰。對(duì)一對(duì)密文進(jìn)行解密，淘汰的密鑰量為剩余密鑰的 ( 2-8)4= 2-32，過濾了 238對(duì)明密文對(duì)后，剩下的錯(cuò)誤密鑰數(shù)目為因此正確密鑰被唯一確定。

該攻擊的數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度如下：

1) 為得到密文需要 239次明文加密；

2) 在淘汰密鑰階段，由于需要猜測(cè) 232個(gè)密鑰（的左邊32bit），另外32bit密鑰可以用查表來淘汰。因此，一共需要計(jì)算不少于 232N= 270次f函數(shù)，相當(dāng)于 268次加密。

故攻擊5輪FOX密碼的數(shù)據(jù)復(fù)雜度為 239，時(shí)間復(fù)雜度為 268。

4.2 6輪FOX64的不可能差分攻擊

在4.1節(jié)攻擊的基礎(chǔ)上，如果在前面再添加額外一輪，就可以得到6輪FOX64密碼的不可能差分攻擊。

令φ= ( u1, u2, … ,u8)， ui∈F28(i= 1 ,…,8 )為常數(shù)，Λ = (x, u2, y, u4, z, u6, w, u8)，其中，x，y，z，w遍歷 F28。定義結(jié)構(gòu)一個(gè)結(jié)構(gòu)Γφ中約含有(28)4=232個(gè)元素。從Γφ中選擇的明文具有本文所需要的結(jié)構(gòu)

選取 224個(gè)結(jié)構(gòu)，可以得到 256個(gè)明文和 287對(duì)明文。選擇具有如下差分形式的密文具有這種形式的密文對(duì) C ⊕C*有N= 287× 2-16= 271對(duì) 。 為 猜 測(cè) 輪 密 鑰和，用128bit密鑰的所有可能值分別對(duì)明文對(duì)進(jìn)行一輪加密和對(duì)密文對(duì)進(jìn)行一輪解密，如果加密一輪后進(jìn)入f2變換的差分形如(0,0,0,0)，并且解密得到f6變換后的差分為(c ⊕d,0,c,0)，則該密鑰被淘汰。對(duì)一對(duì)明密文進(jìn)行加解密，淘汰的密鑰量為剩余密鑰的 ( 2-8)4× ( 2-8)4= 2-64，過濾了 271對(duì)明密文對(duì)后，剩下的錯(cuò)誤密鑰數(shù)目為( 2128- 1 )(1 - 2-64)271≈ 2128× e-128＜ 1 ，因此正確密鑰被唯一確定。該攻擊的復(fù)雜度如下：

1) 為得到密文需要 256次明文加密；

2) 在淘汰密鑰階段，一共需要猜測(cè) 264個(gè)密鑰（包括的32bit和的32bit），需要計(jì)算不大于 264N= 2135次f函數(shù)，相當(dāng)于 2133次加密。

故攻擊6輪FOX密碼的數(shù)據(jù)復(fù)雜度為 256，時(shí)間復(fù)雜度為 2133。

4.3 7輪FOX64的不可能差分攻擊

該攻擊的復(fù)雜度如下：

1) 為得到密文需要562次明文加密；

2) 在淘汰密鑰階段，一共需要猜測(cè) 232×264×232= 2128個(gè)密鑰，一共需要計(jì)算不大于 2128N=2215次f函數(shù)，相當(dāng)于 2213次加密。

故攻擊6輪FOX密碼的數(shù)據(jù)復(fù)雜度為 256，時(shí)間復(fù)雜度為 2213。

5 低輪FOX128密碼的攻擊

對(duì)于FOX128的攻擊與FOX64的攻擊類似，本文不再詳細(xì)描述，只給出攻擊結(jié)果。攻擊 5輪FOX128的數(shù)據(jù)復(fù)雜度為 272，時(shí)間復(fù)雜度為 2134。

6 結(jié)束語

本文給出了FOX系列密碼的4輪不可能差分，并利用它對(duì)低輪數(shù)的FOX密碼進(jìn)行了攻擊，攻擊復(fù)雜度及其比較在表1和表2中列出。與已知的攻擊結(jié)果相比，所需的計(jì)算量大幅度降低。之所以有這些結(jié)果，主要是因?yàn)楸疚恼业降牟豢赡懿罘謹(jǐn)?shù)據(jù)量大，從而可以選擇的明文量更大。由于設(shè)計(jì)者推薦FOX64和FOX128的輪數(shù)為16，因此本文結(jié)果并未威脅到完整輪數(shù)的FOX算法。鑒于不可能差分的結(jié)果，要求設(shè)計(jì)者除了考慮差分特征和線性逼近的上界之外，還要考慮差分特征的下界（即概率為零的差分特征），確保算法能抵抗不可能差分攻擊。

表1 FOX64密碼的攻擊結(jié)果

表2 FOX128密碼的攻擊結(jié)果

[1] JUNOD P, VAUDENAY S. FOX∶ a new family of block ciphers[A].Selected Areas in Cryptography-SAC 2004[C]. Waterloo, Canada.,2004.114-129.

[2] VAUDENAY S. On the lai-massey scheme[A]. Advances in Cryptology—Asiacrypt’99[C]. 1999.8-19.

[3] JUNOD P, VAUDENAY S. Perfect diffusion primitives for block ciphers—building efficient MDS matrices[A]. Selected Areas in Cryptography-SAC 2004[C]. Waterloo, Canada, 2004. 84-99.

[4] WU W L, ZHANG W T, FENG D G. Integral cryptanalysis of reduced fox block cipher[A]. ICISC 2005[C]. Beijing, China, 2005.229-241.

[5] 吳文玲, 衛(wèi)宏儒. 低輪 FOX 分組密碼的碰撞積分攻擊[J]. 電子學(xué)報(bào). 2005, 33(7)∶ 1307-1310.WU W L, WEI H R. Collision-integral attack of reduced-round FOX[J]. Acta Electronica Sinica, 2005, 33(7)∶ 1307-1310.

[6] WU W L, ZHANG L, ZHANG W T. Improved impossible differential cryptanalysis of reduced-round camellia[A]. Selected Areas in Cryptography-SAC 2008[C]. New Brunswick, Canada. 2008. 442-456.

[7] TSUNOO Y, TSUJIHARA E, SHIGERI M, et al. Impossible differential cryptanalysis of CLEFIA[A]. Fast Software Encryption—FSE 2008[C]. 2008. 398-411.

[8] HONG D, SUNG J, MORIAI S, et al. Impossible differential cryptanalysis of zodiac[A]. Fast Software Encryption—FSE 2001[C]. Yokohama, Japan, 2001.300-311.

[9] 吳文玲, 張蕾. 不可能差分密碼分析研究進(jìn)展[J]. 系統(tǒng)科學(xué)與數(shù)學(xué),2008, 28(8)∶ 971-983.WU W L, ZHANG L. The state of the art of research on impossible differential cryptanalysis[J]. Journal of System Science and Mathematics and Science, 2008, 28(8)∶ 971-983.

[10] MINIER M. An integral cryptanalysis against a five rounds version of FOX[A]. Western European Workshop on Research in Cryptology 2005[C]. 2005. 98-103.