由Feal-4密码算法浅谈差分攻击

Feal-4密码算法在密码分析史上有重要的地位，差分分析就是针对该算法首次提出，是一个很好的学习范例。*ctf2019就有一道相关的问题。可能是由于已经不存在现实应用，探讨该问题的中文文档非常少，详细分析对Feal-4进行差分攻击的我还没有看到。因此笔者将自己的分析总结与大家分享。

一、Feal-4 加密算法

1.1 Feal密码概述

Fea加密算法由日本NTT公司于1987年发明，该算法的全称是 Fast data Encryption ALgorithm。Feal密码的最初版本就是Feal-4，后来由陆续推出了Feal-8和Feal-N。该算法提出后，经过密码学家的研究，陆续发现了该算法的一些脆弱性，即使是后续版本也存在一定程度的不安全性。

本文我们主要讨论Feal-4，分析该密码算法的脆弱性及差分攻击方法。

Feal-4密码算法在密码学史上有很重要的地位，差分攻击正是研究者通过对Feal-4的研究首次提出的，之后又拓展到了DES密码算法上。自此以后，抗差分分析成了密码设计的一部分，差分分析成为了密码分析的基本方法。

由于Feal-4的自身的设计特点，差分攻击对Feal-4非常有效，不需要大量的选择明文就可以实现。

关于对Feal-4的差分分析，博客 http://theamazingking.com/crypto-feal.php 有比较详细的阐述， 我自己在分析时也参考了该博客的内容，感谢作者的分享。

通过进一步学习我发现，有比该博客上的方法更高效的方式进行差分攻击。第一，该博客使用的方法，子密钥枚举空间是2的32次方，如果用 Python 实现，运行的时间久到无法承受，本文使用的方法枚举空间是2的17次方，能大大节约了破解时间。第二，该博客中讲到，子密钥K0不能使用差分方法求得，通过测试我发现是可以的，需要稍微改动求解方式，基本与前3轮子密钥的破解相同。这样破解K0也能使用枚举2的17次方的方法。

1.2 Feal-4密码算法加解密流程

Feal-4属于分组加密算法，采用Feistel架构。密钥长度为8字节，分组长度也是8字节。Feal-4密码算法对一个分组的加密过程可用下面的图描述

首先，8字节的密钥经过子密钥生成算法，扩展为6个4字节的子密钥 K0 – K5，加密过程使用的就是这样6个4字节子密钥。所以如果能恢复出子密钥，不需要恢复原始密钥，就能完成对Feal-4的解密，下文的差分攻击也正是这样做的。

分组加密过程中，首先8字节明文分组被分成左右两个部分，左半部与子密钥K4异或，右半部与子密钥K5异或。两个半部再异或作为右半部。接着进入4轮轮函数。每一轮里，右半部直接成为下一轮的左半部。

第一轮里，右半部与K0异或，然后进入F函数，F函数实现非线性部分，F函数的结果与左半部进行异或，成为下一轮的右半部。后3轮同理，依次使用子密钥 K1 K2 K3。

4轮操作完成后，左半部就是密文分组的左半部，左半部与右半部异或后，成为密文分组的右半部。这就是一个分组的加密过程。解密过程就是上述过程的逆过程。

1.3 轮函数

下面我们来看F函数。Feal-4的脆弱性就在F函数中。轮函数F将32比特映射为32比特。轮函数中使用了一个名为G函数的操作，G函数有两个定义如下

G0和G1，接收两个参数 a 和 b，将a+b的值加0或加1，模256后（避免超出一个字节的长度），进行循环左移位，移2位。定义完G函数，轮函数F可用下图描述

如果说轮函数F是Feal-4的核心，G函数就是F函数的核心。

二、对 Feal-4 进行差分攻击

接下来我们开始对Feal-4进行差分攻击。差分分析的目标是获得加密的子密钥。

差分分析最早由Murphy于1990年，针对Feal4密码提出，随后 Biham 和 Shamir 又在一系列研究里对该技术进行了发展，属于选择明文攻击，适用于过度使用异或操作的分组密码算法。

所谓差分分析，是指追踪明文对的“差异”的传播。这里的“差异”由我们根据目标进行定义，可以是异或值，也可以是其它。针对Feal-4，我们使用的就是异或值定义“差异”，或者称之为“距离”。有些地方也称为“特征”（characteristic）

比如说，选定明文分组P1，分组之间的“差值”（differential）为δ，于是另一个明文分组就是P1+δ，明文P1对应的密文分组时C1，明文 P1+δ 对应的密文与C1的“距离”是 ε

如果 δ 以一定的概率对应着 ε ，就称 δ 是一个差分特征。

其实这个过程我们主要关注的是非线性部分F函数，所以也可以用下面的图描述这个过程，右侧可认为是一种简要描述

在Feal-4密码里，有这样两个有用的“特征”，第一个，同样的输入经过轮函数F一定产生同样的输出，即，当轮函数的输入差值为0x00000000时，轮函数的输出差值一定时0x00000000，概率为1。第二个，当轮函数的输入差值为0x80800000时，轮函数的输出差值一定时0x02000000，概率为1。

基于这样一个事实，我们来追踪差分特征0x8080000080800000在Feal-4加密过程的传播。

我们可以任意选择一个明文分组P0，然后与0x8080000080800000异或，得到明文分组P1，P0与P1构成一个明文对，差值为0x8080000080800000 对应的密文分组分别是C0和C1，记

追踪差分特征 P’ 在Feal-4中的传播，过程如下

上述差值进入Feal-4后，我们可以追踪差值到第3轮，此后由于差值0x02000000对应的轮函数差值不确定，才中断。但是，密文分组我们是知道的（选择明文攻击），因此，L’ 和 R’ 是已知的，我们可以从密文倒推，看倒推到差值追踪中断的地方

