FOX算法的中间相遇攻击

李荣佳，金晨辉

（解放军信息工程大学三院，河南 郑州 450002）

FOX算法的中间相遇攻击

李荣佳，金晨辉

（解放军信息工程大学三院，河南 郑州 450002）

研究了FOX分组密码算法在中间相遇攻击下的安全性。首先，分别构造了FOX64和FOX128的3轮中间相遇区分器，实施了6轮中间相遇攻击，得到对6轮FOX64和FOX128较好的攻击结果。其次，将FOX128的中间相遇区分器扩展到4轮，并结合时间存储数据折衷的方法，攻击了7轮FOX128，与已有的攻击结果相比，攻击的时间复杂度和存储复杂度略大，而数据复杂度明显降低。

分组密码；密码分析；中间相遇攻击；FOX算法

1 引言

FOX密码算法[1]是由Junod和Vaudenay在2004年提出的系列分组密码算法，分组规模可为64 bit和128 bit，分别记为FOX64和FOX128。FOX密码的整体结构采用Lai-Massey结构，其轮函数采用SPS结构。FOX密码算法在各平台都具有不错的性能，广泛地应用于欧洲有线电视等安全产品中。

对 FOX算法的主要攻击方法有积分攻击、不可能差分攻击、差分—碰撞攻击等。文献[2]利用3轮积分区分器分析了 FOX算法。文献[3]分析了FOX算法抵抗不可能差分攻击的能力。文献[4]构造了4轮区分器并给出了对FOX算法的差分—碰撞攻击结果。文献[5,6]分别对FOX64算法进行了零相关—积分分析和多维零相关线性分析。在 2014年FSE会议上，文献[7]提出的对FOX算法的全子密钥恢复攻击，目前取得对FOX算法的较好攻击结果。

中间相遇攻击由Diffie和Hellman在分析DES算法的安全性时首次提出。近几年，中间相遇攻击被应用于AES算法的分析中，并得到了较好的攻击结果。在文献[8]中，Demirci和Selçuk首次将中间相遇攻击用于分析AES，利用4轮中间相遇区分器攻击了7轮AES-192和8轮AES-256。文献[9]有效地降低了Demirci和Selçuk攻击的存储和时间复杂度。在2013年欧密会上，Derbez等[10]利用中间相遇攻击取得了在单密钥条件下对 AES-128较好的攻击结果。文献[11]利用中间相遇攻击，结合密钥制约关系，攻击了9轮AES-192。

本文着重研究对 FOX算法的中间相遇攻击。首先，本文通过构造3轮的中间相遇区分器，对6轮FOX64和FOX128算法实施了攻击，得到对6轮FOX64和FOX128较好的攻击结果。其次，对于 FOX128，本文将其中间相遇攻击区分器扩展到4轮，并结合时间存储数据折衷的方法，对 7轮FOX128实施了攻击，与已有的攻击结果相比，此攻击的时间复杂度和存储复杂度略大，而数据复杂度明显降低。表1和表2将本文对FOX算法的攻击结果与此前的主要攻击结果进行了对比。

表1 FOX64的主要分析结果

表2 FOX128的主要分析结果

2 预备知识

2.1 符号表示

x||y：x与y级联。

Pi：第i个明文。

S：FOX密码的S盒运算。

X[ i]：X的第i个字节。

X[ i,… ,j]：X的第i个到第j个字节。

X[ i,…,j]=Y[ i,…,j ]：X的第i个到第j个字节与Y的第i个到第j个字节对应相等。

2.2 FOX64密码简介

FOX64采用了16轮迭代的Lai-Massey结构，其第 i轮的 64 bit输入可以表示为 2个 32 bit。类似地，第i轮的64 bit的子密钥Ki也可以表示为2个32 bitFOX64的具体结构如图 1所示。对于令设f32为其轮函数，则

图1 1轮FOX64

轮函数f32采用SPS结构，包括子密钥加、代替变换 sigma4和扩散变换mu4这3个变换，可以表示为

代替变换 sigma4由4个8 bit S盒并置而成，扩散变换mu4是一个4×4的MDS矩阵运算。

2.3 FOX128密码简介

与FOX64类似，FOX128也采用16轮迭代的Lai-Massey结构，其第i轮的128 bit输入表示为4个128 bit的子密钥Ki表示为2个的具体结构如图2所示，设f64为其轮函数，则

图2 1轮FOX128

