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.