Cryptography Reference
In-Depth Information
the S-box layers of two consecutive rounds can be attacked independently since
the round function uses only half of the input. For a given two-round differential,
first a pair of input states that satisfy the differential of the first round function
is fixed, and then a pair of states of the second round function. Therefore, in
an known-key attack, any differential trail can be extended by two additional
rounds (this should not be confused with the distinguishers on 7-round Feistel
ciphers proposed in [18]).
L
R
Assume that the adversary can control the key in
a Feistel cipher. As the size of the input to the round
function and the size of the round key are (usually)
half as big as in the SP ciphers, the number of rounds
that can be attacked for free is twice as big as for the
SP ciphers. Let us examine the possibility of obtaining
a pair of states for a three-round differential. Let n -
bit Feistel cipher has an invertible key schedule that
generates 2 -bit subkeys. To find a pair of states that
follows some three-round differential:
k 1
F
AB
k 2
F
D
C
k 3
F
EG
Fig. 3. Chosen-key dis-
tinguisher
( Δ 1 1 )
( Δ 2 2 )
( Δ 3 3 )
( Δ 4 4 )
for
3-round
Feistel ciphers
Δ 1 )), the ad-
versary builds, as in the rebound attack, three pairs of states, separately for each
round, that satisfy the one-round differentials, i.e. he finds the values A, C, E ,
such that
Δ 1 ,R
(the pair of states is ( L, R ) , ( L
Δ 1 )= Δ 1
Δ 2 ,
F ( A )
F ( A
Δ 2 )= Δ 2
Δ 3 ,
F ( C )
F ( C
Δ 4 .
Let F ( A )= B, F ( C )= D, F ( E )= G . Then, in order to connect these three
one-round differentials, the following conditions for the subkeys k 1 ,k 2 ,k 3 apply:
Δ 3 )= Δ 3
F ( E )
F ( E
L
k 1 = A,
R
B
k 2 = C,
L
D
k 3 = E.
From the first and the third equation, we get the relation k 1 ⊕ k 3 = A ⊕ D ⊕ E
(note that the adversary does not control the values of A, D, E because they are
fixed by the rebound attack). To satisfy this relation, the keys k 1 ,k 3 have to be
independent (or be linearly dependent - but this is not common for ciphers).
Once this is satisfied, the solution ( L, R, k 1 ,k 2 ,k 3 ) for the system can be found
in linear time. Hence in general, the master key has to be at least 3 2 -bit long.
A similar analysis applies to cases when a higher number of rounds has to be
covered for free. The only difference is that the resulting system has more equa-
tions. When r rounds are fixed, the system has r equation and r + 2 unknowns:
L, R, k 1 ,...,k r . In order to find the solution in linear time, for any invertible key
schedule, the subkeys have to be independent. Hence, to attack an additional r
rounds of a n -bit Feistel cipher the key has to be at least
r 2 -bit long.
Search WWH ::




Custom Search