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

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

两张重要图片

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

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

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

F 函数的特性

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

  • 若 $X \oplus Y = 0$，则 $F(X) = F(Y)$。
  • 若 $X \oplus Y = 0x80800000$，则 $F(X) \oplus F(Y) = 0x02000000$。

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

差分路径的详细分析

假设我们选择一对特殊的明文 $P_0$ 和 $P_1$，满足： $$ P_0 \oplus P_1 = 0x8080000080800000 = P^{\prime}. $$ 这个特定差分向量有助于简化 FEAL-4 若干轮次输出中的差分计算。

1. 初始轮次差分推导

  • 令 $(L0_0, R0_0)$ 表示 $P_0$ 的左右分块（同理 $(L0_1, R0_1)$ 表示 $P_1$ 的左右分块）。

  • 经过第一轮的异或操作后： $$ L1_0 \oplus L1_1 = (L0_0 \oplus K4) \oplus (L0_1 \oplus K4) = L0_0 \oplus L1_0 = 0x80800000. $$ 同理可推出右半部分的差分。

  • 进一步由于加密时存在 “额外一轮 XOR”，可得到： $$ R2_0 \oplus R2_1 = (R1_0 \oplus L1_0) \oplus (R1_1 \oplus L1_1) = 0x80800000 \oplus 0x80800000 = 0. $$ 这意味着在后续计算中，差分会以更简单的形式得以归并。

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

当我们获得明文对 $(P_0, P_1)$ 与对应的密文对 $(C_0, C_1)$ 后，可以进一步进行后向推导。令密文记作 $(L, R)$，则：

  • 计算出 $C^{\prime} = C_0 \oplus C_1$，得到 $(L^{\prime}, R^{\prime})$。
  • 根据已知差分性质，可在末轮逐步还原 $X^{\prime}$、$Y^{\prime}$、$Z^{\prime}$ 等中间变量。
  • 利用这些结果便可对各子密钥展开攻击或验证。

攻击 K3

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

  1. 选取明文对： 我生成了 12 对满足
    $$ P_0 \oplus P_1 = 0x8080000080800000 $$
    的随机明文。
  2. 加密并提取差分： 将上述明文对加密后，得到相应的密文对；结合差分路径推导出 $Y_0$、$Y_1$、$Z^{\prime}$ 等中间值。
  3. 遍历 $K_3$：
    $$ Z^{\prime} = Z_0 \oplus Z_1 = F(Y_0 \oplus K_3) \oplus F(Y_1 \oplus K_3). $$
    只要找到满足差分方程 $= 0x02000000$ 的候选即保留。

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

cfa38976, cfa309f6, 4f238976, 4f2309f6

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

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

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

攻击 K2

在拿到 $K_3$ 的若干候选后，可以继续推算 $K_2$。其核心方程： $$ X’ = X_0 \oplus X_1 = F(U_0 \oplus K_2) \oplus F(U_1 \oplus K_2), $$ 其中 $U$ 来自于上一轮运算（包括对 $Y$、$Z$ 等的进一步计算）。同样地：

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

攻击 K1

类似地，攻击 $K_1$ 也可以按前面流程来做。
为了让差分路径能稳定呈现预期结果，我生成了 12 对满足
$$ P_0 \oplus P_1 = 0x0000000002000000 $$
的明文，并验证其加密输出。

命令示例：

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

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

攻击 K0, K4, K5

当 $K_3, K_2, K_1$ 全部到手后，就可以反推最后一轮所需的 $K_0, K_4, K_5$。
设最终加密得到的左、右部分为 $L_0, R_0$。对应的明文分块为 $PL, PR$。则有：

  • $PL \oplus K_4 = LR_0$
  • $PR \oplus K_5 = RR_0$
  • $RR_0 \oplus LR_0 = R_0$
  • $f(R_0 \oplus K_0) \oplus L_0 = LR_0$

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

命令示例：

./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. 验证方法

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

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

最终结果

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

Possible Values for K0 

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

Possible Values for K1 

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

Possible Values for K2 

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

Possible Values for K3 

cfa38976 cfa309f6 4f238976 4f2309f6

Possible Values for K4 

89eb0024 89eb0026 8beb0024 8beb0026

Possible Values for K5 

b85e6bc0 b85e6bc2 ba5e6bc0 ba5e6bc2

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

总结

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

comments powered by Disqus
© 2025 Nansen Li（李楠森）
使用 Hugo 构建
主题 Stack 由 Jimmy 设计