Cryptography Reference
In-Depth Information
Output
: two message blocks
x
and
x
1:
for
i
=
0
,
1
,
2
,
4
,
5
,
6
,
8
,
9
,
10
,
12
,
13
do
x
←−
k
2
2:
σ
−
1
2
(
i
)
3:
end for
4:
x
11
←
random
{
we have defined
x
0
,...,
x
11
}
5:
initialize
a
,
b
,
c
,
d
to the initial hash value
6:
for
i
=
0to11
do
ROTL
α
i
,
1
(
a
(
a
,
d
,
c
,
b
)
←
(
d
,
c
,
b
,
+
f
1
(
b
,
c
,
d
)
+
x
i
+
k
1
))
7:
8:
end for
9:
for
i
=
12 to 14
do
x
i
←−
+
,
,
+
(
a
f
1
(
b
c
d
)
k
1
)
10:
(
a
,
d
,
c
,
b
)
←
(
d
,
c
,
b
,
0)
11:
12:
end for
{
we now have defined all
x
i
but
x
16
}
13:
b
0
←
a
{
b
0
,
x
0
,...,
x
14
define a function
g
as detailed below
}
g
(
x
15
)
14:
look for a collision
g
(
x
15
)
=
15:
define
x
i
=
x
i
for
i
=
0
,...,
14
16:
output
x
and
x
and exit
Function
g
(
x
15
):
1:
initialize
a
,
c
,
d
to 0
ROTL
α
15
,
1
(
b
0
+
2:
b
←
x
15
+
k
1
)
3:
for
i
=
0to15
do
ROTL
α
i
,
2
(
a
(
a
,
d
,
c
,
b
)
←
(
d
,
c
,
b
,
+
f
2
(
b
,
c
,
d
)
+
x
σ
2
(
i
)
+
k
2
))
4:
5:
end for
6:
return
b
Figure 3.9.
Dedicated attack against MD4.
values are compared by human beings, a modification in one bit out of 128 may not be
noticed!)
These attacks against MD4 were further improved by Hans Dobbertin, a mathe-
matician from the German Intelligence Agency, who showed how to build full collisions
(see Refs. [61, 62]). As depicted in Fig. 3.10, the main idea consists of keeping track
of a single bit flip in the message block. Indeed, we consider two messages such that
the least significant bit of
x
12
is flipped. This message modification starts influencing
the computation at the output of the
B
12
1
box. The first part of the analysis consists
of looking for some entering values of the
A
,
B
,
C
, and
D
registers before this box
and some values of
x
0
,
x
4
,
x
8
,
x
12
,
x
13
,
x
14
, and
x
15
which are the only values which
are used up to the
B
2
box. All those values must be such that the influence of flipping
the bit of
x
12
leads to flipping only two bits of the
A
,
B
,
C
, and
D
registers, namely the
bit of 2
25
in
B
and the bit of 2
5
in
C
. This part of the attack is based on solving some
equations. The second part of the analysis consists of picking some random matching
x
1
,
x
2
,
x
3
,
x
5
,
x
6
,
x
7
,
x
9
,
x
10
,
x
11
so that we get the right content of the
A
,
B
,
C
, and
D
registers before the
B
1
1
box. The third part of the analysis consists of expecting that
those two bit flips in
B
and
C
have a controlled propagation behavior as depicted in
Fig. 3.10, they do not propagate to
A
and
D
and only two bits are flipped in total. Since
Search WWH ::
Custom Search