FOX算法的中間相遇攻擊

李榮佳，金晨輝

（解放軍信息工程大學三院，河南 鄭州 450002）

FOX算法的中間相遇攻擊

李榮佳，金晨輝

（解放軍信息工程大學三院，河南 鄭州 450002）

研究了FOX分組密碼算法在中間相遇攻擊下的安全性。首先，分別構(gòu)造了FOX64和FOX128的3輪中間相遇區(qū)分器，實施了6輪中間相遇攻擊，得到對6輪FOX64和FOX128較好的攻擊結(jié)果。其次，將FOX128的中間相遇區(qū)分器擴展到4輪，并結(jié)合時間存儲數(shù)據(jù)折衷的方法，攻擊了7輪FOX128，與已有的攻擊結(jié)果相比，攻擊的時間復雜度和存儲復雜度略大，而數(shù)據(jù)復雜度明顯降低。

分組密碼；密碼分析；中間相遇攻擊；FOX算法

1 引言

FOX密碼算法[1]是由Junod和Vaudenay在2004年提出的系列分組密碼算法，分組規(guī)?？蔀?4 bit和128 bit，分別記為FOX64和FOX128。FOX密碼的整體結(jié)構(gòu)采用Lai-Massey結(jié)構(gòu)，其輪函數(shù)采用SPS結(jié)構(gòu)。FOX密碼算法在各平臺都具有不錯的性能，廣泛地應用于歐洲有線電視等安全產(chǎn)品中。

對 FOX算法的主要攻擊方法有積分攻擊、不可能差分攻擊、差分—碰撞攻擊等。文獻[2]利用3輪積分區(qū)分器分析了 FOX算法。文獻[3]分析了FOX算法抵抗不可能差分攻擊的能力。文獻[4]構(gòu)造了4輪區(qū)分器并給出了對FOX算法的差分—碰撞攻擊結(jié)果。文獻[5,6]分別對FOX64算法進行了零相關(guān)—積分分析和多維零相關(guān)線性分析。在 2014年FSE會議上，文獻[7]提出的對FOX算法的全子密鑰恢復攻擊，目前取得對FOX算法的較好攻擊結(jié)果。

中間相遇攻擊由Diffie和Hellman在分析DES算法的安全性時首次提出。近幾年，中間相遇攻擊被應用于AES算法的分析中，并得到了較好的攻擊結(jié)果。在文獻[8]中，Demirci和Sel?uk首次將中間相遇攻擊用于分析AES，利用4輪中間相遇區(qū)分器攻擊了7輪AES-192和8輪AES-256。文獻[9]有效地降低了Demirci和Sel?uk攻擊的存儲和時間復雜度。在2013年歐密會上，Derbez等[10]利用中間相遇攻擊取得了在單密鑰條件下對 AES-128較好的攻擊結(jié)果。文獻[11]利用中間相遇攻擊，結(jié)合密鑰制約關(guān)系，攻擊了9輪AES-192。

本文著重研究對 FOX算法的中間相遇攻擊。首先，本文通過構(gòu)造3輪的中間相遇區(qū)分器，對6輪FOX64和FOX128算法實施了攻擊，得到對6輪FOX64和FOX128較好的攻擊結(jié)果。其次，對于 FOX128，本文將其中間相遇攻擊區(qū)分器擴展到4輪，并結(jié)合時間存儲數(shù)據(jù)折衷的方法，對 7輪FOX128實施了攻擊，與已有的攻擊結(jié)果相比，此攻擊的時間復雜度和存儲復雜度略大，而數(shù)據(jù)復雜度明顯降低。表1和表2將本文對FOX算法的攻擊結(jié)果與此前的主要攻擊結(jié)果進行了對比。

表1 FOX64的主要分析結(jié)果

表2 FOX128的主要分析結(jié)果

2 預備知識

2.1 符號表示

x||y：x與y級聯(lián)。

Pi：第i個明文。

S：FOX密碼的S盒運算。

X[ i]：X的第i個字節(jié)。

X[ i,… ,j]：X的第i個到第j個字節(jié)。

X[ i,…,j]=Y[ i,…,j ]：X的第i個到第j個字節(jié)與Y的第i個到第j個字節(jié)對應相等。

2.2 FOX64密碼簡介

FOX64采用了16輪迭代的Lai-Massey結(jié)構(gòu)，其第 i輪的 64 bit輸入可以表示為 2個 32 bit。類似地，第i輪的64 bit的子密鑰Ki也可以表示為2個32 bitFOX64的具體結(jié)構(gòu)如圖 1所示。對于令設f32為其輪函數(shù)，則

圖1 1輪FOX64

輪函數(shù)f32采用SPS結(jié)構(gòu)，包括子密鑰加、代替變換 sigma4和擴散變換mu4這3個變換，可以表示為

