Known and Chosen Key Differential Distinguishers for Block Ciphers - Information Security and Cryptology-ICISC 2010 - page 42

Fig. 2. Standard differential trail for 6.5 rounds of SAFER++ for the chosen-key dis-
tinguisher and 128-bit key. The first round is without the S-box layers, crossed square
represents fixed 8-bit difference. The detailed trail is given in Fig.7 of the Appendix A.

First, to cancel the effects of the last extra subkey addition, we fix the MSB
of the bytes 1, 3, 9, 12, 13, 14, 15, 16 of the last subkey to zero, while the values
for the other bits of the subkey are randomly chosen. Then, from the mentioned
subkey, we find the value of the master key, and the values for all remaining
subkeys. Now we are ready to start the rebound attack.
We assign differences to the bytes 2, 3, 5, 13 (and no difference to other bytes)
of the state before the linear layer in round 3. The differences should be such
that after the linear layer all bytes are active (this holds for almost any assigned
values). Similarly, we assign differences to the bytes 2, 4, 9, 12 of the state after
the linear layer in round 4, go backwards through the linear layer and obtain a
full active state. In between the top and the bottom active states, there is only
theS-boxlayer,hencewematchthedifferences through this layer, i.e. we fix
the values of the bytes such that all the input differences produce all the output
differences. Since the values of the full state have been fix, the rest of the rounds
are passed probabilistically. There are 2, 4, 4, 2, 4 active S-boxes (16 in total)
in the rounds 2, 3, 5, 6, 7, respectively.
If we assume that the differential propagation through all of the S-boxes occurs
with the probability 2 − 7 then the complexity of the whole attack is 2 7 · 16 =2 112
encryptions. Note that for a fixed key, we have 2 64 starting values for the rebound
attack. We can choose different keys (such that the last subkey has the MSB of
the mentioned above bytes fixed to zero) to get the necessary number of starting
pairs for the differential attack. Since the input and output differences of the
differential pair are fully fixed, such a pair in a random permutation can be
found with 2 128 encryptions.

5.3 Feistel Ciphers

Feistel ciphers with a SP round function can have a number of rounds covered
for free in the known and chosen-key differential attacks. When the key is known,