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

E K ( P ) and wish to design a compression function that takes a 2 n -bit input
( H, M ) and outputs a n -bit string F ( H, M ). This problem has been investigated
in [7,27] and it has been shown that there are 12 structures (modes) that are
secure. An example of one such structure is the well-known Davies-Meyer (DM)
mode that is defined as F ( H, M )= E M ( H )

H (see mode 5 in Table 2), where
H and M are the chaining value and the message, respectively.
In this work, we consider four types of collision attacks against the compres-
sion functions:

⊕

1. Collisions - for a fixed chaining value H 0 , the adversary tries to find two
distinct messages M 1 ,M 2 such that F ( H 0 ,M 1 )= F ( H 0 ,M 2 ).
2. Pseudo collisions - for a message M , the adversary wishes to find two distinct
chaining values H 1 ,H 2 such that F ( H 1 ,M )= F ( H 2 ,M ).
3. Semi-free start collisions - the adversary attempts to find two distinct mes-
sages M 1 ,M 2 and a chaining value H such that F ( H, M 1 )= F ( H, M 2 ).
4. Free start collisions - the adversary tries to find two distinct chaining val-
ues H 1 ,H 2 , and two distinct messages M 1 ,M 2 such that F ( H 1 ,M 1 )=
F ( H 2 ,M 2 ).

We investigate the resistance of compression functions based on block ciphers
against the attacks described above. We assume that the adversary can build
a differential trail for the cipher with differences not only in the plaintext, or
in the key, but also in both the plaintext and the key. For example, for the
DM compression function, this means the adversary can find a pair of chaining
values ( H 1 ,H 2 ) and a pair of messages ( M 1 ,M 2 ) (possibly in one of the pairs
the two values are equal) such that H 1 ⊕

H 2 = Δ H ,M 1 ⊕ M 2 = Δ M and

F ( H 1 ,M 1 ) Δ 2 . Hence, when the adversary can build some

trail, i.e. when he cannot control the exact values of the differences Δ H ,Δ 2 ,
then he can find a differential distinguisher for the DM compression function.
On the other hand, when the adversary can build a specific trail for the cipher
with a difference in the plaintext ( H is the plaintext input to the cipher), such
that Δ H ⊕ Δ 2 = 0, then he can find: 1) free-start collisions, if Δ M ,Δ H =0,
2) pseudo-collisions, if Δ M =0 ,Δ H = 0, 3) collisions or semi-free start collisions,
if Δ M =0 ,Δ H = Δ 2 = 0 (note that this implies that there are key collisions in
the cipher since in DM, the message is the key).
The same approach can be applied to the other 11 modes. We try to find
the all possible collision attacks under the assumption that the adversary can
control the relation between the input and the output differences of a trail in
the cipher. Our findings are presented in Table 2.
Often the block size of a cipher is too small to be secure in the compression
mode. Hence, there is a class of compression functions, also called double-block-
length ones, whose output size is two times bigger than the block size of the
underlying cipher. We investigate the security of such functions proposed by Lai-
Massey in [20], Hirose in [14] and Bracht et al. in [8]. Our results are presented
in Table 3.

⊕ F ( H 2 ,M 2 )= Δ H ⊕