代替變換 sigma4由4個8 bit S盒并置而成，擴散變換mu4是一個4×4的MDS矩陣運算。

2.3 FOX128密碼簡介

與FOX64類似，F(xiàn)OX128也采用16輪迭代的Lai-Massey結(jié)構(gòu)，其第i輪的128 bit輸入表示為4個128 bit的子密鑰Ki表示為2個的具體結(jié)構(gòu)如圖2所示，設f64為其輪函數(shù)，則

圖2 1輪FOX128

輪函數(shù) f64與 f32類似，采用SPS結(jié)構(gòu)，包括子密鑰加、代替變換 sigma8和擴散變換mu8這3個變換，可以表示為

代替變換 sigma8由8個8 bit S盒并置而成，擴散變換mu8是一個8× 8的MDS矩陣運算。

本文把輪函數(shù) f32和 f64的輸入記作x，經(jīng)過第1層子密鑰加、第1層代替變換、擴散變換、第2層子密鑰加、第2層代替變換、第3層子密鑰加后的狀態(tài)分別記作 y、z、w、q、r、s。

一輪FOX64算法具有如下性質(zhì)。

性質(zhì)1[6]設1輪FOX64的輸入為輸出為則有

類似地，F(xiàn)OX128算法具有如下性質(zhì)。

性質(zhì)2[6]設1輪FOX128的輸入為，輸出為，則有

3 FOX64的中間相遇攻擊

3.1 FOX64的3輪區(qū)分器

本文給出FOX64的3輪中間相遇區(qū)分器，如圖3所示，其中白塊表示差分為0，黑塊表示可以求出的差分，下同。

定理1給定FOX64的16個明文 {P0,P1,… ,P15},滿 足 Pi[2]=Pi[6]=i,Pj[0,1,3,4,5,7]=P0[0,1,3,4,5,7](0 ≤ i,j≤ 15)。若對這 16個明文進行 3輪FOX64加密，則有序序列只有 288種可能的取值。

證明序列由如下11個字節(jié)決定：

圖3 FOX64的3輪中間相遇區(qū)分器

3.2 FOX64的6輪中間相遇攻擊

攻擊分為2階段：預計算階段和在線階段。

在線階段：在線階段的具體攻擊步驟如下。

步驟1選擇16個明文滿足并獲取相應的密文。

步驟 2猜測子密鑰脫密16個密文，得到

步驟3由性質(zhì)1，計算進而得到序列

步驟4檢測步驟3中求得的序列是否在預計算表H1中。若在，則判定猜測的密鑰為正確密鑰；否則，判定為錯誤密鑰。故一個錯誤密鑰通過檢測的概率為最終保留的密鑰個數(shù)為

4 FOX128的中間相遇攻擊

4.1 FOX128的3輪區(qū)分器

本文給出FOX128的3輪中間相遇區(qū)分器，如圖4所示。

定理2給定FOX128的25個明文若對這25個明文進行 3輪 FOX128加密，則有序序列只有1522 種可能的取值。

圖4 FOX128的3輪中間相遇區(qū)分器

4.2 FOX128的6輪中間相遇攻擊

攻擊分為2階段：預計算階段和在線階段。

在線階段：在線階段的具體攻擊步驟如下。

步驟1選擇25個明文滿足并獲取相應的密文。

步驟 2猜測子密鑰脫密25個密文,得到

步驟3由性質(zhì)2計算進而得到序列

步驟4檢測步驟3中求得的序列是否在預計算表H2中。若在，則判定猜測的密鑰為正確密鑰；否則，判定為錯誤密鑰。故一個錯誤密鑰通過檢測的概率為，最終保留的密鑰個數(shù)為

4.3 FOX128的7輪中間相遇攻擊

在FOX128的3輪中間相遇區(qū)分器的中間增加1輪，本文得到如下的4輪中間相遇區(qū)分器。

定理3給定FOX128的25個明文，滿足若對這25個明文進行 4輪 FOX128加密，則序列只有2802 種可能的取值。

如果本文采用4.2節(jié)中的方法，在預計算階段計算所有的2802 種可能的取值，那么預計算階段的時間復雜度大約為次7輪FOX128加密，存儲復雜度大約為個128 bit，這一復雜度超出了窮舉攻擊的復雜度。因此，本文利用時間存儲數(shù)據(jù)折衷的方法，預計算階段，只計算并存儲序列的2802 種可能取值中的同時，在線階段，本文需要選擇大約個明文，重復382次攻擊。于是正確密鑰可以在預計算表中找到匹配的概率變?yōu)?/p>

