差分攻击 FEAL-4：从原理到实现

发表于 Disqus：

这篇文章主要介绍了如何对传统分组密码算法 FEAL-4 进行差分分析（Differential Cryptanalysis），并展示了攻击进程和关键实现细节。文中还包含了部分实验数据和攻击结果，可供有兴趣的读者参考或复现。

您可以在这里找到本文中涉及到的源代码： https://github.com/linanwx/FEAL-4-Differential-Cryptanalysis 。

本文章基于 Dublin City University(DCU) CSC1132/CA642 课程内容撰写。

两张重要图片

在正式展开分析之前，先给出两张与 FEAL-4 密切相关的图片，方便对差分传播和整体加密流程有一个直观认识。

  1. 差分传播示意图
    下图展示了在 FEAL-4 中，明文差分（XOR 形式）如何在加密轮次中传播并最终反映到密文上。

  2. FEAL-4 工作流示意图
    下图是 FEAL-4 的整体加密框架示意，包括明文的左右分块、各轮子密钥注入以及 F 函数的运用流程。

F 函数的特性

FEAL-4 的轮函数（即 F 函数）可以视作对 32 位输入进行某种随机化排列（Permutation）。在差分分析中，我们并不需要 F 的具体实现，而更关注它的两个关键差分属性：

  • 若 ，则 。
  • 若 ，则 。

有了这两个结论，在后续分析时就能推断特定差分输入下的输出表现，从而帮助定位子密钥。

差分路径的详细分析

假设我们选择一对特殊的明文 和 ，满足：

这个特定差分向量有助于简化 FEAL-4 若干轮次输出中的差分计算。

1. 初始轮次差分推导

  • 令 表示 的左右分块（同理 表示 的左右分块）。

  • 经过第一轮的异或操作后：

    同理可推出右半部分的差分。

  • 进一步由于加密时存在 “额外一轮 XOR”，可得到：

    这意味着在后续计算中，差分会以更简单的形式得以归并。

2. 后向差分计算（Backward Calculation）

当我们获得明文对 与对应的密文对 后，可以进一步进行后向推导。令密文记作 ，则：

  • 计算出 ，得到 。
  • 根据已知差分性质，可在末轮逐步还原 、、 等中间变量。
  • 利用这些结果便可对各子密钥展开攻击或验证。

攻击 K3

在差分分析中，往往先从某个中间轮次子密钥开始，例如 。具体步骤如下：

  1. 选取明文对： 我生成了 12 对满足

    的随机明文。
  2. 加密并提取差分： 将上述明文对加密后，得到相应的密文对；结合差分路径推导出 、、 等中间值。
  3. 遍历 ：

    只要找到满足差分方程 的候选即保留。

通过这种方法，我成功得到四个候选子密钥：

1
cfa38976, cfa309f6, 4f238976, 4f2309f6

执行以上过程的命令示例为：

1
./main -mode=attackk3 -file=K3.txt

该实现与我在 www.theamazingking.com 上介绍的方法一致。

攻击 K2

在拿到 的若干候选后，可以继续推算 。其核心方程：

其中 来自于上一轮运算（包括对 、 等的进一步计算）。同样地：

  1. 生成明文对，满足差分条件
  2. 抓取加密后密文差分，通过遍历所有可能 值，检查是否能满足差分约束 。
  3. 命令示例：
    1
    ./main -mode=attackk2 -file=K2.txt -k3=cfa38976,cfa309f6,4f238976,4f2309f6
  4. 最终输出示例如下所示：
    1
    2
    3
    4
    5
    Candidate K2: 8b722e41 (K3: cfa38976)
    Candidate K2: 8b72aec1 (K3: cfa38976)
    ...
    Candidate K2: 89722e43 (K3: 4f2309f6)
    Candidate K2: 8972aec3 (K3: 4f2309f6)

攻击 K1

类似地，攻击 也可以按前面流程来做。
为了让差分路径能稳定呈现预期结果，我生成了 12 对满足

的明文，并验证其加密输出。

命令示例：

1
./main -mode=attackk1 -file=K1.txt -k3k2="cfa38976,8b722e41; cfa38976,8b72aec1; ..."

可一次性将前面得到的所有 候选组合带入，最终找到对应的 候选。

攻击 K0, K4, K5

当 全部到手后，就可以反推最后一轮所需的 。
设最终加密得到的左、右部分为 。对应的明文分块为 。则有：

只要枚举所有可能的 ，即可通过上述方程解出相应的 与 。然后用其他明文-密文对交叉验证正确性。若都满足，则得到正确的最终密钥集。

命令示例：

1
./main -mode=attackk0k4k5 -k3k2k1="..." -file=K1.txt -file2=K1_p.txt

实现、优化与验证

1. 自动化生成与并行计算

  • 自动生成随机明文对：在代码中事先控制 XOR 差分，即可批量输出满足需求的明文文件（如 K3_p.txt, K2_p.txt, K1_p.txt）。
  • 并行化搜索：使用 Go 语言的 Goroutines，开启 10 个并行任务，在带有 10 核的 Mac 上最大化利用 CPU 资源。
  • 进度条与可视化：通过 progressbar 库实时显示搜索进度，让实验过程更直观。

2. 验证方法

  • 本地自定义密钥测试
    先选定一套已知的 –（如 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020），对前面生成的明文对进行加密，并重复差分分析过程，看是否能在结果中匹配这套密钥。
    实验证明能够正确还原这组测试密钥，从而确认代码逻辑的准确性。

  • 特定明文-密文对测试
    选定一个明文 1234567890abcdef 和在 Einstein Zone 生成的密文 f43ae3eeb56e2bbf，验证最终得到的 256 组候选 – 中，每一组都可重现这条加密映射，进一步确认攻击流程无误。

最终结果

所有解出的 – 存放于 final_result.txt。去重后包括以下范围：

Possible Values for K0

1
2
890c2148 890ca1c8 098c2148 098ca1c8 ...
0b8c214a 0b8ca1ca 8b0c214a 8b0ca1ca

Possible Values for K1

1
2
471f077e 471f87fe c79f077e c79f87fc ...
451f077c 451f87fc c59f077c c59f87fc

Possible Values for K2

1
2
8b722e41 8b72aec1 8b722e43 8b72aec3 ...
89722e43 8972aec3

Possible Values for K3

1
cfa38976 cfa309f6 4f238976 4f2309f6

Possible Values for K4

1
89eb0024 89eb0026 8beb0024 8beb0026

Possible Values for K5

1
b85e6bc0 b85e6bc2 ba5e6bc0 ba5e6bc2

借助差分分析，我们最终能获得一批子密钥候选集。与现代分组密码（AES 等）相比，FEAL-4 的轮数较少、结构也更为简洁，因此在教学和研究中非常适合用于演示差分分析思路。

总结

本文详细展示了对 FEAL-4 进行差分攻击的完整流程，包括从差分路径设计、生成明文对、中间子密钥 () 攻击，再到最后对 的逆向求解。同时也介绍了代码实现过程中的几处优化和验证方法。
FEAL-4 算法因为较低的轮数和简单的结构为差分分析提供了便利。然而对于现代更安全、更复杂的分组算法，同样的分析思路也至关重要。本案例希望对密码学的学习者和研究者有所启发，如有任何问题或改进方案，欢迎在评论区讨论交流！