Differential Attack on FEAL-4 - From Principles to Implementation

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.

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.

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.
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 $X \oplus Y = 0$, then $F(X) = F(Y)$.
If $X \oplus Y = 0x80800000$, then $F(X) \oplus F(Y) = 0x02000000$.

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 $P_0$ and $P_1$ such that: $$ P_0 \oplus P_1 = 0x8080000080800000 = P^{\prime}. $$ This specific differential vector helps simplify the differential computations in several rounds of FEAL-4 outputs.

1. Derivation of Initial Round Differences

Let $(L0_0, R0_0)$ denote the left and right blocks of $P_0$ (similarly, $(L0_1, R0_1)$ denotes those of $P_1$).
After the XOR operation in the first round: $$ L1_0 \oplus L1_1 = (L0_0 \oplus K4) \oplus (L0_1 \oplus K4) = L0_0 \oplus L0_1 = 0x80800000. $$ Similarly, the differential of the right half can be derived.
Furthermore, due to the “additional XOR round” during encryption, we obtain: $$ R2_0 \oplus R2_1 = (R1_0 \oplus L1_0) \oplus (R1_1 \oplus L1_1) = 0x80800000 \oplus 0x80800000 = 0. $$ This implies that in subsequent computations, the differences can be merged in a simpler form.

2. Backward Differential Calculation

After obtaining the plaintext pair $(P_0, P_1)$ and the corresponding ciphertext pair $(C_0, C_1)$, further backward derivations can be made. Let the ciphertext be denoted as $(L, R)$, then:

Compute $C^{\prime} = C_0 \oplus C_1$, obtaining $(L^{\prime}, R^{\prime})$.
Based on the known differential properties, gradually restore intermediate variables such as $X^{\prime}$, $Y^{\prime}$, $Z^{\prime}$, 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 $K_3$. The specific steps are as follows:

Select Plaintext Pairs: I generated 12 pairs of random plaintexts satisfying
$$ P_0 \oplus P_1 = 0x8080000080800000 $$
Encrypt and Extract Differences: Encrypt the above plaintext pairs to obtain the corresponding ciphertext pairs; combine with the differential path to derive intermediate values $Y_0$, $Y_1$, $Z^{\prime}$, etc.
Traverse $K_3$:
$$ Z^{\prime} = Z_0 \oplus Z_1 = F(Y_0 \oplus K_3) \oplus F(Y_1 \oplus K_3). $$
Any candidate $K_3$ that satisfies the differential equation $= 0x02000000$ is retained.

Using this method, I successfully obtained four candidate subkeys:

cfa38976, cfa309f6, 4f238976, 4f2309f6

An example command to execute the above process is:

./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 $K_3$, we can proceed to deduce $K_2$. The core equation is: $$ X’ = X_0 \oplus X_1 = F(U_0 \oplus K_2) \oplus F(U_1 \oplus K_2), $$ where $U$ comes from the previous round operations (including further computations on $Y$, $Z$, etc.). Similarly:

Generate plaintext pairs that satisfy the differential condition $$ P_0 \oplus P_1 = 0x0000000080800000. $$
Capture ciphertext differences after encryption, and by traversing all possible $K_2$ values, check if the differential constraint $=0x02000000$ is satisfied.

Example command:

./main -mode=attackk2 -file=K2.txt -k3=cfa38976,cfa309f6,4f238976,4f2309f6

The final output example is as follows:

Candidate K2: 8b722e41 (K3: cfa38976)
Candidate K2: 8b72aec1 (K3: cfa38976)
...
Candidate K2: 89722e43 (K3: 4f2309f6)
Candidate K2: 8972aec3 (K3: 4f2309f6)

Attacking K1

Similarly, attacking $K_1$ can be done following the previous process.
To ensure the differential path consistently presents the expected results, I generated 12 plaintext pairs satisfying
$$ P_0 \oplus P_1 = 0x0000000002000000 $$
and verified their encryption outputs.

Example command:

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

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

Attacking K0, K4, K5

Once $K_3$, $K_2$, and $K_1$ are all obtained, $K_0$, $K_4$, and $K_5$ required for the last round can be deduced.
Let the final encrypted left and right parts be $L_0$, $R_0$. The corresponding plaintext blocks are $PL$, $PR$. Then:

$PL \oplus K_4 = LR_0$
$PR \oplus K_5 = RR_0$
$RR_0 \oplus LR_0 = R_0$
$f(R_0 \oplus K_0) \oplus L_0 = LR_0$

By enumerating all possible $K_0$, the corresponding $K_4$ and $K_5$ 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:

./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 $K_0$–$K_5$ (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 $K_0$–$K_5$ sets can reproduce this encryption mapping, further confirming the attack process is correct.

Final Results

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

Possible Values for K0

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

Possible Values for K1

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

Possible Values for K2

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

Possible Values for K3

cfa38976 cfa309f6 4f238976 4f2309f6

Possible Values for K4

89eb0024 89eb0026 8beb0024 8beb0026

Possible Values for K5

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 ($K_3$, $K_2$, $K_1$), and finally reverse-solving for $K_0$, $K_4$, $K_5$. 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!