也就是說，本文攻擊成功的概率為99.97%。經(jīng)過時間存儲數(shù)據(jù)折衷后，預計算階段的時間復雜度降低為次7輪FOX128加密，而在線階段的時間復雜度提高到次7輪FOX128加密，故攻擊的時間復雜度約等于在線階段的時間復雜度。攻擊的存儲復雜度降低為個128 bit。攻擊所需的數(shù)據(jù)量變?yōu)?42.6個選擇明文。

5 結(jié)束語

本文主要研究了對FOX64和FOX128算法的中間相遇攻擊，首先，本文分別構(gòu)造了 FOX64和FOX128的 3輪中間相遇區(qū)分器，通過猜測最后 2輪的部分子密鑰，利用1輪FOX算法的輸入與輸出的關(guān)系，實施了 6輪攻擊，此攻擊是目前為止對 6輪FOX64和FOX128較好的攻擊結(jié)果。其次，本文將FOX128的中間相遇攻擊區(qū)分器擴展到4輪，并結(jié)合時間存儲數(shù)據(jù)折衷的方法，對7輪FOX128實施了攻擊，與已有的攻擊結(jié)果相比，此攻擊的時間復雜度和存儲復雜度略大，而數(shù)據(jù)復雜度得到明顯降低。

[1]JUNOD P,VAUDENAY S. FOX: a new family of block ciphers[C]//Lecture Notes in Computer Science,2004. c2004:131-146.

[2]WU W,ZHANG W,FENG D. Integral cryptanalysis of reduced FOX block cipher[J]. Lecture Notes in Computer Science. 2005,3935(1):229-241.

[3]WU Z M,LAI X J,ZHU B,et al. Impossible differential cryptanalysis of FOX [EB/OL]. IACR Cryptology ePrint Archive,2009.

[4]CHEN J,HU Y P,ZHANG Y Y,et al. Differential collision attack on reduced fox block cipher[J]. China Communications. 2012,9(7):71-76.

[5]郭瑞,金晨輝. 低輪 FOX64 算法的零相關(guān)-積分分析[J]. 電子與信息學報,2015,37(2): 417-422.GUO R,JIN C H. Integral cryptanalysis of reduced round FOX64[J]. Journal of Electronics amp; Information Technology. 2015,37(2): 417-422

[6]伊文壇,陳少真. FOX密碼的多維零相關(guān)線性分析[J]. 密碼學報,2015,2(1): 27-39.YI W T,CHEN S Z. Multidimensional zero-correlation linear attacks on Fox block cipher[J]. Journal of Cryptologic Research,2015,2(1): 27-39.

[7]ISOBE T,SHIBUTANI K. Improved all-subkeys recovery attacks on FOX,KATAN and SHACAL-2 block ciphers [C]//FSE 2014. c2014:104-126.

[8]DEMIRCI H,SEL?UK A. A Meet-in-the-middle attack on 8-round AES[C]//Lecture Motes in Computer Science,Lausanne,Switzerland,c2008:116-126.

[9]DUNKELMAN O,KELLER N,SHAMIR A. Improved single-key attacks on 8-round AES-192 and AES-256[J]. Journal of Cryptology,2010,28(3):158-176.

[10]DERBEZ,P,FOUQUE P A,JEAN J. Improved key recovery attacks on reduced-round AES in the single-key setting[J]. Lecture Notes in Computer Science,2013,788: 371-387.

[11]LI L B,JIA K T,WANG X Y. Improved single-key attacks on 9-round AES-192/256[M]//Fast Software Encryption. Springer Berlin Heidelberg,2014:127-146.

Meet-in-the-middle attacks on FOX block cipher

LI Rong-jia,JIN Chen-hui

(The Third College,PLA Information Engineering University,Zhengzhou 450002,China)

The security of the block cipher FOX against meet-in-the-middle attack was analyzed. Firstly,3-round meet-in-the-middle distinguishers was constructed and 6-round meet-in-the-middle attacks for FOX64 and FOX128 was proposed. The two attacks were beter attacks for 6-round FOX64 and FOX128,respectively. Secondly,the meet-in-the-middle distinguisher was extended of FOX128 to 4 rounds and proposed 7-round meet-in-the-middle attack combined with time/memory/data tradeoff. Compared to the currently known attacks on 7-round FOX128,The attack has a greater time and memory complexity,however the data complexity is much smaller.

block cipher,cryptanalysis,meet-in-the-middle attack,FOX

The National Natural Science Foundation of China (No.61272488,No.61402523)

TP918.1

A

2015-06-26；

2016-01-20

國家自然科學基金資助項目（No.61272488,No.61402523）

10.11959/j.issn.1000-436x.2016168

李榮佳（1991-），男，山東泗水人，解放軍信息工程大學碩士生，主要研究方向為對稱密碼設計與分析。

金晨輝（1965-），男，河南扶溝人，解放軍信息工程大學教授，主要研究方向為密碼學與信息安全。