feal-differential-cryptanalysis

FEAL 差分密码分析

概述

此技能为实施针对 FEAL 及类似 Feistel 网络分组密码的差分密码分析攻击提供结构化指导。差分密码分析利用特定输入差分在密码各轮中以可预测的概率传播这一特性，从而恢复密钥。

核心原则

理论先行，再实现

编写任何攻击代码之前：

1. 了解密码结构——确定 Feistel 网络布局、轮函数（F 函数）、密钥调度和轮数
2. 研究 F 函数的差分特性——确定哪些输入差分会以较高概率产生哪些输出差分
3. 识别差分特征——找到通过密码各轮的高概率差分路径
4. 建立攻击方程——了解密钥位与可观测输出差分之间的关系

差分密码分析的原理

该攻击利用了以下特性：对于正确密钥，解密得到的中间值代表实际密码状态，并满足轮函数方程。对于错误密钥，这些值基本上是随机数据，不会满足差分关系。

区分它们的关键在于是否符合 Feistel 结构，而非熵、方差或汉明重量等统计指标。

方法

步骤 1：分析密码

1. 梳理完整的密码结构（轮、密钥混合、F 函数）
2. 确定哪些密钥位会影响哪些中间计算
3. 确定在给定部分密钥猜测的情况下可以计算哪些中间值
4. 记录明文、密文和密钥位之间的依赖关系

步骤 2：研究差分特性

1. 分析 F 函数的差分特征
2. 找出能产生可预测输出异或差分的输入异或差分
3. 计算每种差分特征的概率
4. 识别高概率的多轮差分路径

步骤 3：设计选择明文

1. 选择具有特定异或差分的明文对，以利用已识别的差分
2. 确保明文差分与高概率特征相符
3. 记录每个明文选择的理论依据
4. 避免在没有理论依据的情况下随意选择明文

步骤 4：实现密钥恢复

1. 对于每个候选密钥，使用部分解密计算中间值
2. 检查计算出的值是否满足预期的差分关系
3. 统计有多少明文对为每个候选密钥“投票”
4. 正确密钥对应的匹配对数量会显著更多

步骤 5：逐步验证

1. 在组合各部分之前，分别验证每个组件
2. 对于已知测试用例，确认中间值与预期状态相符
3. 直接比较正确密钥与错误密钥的行为
4. 在继续下一阶段之前，先确认当前攻击阶段可靠

验证策略

直接比较法

调试时，分别计算正确密钥和错误密钥对应的中间值：

1. 使用已知密钥生成测试用例
2. 计算正确密钥对应的中间状态
3. 计算若干错误密钥对应的中间状态
4. 通过实测确定区分特性

方程验证

对于每个明文对和密钥猜测：

1. 计算推定的中间状态
2. 检查该状态是否满足预期的差分方程
3. 统计每个候选密钥的通过／失败次数
4. 对于效果良好的差分，正确密钥的通过率应接近 100%

合理性检查

1. 使用随机密钥时，攻击应当失败（返回错误答案）
2. 通过预言机访问时，中间计算结果应与实际密码状态相符
3. 减少轮数应使攻击更容易
4. 使用更多明文对应该能提高可靠性

常见陷阱

陷阱 1：使用统计启发式方法，而非微分方程

错误做法：使用熵、汉明重量方差、碰撞计数或其他统计指标来区分正确密钥和错误密钥。

失败原因：正确密钥和错误密钥的这些指标往往相近。区分它们的特性是结构性的（是否满足微分方程），而非统计性的。

正确做法：检查计算出的中间值是否满足根据密码结构推导出的预期微分关系。

陷阱 2：任意选择明文

错误做法：使用 i * 0x0101010101010101 之类的明文，或缺乏理论依据的随机值。

失败原因：差分攻击需要特定的明文异或差分，以便在密码中产生有用的差分。

正确做法：选择异或差分符合 F 函数高概率差分特征的明文对。

陷阱 3：反复尝试各种启发式方法

错误做法：不断尝试不同的评分函数（熵、方差、最小值/最大值、碰撞计数），希望其中某个能奏效。

失败原因：如果不理解每种方法失败的原因，新的尝试同样很可能失败。

正确做法：方法失败时，分析失败原因。直接比较正确密钥与错误密钥的行为，逐步建立理解。

陷阱 4：忽略密码特定的文献

错误做法：不研究 FEAL 的特定弱点，就直接实现一种通用的“差分攻击”。

失败原因：FEAL 的差分特征已有详尽记录。忽略这些领域知识，就会低效地重复造轮子。

正确做法：研究针对特定密码的现有差分攻击，了解哪些差分已被证明有效。

陷阱 5：未完整验证部分解密

错误做法：不对照已知中间状态进行验证，就假定部分解密代码正确。

失败原因：部分解密中的错误会产生毫无意义的中间值，无论区分器如何设计，攻击都无法成功。

正确做法：对于已知密钥，验证计算出的中间值是否与密码在每一轮的实际内部状态一致。

FEAL 特定攻击的关键要点

1. 轮密钥独立性：不同轮密钥可能影响不同的中间值。确定哪些计算依赖于目标密钥位。

2. 种子约束：如果密钥生成使用较小的种子空间（例如 16 位），穷举搜索是可行的，但仍需要可靠的区分器。

3. L/R 状态分离：在 Feistel 网络中，左右两半的依赖关系不同。利用这一点隔离密钥位的影响。

4. F 函数弱点：FEAL 的 F 函数存在已知的差分弱点。输入差分 0x80800000 经过 F 函数时，会产生特定的高概率输出差分。

调试检查清单

攻击返回错误结果时：

• 验证部分解密是否能为已知密钥计算出正确的中间值
• 确认明文对具有预期的异或差分
• 检查微分方程是否正确描述了轮结构
• 使用调试输出比较正确密钥与错误密钥的投票计数
• 验证 F 函数的实现是否符合密码规范
• 使用较少的轮数进行测试，以确定攻击从何处开始失效