Y' = L' ^ R'
Z' = 0x02000000 ^ L'
X' = 0x80800000 ^ Y'

由上面三行，我们已经倒推到X’了，于是整个流程里的差分值，我们都是清楚的。L’ R’ X’ Y’ Z’ 都是已知的。

请注意轮函数的输出差值Z’，马上就要用到。

结合实际加密流程图，我们还可以通过猜解K3，计算实际的Z0和Z1，从而获得实际的 Z0 ^ Z1

Y0 = L0 ^ R0
Y1 = L1 ^ R1
Z0 = F(Y0 ^ K3)
Z1 = F(Y1 ^ K3)

所以现在我们有了一个K3的方程，

差分分析得到实际的 Z’ = 0x02000000 ^ L’

猜解K3得到可能的 Z’ = Z0 ^ Z1 = F(Y0 ^ K3) ^ F(Y1 ^ K3)

如果猜解的K3正确，那么这两个值应该相等，由此我们就可以爆破出K3，爆破需要枚举的空间是4个字节，即2的32次方。爆破出K3后，使用K3以及 L、R，可以恢复出第四轮加密前的数据，即第三轮加密的结果

L3 = Y
R3 = L4 ^ F(Y ^ K3)

使用L3和R3继续上面的过程，可以猜解出K2。这个过程需要改变的是使用的差分特征，猜解K3时使用的差分特征是0x8080000080800000，猜解K2时使用差分特征 0x0000000080800000，可以像K3那样构建方程

由于K3已知，可以算出此时的Y0和Y1

Y0 = L ^ F(K3 ^ R0 ^ L0)

Y1 = L ^ F(K3 ^ R1 ^ L1)

同理可以由差分数据流得到Z’

Z’ = L3’ ^ 0x02000000

其中 L3’ = R4’ = L’ ^ R’

此时猜解K2，构建Z’的等式

Z’ = F(Y0 ^ K2) ^ F(Y1 ^ K2)

Z’ = L3’ ^ 0x02000000

得到K2

同理，用差分特征0x00000000 02000000 可以求解出K1

那么如何求解K0和K4、K5呢？theamazingking 博客上讲到，无法使用差分方法求解K0，只能直接猜解K0，然后求出对应的K4和K5，然后使用其他选择明文分组验证猜解的K0 K4 K5 正确性。经过测试我发现其实是可以使用差分的方式求K0的。

还是使用差分特征0x0000000002000000，此时构建K0的方程针对 X’ 构建。有了K3 K2 K1后，我们就有了第一轮加密的左右输出，从而有了L1’ 和 R1’，于是

X' = L1' ^ 0x00000000 = L1'

另一方面，猜解K0，得到

X0 = F(R1_0 ^ K0)
X1 = F(R1_1 ^ K0)
X' = X0 ^ X1

我们同样可以得到K0的等式。

提高破解速度

上述过程已经可以实现子密钥的恢复，但是枚举空间是2的32次方，theamazingking的 C demo 程序就是使用的这种算法。C程序的运行时间已经较慢了，使用Python实现破解程序，速度慢到无法承受。得益于Feal-4轮函数的设计，我们还能以更快的速度找到子密钥，方法如下

首先定义M函数，针对4字节输入产生4字节输出，如下

其中z表示zero,0x00

然后对所有可能的四字节序列，计算 Q0 和 Q1

此时有这样的结论：如果A恰好等于M(K3)，那么下面的式子成立

将式子展开，就能看到等式左右两边相等

基于这种方式，我们可以将猜解子密钥的过程分为两步。

第一步，猜解16位的M(K3)，即 M(K3) = (0, a0, a1, 0) ，猜解的空间是2的16次方

通过上述步骤得到 Q0 和 Q1，然后与 Z’ 建立方程，

Q0 ^ Q1 = F[ M(Y0) ^ (0, a0, a1, 0) ] ^ F[ M(Y1) ^ (0, a0, a1, 0) ]
Z' = L' ^ 0x02000000
Q0 ^ Q1 的8-23位 = Z' 的8-23位

通过上述三行式子，枚举全部的 M(K3)，得到所有可能的 M(K3)

第二步，根据 K3 = (c0, c0^a0, c1^a1, c1) ，继续猜解 c0 c1两个字节，猜解方式依然是基于Z’构建等式，猜解的空间是2的16次方，就可以得到完整的子密钥 K3。

通过这种子密钥求解方式，两次2的16次方的枚举，共2的17次方的枚举次数，就可以求解出子密钥K3，K2 K1 K0的求解方式一样。实际测试中，效率提升非常明显。

以上就是对Feal-4的差分攻击过程。上述分析过程仍然有可以改进的地方，比如选择明文的数量。以及使用破解K0的方式，用同一组选择明文破解K3 和 K2，第二组选择明文破解K1 和 K0，这样需要的选择明文数更少。由于时间原因我没有再做测试。

三、实例

*ctf 2019 的 notfeal 问题就是这样一个使用差分方式攻击Feal密码的例子。不过该程序对原始Feal-4进行了改动。有以下两点

第一，F函数的输出被逆序了。

第二，Feistel架构左右颠倒了。

只要理解了差分攻击的过程，不难调整差分过程，完成攻击。

由于输出逆序，三轮使用的差分特征要调整为

1.0×0000000080800000

2.0×8080000080800000

3.0×0000000200000002

该问题限定的选择明文数量是50组，实际上使用36组就可以成功。

代码很乱就不放了。可参考 sixstar 在github上的官方 writeup（该wp使用的就是theamazingking的C代码）

值得一提的是，差分攻击得到的子密钥组不唯一，但是都可以正确解密。