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

be an arbitrary two-round differential trail. First the adversary finds (with the
rebound attack) a pair of states that satisfies the differential trail of the first
round, i.e. he finds a pair ( A, A Δ 2 ) on the output.

Then independently, he finds a pair of states for the second round, i.e. he finds
( C, C

⊕ Δ 1 ) that produces ( B, B ⊕

Δ 3 ). In the last step he has to
fix a proper subkey k i +1 for the second round, which will connect the output of
the first round and the input of the second round. To do so, the adversary fixes
k i +1 = B

⊕ Δ 2 ) that produces the output ( D, D ⊕

⊕ C , and as the result he obtains a pair of states ( A ⊕ k i ,A ⊕ k i ⊕ Δ 1 )

that satisfy the two round differential trail.
Similarly, the adversary can pass more S-box layers when he controls the sub-
keys of these layers. An obvious requirement for the subkeys of these additional
rounds is that they need to be independent. Otherwise, a change in a subkey
in one round will change the value of a subkey in another round, which might
lead to incorrect input values for the S-box layer of this second round. A second
requirement is an invertible key schedule. Since the adversary controls the values
of the subkeys of some middle rounds, he has to be able to produce the values
of the subkeys of the rounds that precede and follow these rounds, hence he has
to find the master key from the fixed subkeys. It is important to notice that this
technique requires a negligible memory.

2.4 Building the Differential Trails

For each of the techniques discussed above, the adversary first builds a trail that
may have a plenty of active S-boxes in some middle rounds and a few at the ends
of the trail. Then, a pair of values that follows the differential trail only in these
middle rounds is found with complexity 1. The rest of the rounds, before and
after the middle rounds, are covered probabilistically since the adversary has no
degree of freedom left.
Finding the optimal differential trails with no difference in the key can be
done automatically since the ciphers considered in this paper are byte-oriented
with a block size of 16 bytes. This leads to a search space of 2 16 possible starting
values.
Some of the ciphers are based on the so-called wide trail strategy [10], and
provide an ecient method for estimating the probability of the best round-
reduced standard differential trails. These estimation are based on the differential
properties of the S-boxes and the diffusion properties of the LD layers, which
are often maximum distance separable mappings.

3 Impact of Block Cipher Known Key Differential Trails

on Hash Modes

The most popular design of cryptographic hash is based on iterative use of a
compression function. This construction is also known as the Merkle-Damg ard
(MD) structure. Early compression functions were using block ciphers as the
main building block. Assume that we have a single instance of a block cipher