Differential Attack on FEAL-4 - From Principles to Implementation

Posted on Disqus:

This article primarily introduces how to perform differential cryptanalysis on the traditional block cipher algorithm FEAL-4, and demonstrates the attack process and key implementation details. The text also includes some experimental data and attack results for interested readers to reference or reproduce.

You can find the source code involved in this article here: https://github.com/linanwx/FEAL-4-Differential-Cryptanalysis.

This article is based on the Dublin City University (DCU) CSC1132/CA642 course content.

Two Important Images

Before delving into the analysis, here are two images closely related to FEAL-4 to provide an intuitive understanding of differential propagation and the overall encryption process.

  1. Differential Propagation Diagram
    The figure below shows how plaintext differences (in XOR form) propagate through the encryption rounds in FEAL-4 and ultimately reflect in the ciphertext.

  2. FEAL-4 Workflow Diagram
    The following figure illustrates the overall encryption framework of FEAL-4, including the left and right blocks of the plaintext, the injection of round subkeys, and the usage flow of the F function.

Characteristics of the F Function

The round function of FEAL-4 (i.e., the F function) can be viewed as some form of random permutation on a 32-bit input. In differential analysis, we do not need the specific implementation of F, but rather focus on its two key differential properties:

  • If , then .
  • If , then .

With these two conclusions, we can infer the output behavior under specific differential inputs in subsequent analyses, thereby aiding in locating the subkeys.

Detailed Analysis of Differential Paths

Suppose we choose a pair of special plaintexts and such that:

This specific differential vector helps simplify the differential computations in several rounds of FEAL-4 outputs.

1. Derivation of Initial Round Differences

  • Let denote the left and right blocks of (similarly, denotes those of ).

  • After the XOR operation in the first round:

    Similarly, the differential of the right half can be derived.

  • Furthermore, due to the “additional XOR round” during encryption, we obtain:

    This implies that in subsequent computations, the differences can be merged in a simpler form.

2. Backward Differential Calculation

After obtaining the plaintext pair and the corresponding ciphertext pair , further backward derivations can be made. Let the ciphertext be denoted as , then:

  • Compute , obtaining .
  • Based on the known differential properties, gradually restore intermediate variables such as , , , etc., in the last round.
  • Using these results, attacks or verifications on the subkeys can be performed.

Attacking K3

In differential analysis, one often starts with attacking an intermediate round subkey, such as . The specific steps are as follows:

  1. Select Plaintext Pairs: I generated 12 pairs of random plaintexts satisfying
  2. Encrypt and Extract Differences: Encrypt the above plaintext pairs to obtain the corresponding ciphertext pairs; combine with the differential path to derive intermediate values , , , etc.
  3. Traverse :

    Any candidate that satisfies the differential equation is retained.

Using this method, I successfully obtained four candidate subkeys:

1
cfa38976, cfa309f6, 4f238976, 4f2309f6

An example command to execute the above process is:

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

This implementation is consistent with the method I introduced on www.theamazingking.com.

Attacking K2

After obtaining several candidates for , we can proceed to deduce . The core equation is:

where comes from the previous round operations (including further computations on , , etc.). Similarly:

  1. Generate plaintext pairs that satisfy the differential condition
  2. Capture ciphertext differences after encryption, and by traversing all possible values, check if the differential constraint is satisfied.
  3. Example command:
    1
    ./main -mode=attackk2 -file=K2.txt -k3=cfa38976,cfa309f6,4f238976,4f2309f6
  4. The final output example is as follows:
    1
    2
    3
    4
    5
    Candidate K2: 8b722e41 (K3: cfa38976)
    Candidate K2: 8b72aec1 (K3: cfa38976)
    ...
    Candidate K2: 89722e43 (K3: 4f2309f6)
    Candidate K2: 8972aec3 (K3: 4f2309f6)

Attacking K1

Similarly, attacking can be done following the previous process.
To ensure the differential path consistently presents the expected results, I generated 12 plaintext pairs satisfying

and verified their encryption outputs.

Example command:

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

This allows you to input all previously obtained candidate combinations of and at once, and finally find the corresponding candidates.

Attacking K0, K4, K5

Once , , and are all obtained, , , and required for the last round can be deduced.
Let the final encrypted left and right parts be , . The corresponding plaintext blocks are , . Then:

By enumerating all possible , the corresponding and can be solved through the above equations. Then, use other plaintext-ciphertext pairs to cross-validate correctness. If all are satisfied, the correct final key set is obtained.

Example command:

1
./main -mode=attackk0k4k5 -k3k2k1="..." -file=K1.txt -file2=K1_p.txt

Implementation, Optimization, and Verification

1. Automated Generation and Parallel Computing

  • Automatically Generate Random Plaintext Pairs: Control the XOR differences in the code in advance to batch output plaintext files that meet the requirements (e.g., K3_p.txt, K2_p.txt, K1_p.txt).
  • Parallelized Search: Use Go’s Goroutines to start 10 parallel tasks, maximizing CPU resource utilization on a 10-core Mac.
  • Progress Bars and Visualization: Use the progressbar library to display search progress in real-time, making the experimental process more intuitive.

2. Verification Methods

  • Local Custom Key Testing
    First, select a set of known – (e.g., 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020), encrypt the previously generated plaintext pairs, and repeat the differential analysis process to see if this set of keys can be matched among the results.
    Experiments confirmed the ability to correctly restore this set of test keys, thereby verifying the accuracy of the code logic.

  • Specific Plaintext-Ciphertext Pair Testing
    Select a plaintext 1234567890abcdef and the ciphertext f43ae3eeb56e2bbf generated in the Einstein Zone, and verify that each of the 256 candidate – sets can reproduce this encryption mapping, further confirming the attack process is correct.

Final Results

All deduced – are stored in final_result.txt. After deduplication, they include the following ranges:

Possible Values for K0

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

Possible Values for K1

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

Possible Values for K2

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

Possible Values for K3

1
cfa38976 cfa309f6 4f238976 4f2309f6

Possible Values for K4

1
89eb0024 89eb0026 8beb0024 8beb0026

Possible Values for K5

1
b85e6bc0 b85e6bc2 ba5e6bc0 ba5e6bc2

With the aid of differential analysis, we ultimately obtained a set of candidate subkeys. Compared to modern block ciphers (such as AES), FEAL-4 has fewer rounds and a simpler structure, making it very suitable for demonstrating the concept of differential analysis in teaching and research.

Conclusion

This article detailed the complete process of performing a differential attack on FEAL-4, including designing differential paths, generating plaintext pairs, attacking intermediate subkeys (, , ), and finally reverse-solving for , , . It also introduced several optimizations and verification methods during the code implementation process.
The FEAL-4 algorithm, due to its fewer rounds and simpler structure, provides convenience for differential analysis. However, for more secure and complex modern block algorithms, the same analytical approach remains crucial. This case study aims to inspire learners and researchers in cryptography. If you have any questions or improvement suggestions, feel free to discuss and exchange ideas in the comments section!