Back to Details

feal-linear-cryptanalysis

Compare original and translation side by side

🇺🇸

Original

English
🇨🇳

Translation

Chinese

FEAL Linear Cryptanalysis

FEAL线性密码分析

Overview

概述

This skill provides structured guidance for performing linear cryptanalysis on FEAL (Fast Data Encipherment Algorithm) and similar Feistel-based ciphers. Linear cryptanalysis exploits linear approximations of the cipher's non-linear components to recover key bits with far fewer operations than brute force.
本技能为对FEAL（快速数据加密算法）及类似基于Feistel结构的密码执行线性密码分析提供结构化指导。线性密码分析利用密码非线性组件的线性近似，以远少于暴力破解的运算量恢复密钥位。

Critical Pre-Implementation Analysis

关键的预实现分析

Before writing any code, complete these analysis steps:
在编写任何代码之前，请完成以下分析步骤：

1. Identify the Attack Type from Task Description

1. 从任务描述中确定攻击类型

When a task explicitly mentions "linear attack" or "linear cryptanalysis":
  • This is a strong hint about the intended solution approach
  • Do NOT ignore this hint in favor of brute-force methods
  • Linear cryptanalysis is likely the only feasible approach
当任务明确提及“线性攻击”或“线性密码分析”时：
  • 这是关于预期解决方案方法的强烈提示
  • 请勿忽略此提示而选择暴力破解方法
  • 线性密码分析很可能是唯一可行的方法

2. Complexity Feasibility Check

2. 复杂度可行性检查

Before implementing any approach, calculate its feasibility:
Key SpaceOperationsTime at 10^9 ops/secFeasible?
2^20~1 million< 1 secondYes
2^40~1 trillion~18 minutesMaybe
2^64~10^19~292 yearsNo
2^80~10^24~38 million yearsNo
If the combined key space exceeds 2^40, brute force is infeasible. Linear cryptanalysis is required.
在实现任何方法之前，请计算其可行性：
密钥空间运算量每秒10^9次运算时的耗时可行？
2^20~100万次< 1秒是
2^40~1万亿次~18分钟可能
2^64~10^19次~292年否
2^80~10^24次~3800万年否
如果组合密钥空间超过2^40，暴力破解不可行，必须使用线性密码分析。

3. Analyze the Cipher Structure

3. 分析密码结构

Before implementing, thoroughly understand:
  1. Round function (F-function): Identify the non-linear components (S-boxes, G-function)
  2. Key schedule: Understand how round keys derive from the master key
  3. Number of rounds: Fewer rounds = easier linear approximations
  4. Known pairs available: Linear cryptanalysis effectiveness scales with available pairs
在实现之前，请彻底理解：
  1. 轮函数（F函数）：识别非线性组件（S盒、G函数）
  2. 密钥调度：了解轮密钥如何从主密钥派生
  3. 轮数：轮数越少，线性近似越容易
  4. 可用的已知对：线性密码分析的有效性随可用对的数量增加而提升

Linear Cryptanalysis Approach

线性密码分析方法

Step 1: Study the Non-Linear Components

步骤1：研究非线性组件

For FEAL-type ciphers, analyze the G-function:
  • Identify rotation operations
  • Locate addition operations (mod 256)
  • Find the one-byte truncation points
These operations have known linear approximations with varying biases.
对于FEAL类型的密码，分析G函数：
  • 识别旋转操作
  • 定位加法操作（模256）
  • 找到单字节截断点
这些操作具有已知的、不同偏差的线性近似。

Step 2: Find Linear Approximations

步骤2：寻找线性近似

Linear approximations relate input bits, output bits, and key bits with a probability ≠ 0.5:
P[input_mask · plaintext ⊕ output_mask · ciphertext ⊕ key_mask · key = 0] = 0.5 + ε
Where ε (bias) determines attack effectiveness. Larger |ε| = fewer pairs needed.
For FEAL specifically:
  • The G-function addition has exploitable linear properties
  • Carry propagation in addition creates predictable bit relationships
  • Common approximation: MSB of (a + b) ≈ MSB(a) ⊕ MSB(b) with bias ~0.25
线性近似将输入位、输出位和密钥位以概率≠0.5关联起来：
P[input_mask · plaintext ⊕ output_mask · ciphertext ⊕ key_mask · key = 0] = 0.5 + ε
其中ε（偏差）决定攻击的有效性。|ε|越大，所需的明文-密文对越少。
针对FEAL的具体情况：
  • G函数的加法具有可利用的线性特性
  • 加法中的进位传播会产生可预测的位关系
  • 常见近似：(a + b)的最高有效位 ≈ MSB(a) ⊕ MSB(b)，偏差约为0.25

Step 3: Chain Approximations Across Rounds

步骤3：跨轮链接近似

Use the piling-up lemma to combine approximations:
  • If individual rounds have biases ε₁, ε₂, ..., εₙ
  • Combined bias: ε_total = 2^(n-1) × ε₁ × ε₂ × ... × εₙ
使用堆积引理组合近似：
  • 如果各轮的偏差为ε₁, ε₂, ..., εₙ
  • 组合偏差：ε_total = 2^(n-1) × ε₁ × ε₂ × ... × εₙ

Step 4: Key Recovery Process

步骤4：密钥恢复过程

  1. For each candidate key (or key portion):
    • Count how many pairs satisfy the linear approximation
    • The correct key produces a count significantly different from N/2
  2. Use multiple approximations to recover different key bits
  3. Verify recovered key bits against all available pairs
  1. 对于每个候选密钥（或密钥部分）：
    • 统计有多少对满足线性近似
    • 正确的密钥会产生明显偏离N/2的计数
  2. 使用多个近似来恢复不同的密钥位
  3. 针对所有可用对验证恢复的密钥位

