FOX密碼的不可能差分攻擊

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

（1. 國防科技大學 計算機學院，湖南 長沙410073；2. 國防科技大學 理學院，湖南 長沙410073；3. 中國科學院研究生院 信息安全國家重點實驗室，北京100049）

1 引言

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

根據算法S盒和擴散層的密碼學性質，可以估計 FOX密碼關于差分密碼攻擊和線性密碼攻擊的安全性。文獻[1]給出了算法對截斷差分分析、高階差分分析、不可能差分分析和滑動攻擊等攻擊方法的免疫能力，目前對于 FOX較為有效的攻擊是文獻[4]和文獻[5]中給出的積分攻擊，指出FOX存在3輪積分區分器，7輪FOX64/256和5輪FOX128/256對積分攻擊是不免疫的。

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

2 FOX分組密碼介紹

FOX是基于字節的分組密碼，由于篇幅限制，僅詳細介紹分組長度為 64bit的 FOX64，FOX128可看作2個FOX64密碼的并置。

2.1 輪函數

輪函數 f主要包括 3個變換：代替變換sigma4，擴散變換 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個8× 8的S盒并置而成，MU4是將32bit的輸入劃分為4個8bit，將其乘以一個MDS矩陣，輸出仍然為32bit。

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

圖1 FOX64的輪函數

2.2 加解密流程

FOX64/k/r將64bit明文經過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)由種子密鑰經密鑰擴展得到。一輪加密過程如圖2(a)所示。

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

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

圖2 1輪加密過程

3 4輪不可能差分

本節利用中間相遇法尋找FOX的不可能差分，所給出的不可能差分很大程度上基于擴散層MU的性質，FOX64和FOX128所使用的擴散變換MU4和MU8都是MDS的[1]。

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

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

其中，標注為粗體字處為非零差分。

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

則，

利用同樣的方法，從第4輪往回解密，可以發現

根據算法結構和加解密的關系，有

即，

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

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

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

利用上一節找到的不可能差分，本節給出對低輪 FOX密碼的不可能差分攻擊結果。為了計算攻擊復雜度，首先介紹文獻[6]中的一個命題。

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

圖3 FOX64的4輪不可能差分

該命題的實質就是差分攻擊中的查表運算，將相關結果存儲起來，避免了多次進行復雜運算，其本質是犧牲存儲空間來降低時間復雜度。

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

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

圖4 對5輪FOX64的不可能差分攻擊

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

該攻擊的數據復雜度和時間復雜度如下：

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

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

故攻擊5輪FOX密碼的數據復雜度為 239，時間復雜度為 268。

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

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

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

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

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

2) 在淘汰密鑰階段，一共需要猜測 264個密鑰（包括的32bit和的32bit），需要計算不大于 264N= 2135次f函數，相當于 2133次加密。

故攻擊6輪FOX密碼的數據復雜度為 256，時間復雜度為 2133。

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

該攻擊的復雜度如下：

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

2) 在淘汰密鑰階段，一共需要猜測 232×264×232= 2128個密鑰，一共需要計算不大于 2128N=2215次f函數，相當于 2213次加密。

故攻擊6輪FOX密碼的數據復雜度為 256，時間復雜度為 2213。

5 低輪FOX128密碼的攻擊

對于FOX128的攻擊與FOX64的攻擊類似，本文不再詳細描述，只給出攻擊結果。攻擊 5輪FOX128的數據復雜度為 272，時間復雜度為 2134。

6 結束語

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

表1 FOX64密碼的攻擊結果

表2 FOX128密碼的攻擊結果

[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] 吳文玲, 衛宏儒. 低輪 FOX 分組密碼的碰撞積分攻擊[J]. 電子學報. 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]. 系統科學與數學,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.