FEAL Differential Cryptanalysis

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.

Core Principles

Theory Before Implementation

Before writing any attack code:

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

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.

Approach

Step 1: Analyze the Cipher

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

Step 2: Study Differential Properties

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

Step 3: Design Chosen Plaintexts

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

Step 4: Implement the Key Recovery

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

Step 5: Validate Incrementally

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

Verification Strategies

Direct Comparison Method

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

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

Equation Verification

For each plaintext pair and key guess:

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

Sanity Checks

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

Common Pitfalls

Pitfall 1: Statistical Heuristics Instead of Differential Equations

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

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.

Pitfall 3: Repeated Heuristic Cycling

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

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.

Pitfall 5: Incomplete Partial Decrypt Verification

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

1. Round key independence: Different round keys may affect different intermediate values. Identify which computations depend on the target key bits.

2. Seed constraints: If key generation uses a small seed space (e.g., 16-bit), exhaustive search is feasible but still requires a reliable distinguisher.

3. L/R state separation: In Feistel networks, the left and right halves have different dependencies. Exploit this to isolate key bit effects.

4. F-function weaknesses: FEAL's F-function has known differential weaknesses. Input difference 0x80800000 through the F-function has specific high-probability output differences.

Debugging Checklist

When the attack returns incorrect results:

• Verify partial decryption computes correct intermediate values for known keys
• Confirm plaintext pairs have the intended XOR differences
• Check that differential equations correctly model the round structure
• Compare voting counts between correct and incorrect keys with debug output
• Verify F-function implementation matches the cipher specification
• Test with reduced rounds to isolate where the attack breaks down