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代码）
值得一提的是，差分攻击得到的子密钥组不唯一，但是都可以正确解密。