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

Although for SP ciphers the truncated differential approach is common, fur-
ther in our analysis we will use both types of differential trails, together with
trails with a difference in the plaintext only.

2.3 Techniques for Differential Trail Constructions

A major improvement in the analysis of SP cryptographic algorithms was the
introduction of the rebound attack [25]. The idea is as follows. If we assume
that the adversary controls the input to the S-boxes, then any input-output
difference 2 to this layer can be obtained for free (simple table lookups). In other
words, when Δ 1 ,Δ 2 are fixed, then it is easy to find x such that S ( x + Δ 1 ) ⊕

S ( x )= Δ 2 . In two consecutive middle rounds the adversary first fixes both the
input differences of the LD layer in the first round, and the output differences
of the LD layer of the second round. Then he goes forward through the first
LD layer and backwards through the second LD layer. He ends up with fully
determined differences, since the layers are linear. In between there is only one
S-box layer (composed of a number of S-boxes), which can be passed for free
when the adversary fixes the values, i.e. when he finds the proper solutions x
of the above equation. Therefore, at the beginning of the first, and at the end
of the second middle round, not only the differences, but now also the values
have been fixed. The rounds that precede and follow the two middle rounds are
passed probabilistically.
The technique of the rebound attack was improved with the Super-Sbox crypt-
analysis [11,13,21]. When the round diffusion is incomplete then two layers of
S-boxes can be passed for free using a precomputed lookup tables. The idea is
similar to the one of the original rebound attack, but bigger lookup tables are
used.

The key can be used to gain an additional degree
of freedom, which in return can lead to more S-box
layers passed for free. When the adversary controls the
key, then the rebound attack can be extended to one
or two additional rounds, depending on the size of the
key. The subkey (roundkey) is xored in each round of
the cipher. The first S-box layer can be passed for free
using the previous rebound technique (by fixing not
only the difference, but the exact values as well). The
second S-box layer can be passed for free as well if
the adversary controls the input values to this layer
by solving the appropriate equations. These values can
be manipulated with the subkey, i.e. the adversary can
choose a proper subkey such that the inputs to the
S-box layer can be of arbitrary value (yet, their difference is fixed). Hence, the
adversary can pass the second S-box layer for free if he controls the subkey of this
round. Let us explain the idea on an example (See Fig.1). Let Δ 1 → Δ 2 → Δ 3
2 Only half of the input-output differences are possible, but for each of them there are
two different input values, hence on average it is true.

X

k i

A

F

B

k i +1

C

F

D

Y

Fig. 1. Chosen-key dis-
tinguisher for SP ciphers