feal-differential-cryptanalysis

Compare original and translation side by side

🇺🇸

Original

English

🇨🇳

Translation

Chinese

FEAL Differential Cryptanalysis

FEAL 差分密码分析

Overview

概述

This skill provides structured guidance for implementing differential cryptanalysis attacks on FEAL and similar Feistel-network block ciphers. Differential cryptanalysis exploits how specific input differences propagate through cipher rounds with predictable probabilities, enabling key recovery.

本技能为针对FEAL及类似Feistel网络分组密码实现差分密码分析攻击提供结构化指南。差分密码分析利用特定输入差异以可预测概率在密码轮次中传播的特性，实现密钥恢复。

Core Principles

核心原则

Theory Before Implementation

先理论后实现

Before writing any attack code:

Understand the cipher structure - Identify the Feistel network layout, round function (F-function), key schedule, and number of rounds
Study the F-function's differential properties - Determine which input differences produce which output differences with high probability
Identify differential characteristics - Find high-probability differential trails through the cipher rounds
Formulate the attack equations - Understand how key bits relate to observable output differences

在编写任何攻击代码之前：

理解密码结构 - 明确Feistel网络布局、轮函数（F-function）、密钥调度和轮次数量
研究F函数的差分特性 - 确定哪些输入差异会以高概率产生哪些输出差异
识别差分特征 - 找到密码轮次中高概率的差分路径
推导攻击方程 - 理解密钥位与可观测输出差异之间的关系

What Makes Differential Cryptanalysis Work

差分密码分析的工作原理

The attack exploits that for the correct key, decrypted intermediate values represent actual cipher states that satisfy the round function equations. For incorrect keys, these values are essentially random garbage that won't satisfy the differential relationships.

The distinguishing property is consistency with the Feistel structure, not statistical measures like entropy, variance, or Hamming weight.

该攻击利用的特性是：对于正确密钥，解密后的中间值代表满足轮函数方程的实际密码状态；对于错误密钥，这些值本质上是随机的垃圾数据，无法满足差分关系。

区分正确与错误密钥的依据是是否符合Feistel结构的一致性，而非熵、方差或汉明重量等统计指标。

Approach

实施步骤

Step 1: Analyze the Cipher

步骤1：分析密码

Map out the complete cipher structure (rounds, key mixing, F-function)
Identify which key bits affect which intermediate computations
Determine what intermediate values can be computed given partial key guesses
Document dependencies between plaintext, ciphertext, and key bits

梳理完整的密码结构（轮次、密钥混合、F函数）
确定哪些密钥位会影响哪些中间计算
明确给定部分密钥猜测时可计算的中间值
记录明文、密文与密钥位之间的依赖关系

Step 2: Study Differential Properties

步骤2：研究差分特性

Analyze the F-function for differential characteristics
Find input XOR differences that produce predictable output XOR differences
Calculate probabilities for each differential characteristic
Identify high-probability multi-round differential trails

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

Step 3: Design Chosen Plaintexts

步骤3：选择明文对

Select plaintext pairs with specific XOR differences that exploit identified differentials
Ensure plaintext differences align with high-probability characteristics
Document the theoretical basis for each plaintext choice
Avoid arbitrary plaintexts without theoretical justification

选择具有特定异或差异的明文对，以利用已识别的差分特征
确保明文差异与高概率特征匹配
记录每个明文选择的理论依据
避免使用无理论依据的任意明文

Step 4: Implement the Key Recovery

步骤4：实现密钥恢复

For each key candidate, compute the intermediate value using partial decryption
Check if the computed values satisfy the expected differential relationships
Count how many plaintext pairs "vote" for each key candidate
The correct key will have significantly more consistent pairs

对每个候选密钥，通过部分解密计算中间值
检查计算值是否符合预期的差分关系
统计每个候选密钥获得的明文对“支持票数”
正确密钥的一致明文对数量会显著更多

Step 5: Validate Incrementally

步骤5：逐步验证

Verify each component independently before combining
For known test cases, confirm intermediate values match expected states
Compare behavior of correct vs incorrect keys directly
Build confidence in each attack stage before proceeding

在整合前独立验证每个组件
对于已知测试用例，确认中间值与预期状态匹配
直接对比正确密钥与错误密钥的行为
在推进到下一阶段前，确保每个攻击阶段的可靠性

Verification Strategies

验证策略

Direct Comparison Method

直接对比法

When debugging, compute intermediate values for both correct and incorrect keys:

Use a known key to generate test cases
Compute intermediate states for the correct key
Compute intermediate states for several incorrect keys
Identify the distinguishing property empirically

调试时，同时计算正确密钥和错误密钥的中间值：

使用已知密钥生成测试用例
计算正确密钥对应的中间状态
计算多个错误密钥对应的中间状态
凭经验识别区分特征

Equation Verification

方程验证法

For each plaintext pair and key guess:

