Cryptography Reference
In-Depth Information
0
∗
0
0
×
a
c
b
d
−
k
2
0
2
B
3
B
1
−
k
2
B
2
B
3
B
1
−
k
2
B
2
B
3
0
B
1
B
2
B
3
B
1
−
k
2
B
2
B
3
B
1
B
1
B
2
B
3
−
k
2
B
1
B
2
B
3
B
L
O
C
K
B
L
O
C
K
B
L
O
C
K
σ
1
B
1
B
2
σ
B
3
3
−
k
2
B
1
B
2
B
3
−
k
2
B
1
B
2
B
3
−
k
2
B
1
1
B
1
2
B
1
3
0
B
1
1
B
1
2
B
1
3
−
k
2
x
12
B
1
1
B
1
2
B
1
3
x
13
−
k
2
B
1
1
B
1
2
B
1
3
x
14
B
1
1
B
1
2
B
1
3
x
15
x
15
B
1
1
B
1
2
B
1
3
(a)
(b)
(c)
0
∗
0
0
∗
Figure 3.8.
Dedicated attack against MD4. (a) First round, (b) second round, and (c) third round.
The permutation
σ
2
of the second round is such that
x
12
,
x
13
,
x
14
,
x
15
are the key
values used in the
B
register. Therefore, if all other values are set to
x
14
are chosen in order to achieve the above property, we make sure that the content of the
A
,
C
, and
D
registers remains zero (see Fig. 3.8b). This property holds for any choice
of
x
15
.
−
k
2
, and
x
12
,
x
13
,
We can consider the output of the second round as a random function of
x
16
for
which three registers are always zero. Randomness is thus limited to 32 bits. Considering
the birthday paradox, we can deduce a collision after 2
16
trials: we obtain two different
key blocks for which the output after the second round is the same. This breaks MD4
reduced to its first two rounds (see Fig. 3.9).
We can even look at what happens in the third round with this attack. The permu-
tation
σ
3
of the third round is such that
x
16
, the only modified key value, is used in the
last transformation box (see Fig. 3.8c). Therefore, the two key blocks
x
and
x
which
collide after the second round have the property that MD4(
x
) and MD4(
x
) only differ
in their second 32-bit quarter. In optimizing this attack, we can find two key blocks for
which the MD4 digests differ in one single bit, which is quite remarkable. (If digest
Search WWH ::
Custom Search