轮函数 f64与 f32类似，采用SPS结构，包括子密钥加、代替变换 sigma8和扩散变换mu8这3个变换，可以表示为

代替变换 sigma8由8个8 bit S盒并置而成，扩散变换mu8是一个8× 8的MDS矩阵运算。

本文把轮函数 f32和 f64的输入记作x，经过第1层子密钥加、第1层代替变换、扩散变换、第2层子密钥加、第2层代替变换、第3层子密钥加后的状态分别记作 y、z、w、q、r、s。

一轮FOX64算法具有如下性质。

性质1[6]设1轮FOX64的输入为输出为则有

类似地，FOX128算法具有如下性质。

性质2[6]设1轮FOX128的输入为，输出为，则有

3 FOX64的中间相遇攻击

3.1 FOX64的3轮区分器

本文给出FOX64的3轮中间相遇区分器，如图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个字节决定：

图3 FOX64的3轮中间相遇区分器

3.2 FOX64的6轮中间相遇攻击

攻击分为2阶段：预计算阶段和在线阶段。

在线阶段：在线阶段的具体攻击步骤如下。

步骤1选择16个明文满足并获取相应的密文。

步骤 2猜测子密钥脱密16个密文，得到

步骤3由性质1，计算进而得到序列

步骤4检测步骤3中求得的序列是否在预计算表H1中。若在，则判定猜测的密钥为正确密钥；否则，判定为错误密钥。故一个错误密钥通过检测的概率为最终保留的密钥个数为

4 FOX128的中间相遇攻击

4.1 FOX128的3轮区分器

本文给出FOX128的3轮中间相遇区分器，如图4所示。

定理2给定FOX128的25个明文若对这25个明文进行 3轮 FOX128加密，则有序序列只有1522 种可能的取值。

图4 FOX128的3轮中间相遇区分器

4.2 FOX128的6轮中间相遇攻击

攻击分为2阶段：预计算阶段和在线阶段。

在线阶段：在线阶段的具体攻击步骤如下。

步骤1选择25个明文满足并获取相应的密文。

步骤 2猜测子密钥脱密25个密文,得到

步骤3由性质2计算进而得到序列

步骤4检测步骤3中求得的序列是否在预计算表H2中。若在，则判定猜测的密钥为正确密钥；否则，判定为错误密钥。故一个错误密钥通过检测的概率为，最终保留的密钥个数为

4.3 FOX128的7轮中间相遇攻击

在FOX128的3轮中间相遇区分器的中间增加1轮，本文得到如下的4轮中间相遇区分器。

定理3给定FOX128的25个明文，满足若对这25个明文进行 4轮 FOX128加密，则序列只有2802 种可能的取值。

如果本文采用4.2节中的方法，在预计算阶段计算所有的2802 种可能的取值，那么预计算阶段的时间复杂度大约为次7轮FOX128加密，存储复杂度大约为个128 bit，这一复杂度超出了穷举攻击的复杂度。因此，本文利用时间存储数据折衷的方法，预计算阶段，只计算并存储序列的2802 种可能取值中的同时，在线阶段，本文需要选择大约个明文，重复382次攻击。于是正确密钥可以在预计算表中找到匹配的概率变为

也就是说，本文攻击成功的概率为99.97%。经过时间存储数据折衷后，预计算阶段的时间复杂度降低为次7轮FOX128加密，而在线阶段的时间复杂度提高到次7轮FOX128加密，故攻击的时间复杂度约等于在线阶段的时间复杂度。攻击的存储复杂度降低为个128 bit。攻击所需的数据量变为242.6个选择明文。

5 结束语

本文主要研究了对FOX64和FOX128算法的中间相遇攻击，首先，本文分别构造了 FOX64和FOX128的 3轮中间相遇区分器，通过猜测最后 2轮的部分子密钥，利用1轮FOX算法的输入与输出的关系，实施了 6轮攻击，此攻击是目前为止对 6轮FOX64和FOX128较好的攻击结果。其次，本文将FOX128的中间相遇攻击区分器扩展到4轮，并结合时间存储数据折衷的方法，对7轮FOX128实施了攻击，与已有的攻击结果相比，此攻击的时间复杂度和存储复杂度略大，而数据复杂度得到明显降低。

[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 算法的零相关-积分分析[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密码的多维零相关线性分析[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-），男，河南扶沟人，解放军信息工程大学教授，主要研究方向为密码学与信息安全。