Compute the alleged intermediate state
Check if state satisfies the expected differential equation
Track pass/fail counts per key candidate
Correct key should have near-100% pass rate for good differentials

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

计算假定的中间状态
检查该状态是否符合预期的差分方程
跟踪每个候选密钥的通过/失败次数
对于优质差分特征，正确密钥的通过率应接近100%

Sanity Checks

合理性检查

With random keys, attack should fail (return wrong answer)
With oracle access, intermediate computations should match actual cipher states
Reducing to fewer rounds should make attack easier
Using more plaintext pairs should improve reliability

使用随机密钥时，攻击应失败（返回错误结果）
若有预言机访问权限，中间计算结果应与实际密码状态匹配
减少轮次应使攻击更容易成功
使用更多明文对应提升攻击可靠性

Common Pitfalls

常见误区

Pitfall 1: Statistical Heuristics Instead of Differential Equations

误区1：用统计启发式替代差分方程

Wrong approach: Using entropy, Hamming weight variance, collision counting, or other statistical measures to distinguish correct from incorrect keys.

Why it fails: These measures often show similar values for correct and incorrect keys. The distinguishing property is structural (satisfying differential equations), not statistical.

Correct approach: Check whether computed intermediate values satisfy the expected differential relationships derived from the cipher's structure.

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

失败原因：这些指标在正确密钥和错误密钥上往往表现相似。区分依据是结构上的（是否满足差分方程），而非统计上的。

正确做法：检查计算出的中间值是否符合从密码结构推导的预期差分关系。

Pitfall 2: Arbitrary Plaintext Selection

误区2：任意选择明文

Wrong approach: Using plaintexts like

i * 0x0101010101010101

or random values without theoretical basis.

Why it fails: Differential attacks require specific plaintext XOR differences that create useful differentials through the cipher.

Correct approach: Choose plaintext pairs where the XOR difference matches high-probability differential characteristics of the F-function.

错误做法：使用诸如

i * 0x0101010101010101

或无理论依据的随机值作为明文。

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

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

Pitfall 3: Repeated Heuristic Cycling

误区3：反复尝试启发式方法

Wrong approach: Trying many different scoring functions (entropy, variance, min/max, collisions) hoping one works.

Why it fails: Without understanding why each approach fails, new attempts are equally likely to fail.

Correct approach: When an approach fails, analyze why. Compare correct vs incorrect key behavior directly. Build understanding incrementally.

错误做法：尝试多种不同的评分函数（熵、方差、最小/最大值、碰撞），寄希望于其中一种有效。

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

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

Pitfall 4: Ignoring Cipher-Specific Literature

误区4：忽略密码相关文献

Wrong approach: Implementing a generic "differential attack" without studying FEAL's specific weaknesses.

Why it fails: FEAL has well-documented differential characteristics. Ignoring this domain knowledge means reinventing the wheel poorly.

Correct approach: Research existing differential attacks on the specific cipher. Understand which differentials have been proven effective.

错误做法：在未研究FEAL特定弱点的情况下，实现通用的“差分攻击”。

失败原因：FEAL的差分特征已有详尽文献记载。忽略该领域知识意味着低效地重复造轮子。

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

Pitfall 5: Incomplete Partial Decrypt Verification

误区5：未完整验证部分解密

Wrong approach: Assuming partial decryption code is correct without verification against known intermediate states.

Why it fails: Bugs in partial decryption produce meaningless intermediate values, making the attack impossible regardless of the distinguisher.

Correct approach: For a known key, verify that computed intermediate values match the actual cipher's internal states at each round.

错误做法：在未与已知中间状态对比验证的情况下，假设部分解密代码是正确的。

失败原因：部分解密中的漏洞会产生无意义的中间值，无论区分器设计如何，都会导致攻击失败。

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

Key Insights for FEAL-Specific Attacks

针对FEAL攻击的关键见解

Round key independence: Different round keys may affect different intermediate values. Identify which computations depend on the target key bits.
Seed constraints: If key generation uses a small seed space (e.g., 16-bit), exhaustive search is feasible but still requires a reliable distinguisher.
L/R state separation: In Feistel networks, the left and right halves have different dependencies. Exploit this to isolate key bit effects.
F-function weaknesses: FEAL's F-function has known differential weaknesses. Input difference
```
0x80800000
```
through the F-function has specific high-probability output differences.

轮密钥独立性：不同的轮密钥可能影响不同的中间值。确定哪些计算依赖于目标密钥位。
种子约束：若密钥生成使用小种子空间（如16位），穷举搜索是可行的，但仍需可靠的区分器。
L/R状态分离：在Feistel网络中，左右半部分具有不同的依赖关系。利用这一点来隔离密钥位的影响。
F函数弱点：FEAL的F函数存在已知的差分弱点。输入差异
```
0x80800000
```
通过F函数会产生特定的高概率输出差异。