李榮佳，金晨輝

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

FOX算法的中間相遇攻擊

李榮佳，金晨輝

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

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

分組密碼；密碼分析；中間相遇攻擊；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密碼算法在各平臺(tái)都具有不錯(cuò)的性能，廣泛地應(yīng)用于歐洲有線電視等安全產(chǎn)品中。

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

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

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

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

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

2 預(yù)備知識(shí)

2.1 符號(hào)表示

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

Pi：第i個(gè)明文。

S：FOX密碼的S盒運(yùn)算。

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

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

X[ i,…,j]=Y[ i,…,j ]：X的第i個(gè)到第j個(gè)字節(jié)與Y的第i個(gè)到第j個(gè)字節(jié)對(duì)應(yīng)相等。

2.2 FOX64密碼簡(jiǎn)介

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

圖1 1輪FOX64

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

代替變換 sigma4由4個(gè)8 bit S盒并置而成，擴(kuò)散變換mu4是一個(gè)4×4的MDS矩陣運(yùn)算。

2.3 FOX128密碼簡(jiǎn)介

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

圖2 1輪FOX128

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

代替變換 sigma8由8個(gè)8 bit S盒并置而成，擴(kuò)散變換mu8是一個(gè)8× 8的MDS矩陣運(yùn)算。

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

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

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

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

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

3 FOX64的中間相遇攻擊

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

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

定理1給定FOX64的16個(gè)明文 {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)。若對(duì)這 16個(gè)明文進(jìn)行 3輪FOX64加密，則有序序列只有 288種可能的取值。

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

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

3.2 FOX64的6輪中間相遇攻擊

攻擊分為2階段：預(yù)計(jì)算階段和在線階段。

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

步驟1選擇16個(gè)明文滿足并獲取相應(yīng)的密文。

步驟 2猜測(cè)子密鑰脫密16個(gè)密文，得到

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

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

4 FOX128的中間相遇攻擊

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

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

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

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

4.2 FOX128的6輪中間相遇攻擊

攻擊分為2階段：預(yù)計(jì)算階段和在線階段。

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

步驟1選擇25個(gè)明文滿足并獲取相應(yīng)的密文。

步驟 2猜測(cè)子密鑰脫密25個(gè)密文,得到

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

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

4.3 FOX128的7輪中間相遇攻擊

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

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

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

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

5 結(jié)束語(yǔ)

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

[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]. 電子與信息學(xué)報(bào),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]. 密碼學(xué)報(bào),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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61272488,No.61402523）

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

李榮佳（1991-），男，山東泗水人，解放軍信息工程大學(xué)碩士生，主要研究方向?yàn)閷?duì)稱密碼設(shè)計(jì)與分析。

金晨輝（1965-），男，河南扶溝人，解放軍信息工程大學(xué)教授，主要研究方向?yàn)槊艽a學(xué)與信息安全。