Verification Strategies

验证策略

Incremental Verification

增量验证

  1. Verify understanding first: Manually trace the cipher with a known pair
  2. Test approximations: Confirm linear approximations hold with expected bias
  3. Partial key verification: As key bits are recovered, verify against all pairs
  4. Full decryption test: Only after complete key recovery, decrypt all ciphertexts
  1. 先验证理解：手动跟踪已知对的密码运算过程
  2. 测试近似：确认线性近似符合预期偏差
  3. 部分密钥验证：在恢复密钥位的过程中，针对所有对进行验证
  4. 完整解密测试：仅在恢复完整密钥后，解密所有密文

Statistical Validation

统计验证

  • With N pairs, expect count deviation of ~N × |ε| for correct key
  • Wrong keys produce counts near N/2
  • Use chi-squared or similar statistical tests for confidence
  • 使用N个对时，正确密钥的计数偏差约为N × |ε|
  • 错误密钥的计数接近N/2
  • 使用卡方检验或类似统计测试来提升置信度

Common Pitfalls to Avoid

需避免的常见陷阱

1. Ignoring Explicit Hints

1. 忽略明确提示

Wrong: Task says "linear attack" but agent implements brute force Right: Follow the explicit methodology hint in the task description
错误做法：任务要求“线性攻击”但Agent实现暴力破解 正确做法：遵循任务描述中的明确方法提示

2. Implementing Before Analysis

2. 未分析就实现

Wrong: Jump into coding brute-force approaches immediately Right: First analyze cipher structure, calculate complexities, design algorithm
错误做法：直接开始编写暴力破解代码 正确做法：首先分析密码结构、计算复杂度、设计算法

3. Memory-Intensive Meet-in-the-Middle

3. 内存密集型中间相遇攻击

Wrong: Attempt to store 2^40 entries in memory (requires terabytes) Right: Calculate memory requirements before implementation:
  • 2^20 entries × 16 bytes = ~16 MB (feasible)
  • 2^30 entries × 16 bytes = ~16 GB (problematic)
  • 2^40 entries × 16 bytes = ~16 TB (infeasible)
错误做法：尝试在内存中存储2^40个条目（需要数TB空间） 正确做法：在实现前计算内存需求：
  • 2^20个条目 × 16字节 = ~16 MB（可行）
  • 2^30个条目 × 16字节 = ~16 GB（有问题）
  • 2^40个条目 × 16字节 = ~16 TB（不可行）

4. Repeated Failed Approaches

4. 重复尝试失败的方法

Wrong: Try brute force variant 1, fail, try variant 2, fail, try variant 3... Right: After one approach fails, analyze WHY before trying alternatives
错误做法：尝试暴力破解变体1失败后，直接尝试变体2、3... 正确做法：一种方法失败后，先分析原因再尝试替代方案

5. Time Mismanagement

5. 时间管理不当

Wrong: Spend all available time on infeasible brute-force implementations Right: Allocate time for: analysis (30%), algorithm design (30%), implementation (30%), testing (10%)
错误做法：将所有时间花费在不可行的暴力破解实现上 正确做法：分配时间：分析（30%）、算法设计（30%）、实现（30%）、测试（10%）

6. Not Using All Available Pairs

6. 未充分利用所有可用对

Wrong: Use pairs only for final verification Right: Linear cryptanalysis uses ALL pairs simultaneously to statistically recover key bits
错误做法：仅在最终验证时使用对 正确做法：线性密码分析同时使用所有对来统计恢复密钥位

Implementation Checklist

实现检查清单

Before starting implementation:
  • Read and understand the complete cipher implementation
  • Identify the key schedule and total key space
  • Calculate brute-force complexity (is it feasible?)
  • If brute force infeasible, identify linear approximations
  • Estimate required number of pairs vs. available pairs
  • Design the attack algorithm on paper before coding
  • Implement with progress output to monitor execution
During implementation:
  • Test each component independently
  • Verify linear approximations hold on known pairs
  • Include flush statements for output visibility
  • Set reasonable timeouts for each phase
After key recovery:
  • Verify recovered key decrypts all ciphertexts correctly
  • Create the required output file in the correct format
  • Double-check output matches expected format
开始实现前：
  • 阅读并理解完整的密码实现
  • 识别密钥调度和总密钥空间
  • 计算暴力破解复杂度（是否可行？）
  • 如果暴力破解不可行，识别线性近似
  • 估算所需的对数量与可用对数量的对比
  • 先在纸上设计攻击算法再编码
  • 实现时加入进度输出以监控执行
实现过程中：
  • 独立测试每个组件
  • 验证线性近似在已知对上成立
  • 加入刷新语句以确保输出可见
  • 为每个阶段设置合理的超时时间
密钥恢复后：
  • 验证恢复的密钥能否正确解密所有密文
  • 以正确格式创建所需的输出文件
  • 再次检查输出是否符合预期格式

Debugging Tips

调试技巧

  1. Output buffering: Use explicit flush after print statements
  2. Progress indicators: Print progress every N iterations for long computations
  3. Intermediate verification: Check partial results against known values
  4. Memory monitoring: Watch process memory usage for large operations
  1. 输出缓冲：在打印语句后使用显式刷新
  2. 进度指示器：对于长时间计算，每N次迭代打印一次进度
  3. 中间结果验证：将部分结果与已知值对比
  4. 内存监控：在大型运算中观察进程内存使用情况

Resources

资源

This skill does not require external scripts or assets. The approach relies on understanding and applying linear cryptanalysis principles to the specific cipher implementation provided in each task.
本技能不需要外部脚本或资源。该方法依赖于理解并将线性密码分析原理应用于每个任务中提供的特定密码实现。