# Differential trails in FEAL-8

In this paper the authors describe a differential attack against FEAL-8. They find several short differential trails, then extend the attack to the full 8-Rounds of the cipher by algebraic means.

In the diagram below, the differential trail includes a zero difference. How is this possible? If the inputs lead to a zero difference at some round in the middle of the cipher, would the intermediate ciphertexts not continue to stay the same for all future rounds?

How are these differential characteristics discovered? It seems easy to iterate over a (small) round function and find the difference probabilities for the inputs, but how can the authors see what the inputs are that cause the desired difference somewhere at a middle round of the cipher?

## 1 Answer

The difference values in the diagram denote the differences going into and coming out of the round function, which only operates on half of the state. The differences of the two halves of the state are not shown after every round - you have to infer them from the 'omega' differences at the top and the output differences of the round functions.

Note that the difference going into the first round is 00 00 02 02x. In a Feistel cipher, the input to the round function is a copy of one half of the state - the half that is not modified by the round function. So that means after the first round, one half of the state still has that same difference (although at the end of the round that half of the state is swapped with the other half).

Now note that the output of the second round function is also 00 00 02 02x. The output is xored with one half of the state, which is the same half that was copied and used as the input for the first round. Since the differences are the same and xor is its own inverse, the two differences cancel out. So now half of the state has difference zero. The other half still has difference 00 80 02 82x.

The two halves are swapped again, and now the half with difference zero is used as the input for the round function. But since an input with zero difference always generates an output with zero difference, the diagram shows zeroes in the inputs and outputs of the round function with probability 1. Do note however that there is still an active difference in the whole state, just not in the half that was copied and used as the input to that third round.

In terms of your second question, these differences are discovered by carefully examining the round function - decomposing it into smaller functions (e.g. s-boxes), examining the difference distribution tables of those smaller functions, and watching how differences from the smaller functions interact in the whole round function. For extending this over several rounds, attackers typically compile a list of the highest probability single round differentials, and then try to stitch together a high probability multi round characteristic from those.

For ciphers like FEAL, attackers generally look for high probability iterative characteristics, which are difference trails that stretch over a handful of rounds but which have the same initial and final states (just like in the diagram). Such iterative characteristics enable the attacker to break many rounds, simply by repeating the characteristic as many times as necessary.