<<

. 9
( 16)



>>

˜ ( i )0 8 4 9 5 13 3
12 2 6 14 1 11 7 15
10


probability of about 1/222, we obtain a collision for the full hash. The trick
then is to efficiently find a sufficient number of pairs of inputs that satisfy
this differential property.
After describing the differential phase of the attack, we then specify a
systeni of nonlinear equations, any solution of which will satisfy the desired
differential property. For the attack to be practical, we must be able to
efficiently solve this system of equations, and we explain how to accomplish
this.
There is also a third phase of the attack that connects the second phase to
the initial steps of the hash algorithm. This third phase is relatively simple.
Before we dive into the computational details behind the attack, we try
to motivate Dobbertin™s approach to the problem. Here, we only provide a
quick overview -for inorc details see Daum [34].

Motivation
Dobbertin™s attack yields a colliding pair of messages, denoted



each consisting of a single 512-bit block. The two messages are chosen to be as
similar as possible with respect to the difference operation, which is defined to
he subtraction modulo 232. More precisely, only one word differs between M
and M™, and the modular difference in that word is 1. Furthermore, the
particular word where this difference occurs is chosen so that, in effect, we
only need to worry about the avalanche effect for steps 12 through 19. This
essentially reduces the most difficult part of the attack to just 8 of the 48
steps. Then a system of equations is derived for these 8 steps, and some
clever insights make it. possible to efficiently solve the resulting equations.
The real beauty of Dobbertin™s a.ttack is that these equations can be solved
so efficiently, that a collision can be generated in about two seconds on a PC.
While the attack does have a differential phase, the critical issue is the
equation solving phase. The system of equations is solved using a method
5.3 MD4 213


that relies on the fact that a small change in the input will usually result in
a small change in the output. This, in turn, only holds because the number
of steps is small, which implies that the avalanche effect is relatively small.
Furthermore, it is crucial that a large number of different inputs compress
to the same output, making a solution that much easier to find. In short,
the attack uses a very specialized method of equation solving that takes full
advantage of the structure of the MD4 hash.

Notation
Let MD4i..,j(A,B ,C , D , M ) be the result of steps i , i f l , i+2,. . . , j of the MD4
hash, where the arguments (A, B ,C , D ) are the “initial values” at step i
and M is the data array (where M consists of sixteen 32-bit words). Then
MD4i,,,j(A, , C ,D , M ) yields the four 32-bit words that result from applying
B
steps i through j to the initial values ( A , B , C , D ) , using M as the data.
18(A, B , C ,D , M ) will yield the (Q18, Q17, Q16, Q15)r the
For example, MD414...
four 32-bit words that result from applying steps 14 through 18 (inclusive)
using the specified initial values, and using the data array M . The only words
of M that will be used in steps 14 through 18 are words 14, 15, 0, 4 and 8,
respectively, as can be seen from Table 5.3. Consequently, the other words
c,
of M are irrelevant in the computation of MD414...18(A, B , D , M ) .
We denote the initial values for step 0 as “IV”; that is, IV is the MD4
initialization vector. As indicated in Table 5.1, the initialization vector is
IV = (0x67452301,Oxef cdab89,Ox98badcfe,0x10325476). (5.7)
The attack presented here would work for any choice of IV, but we must use
the IV in (5.7) to obtain an MD4 collision.
Note that even if the correct MD4 initialization vector is used,

MD40...47(IV, M ) # h ( M ) ,
where h is the MD4 hash function, since there is a final transformation in MD4
that is not accounted for in M D ˜ o . . . ˜ ˜XI)V This final transformation con-
( .,
sists of adding the initial values to the output of the function and rearranging
the order of the output words-see Table 5.1. The MD4 padding is also not
considered in this attack. But any collision found by this attack will result
in a collision for the full MD4 hash without any modification to M or M™.
Suppose
( Q j , Qj-1, Qj-2, Qj-3) = MD40...j (IV, M )

and
(Qi, MD40...j(IV,M™).
Qi-3) =
Qi-11 I - 2 ,
Q

Then define

QI, Qi-1, Q j - 2 Qi-31,
Aj = ( Q j Qg-2, Qj-3
Qj-1-
- - -
HASH FUNCTIONS
214


where, as usual, the arithmetic is taken modulo 232.
We use 2n t o denote the 32-bit word which has decimal value 2n (mod 232),
and -271 represent -2n (mod 232). Then, for example,

2™ 0x02000000 and 25 = Oxf f f f f f eO.
= -



Now we have all of the notation and niachinery necessary t o describe
Dobbertin™s clever attack, which determines two distinct 512-bit inputs, M
and M™, such that MD40...47(IV,M ) = MD40...47(IV,M I ) . As mentioned
above, this implies h ( M ) = h(M™) where h is the MD4 hash function.
Although the differential phase of Dobbertin™s attack occurs last in prac-
tice, we describe it first, since it motivates the remainder of the attack. Then
we work our way backwards t o the start of the attack, and at each phase we
consider the probability of success and the work factor.
Given a 512-bit input M , we have M = ( X o , X l , . . , X I S ) ,where each X ,
is a 32-bit word. Given M , define M™ by



As with all arithmetic operations in this section, t h e addition is taken mod-
ulo 2”.
The input word X12 last appears in step 35 of the MD4 hash. Conse-
quently, if we can find M and 11.1 that satisfy (5.8) for which A35 = (O,O, O , O ) ,
then we have found a collision. That is, if A35 = (O,O, 0,O) then the internal
state of MD4 for inputs M and M™ coincide at step 35, and all input values
for steps 36 through 47 are the same, so the resulting MD4 hash values must
be equal. Our goal is t o find such a pair M and M™.
Given this observation concerning Ass, Dobbertin™s attack consists of the
following three phases.

1. First, we show that if

al, (0, 225,-25, o),
= (5.9)

then, with a probability of at least 1 / 2 ” , we obtain the desired result,
that is, we have A35 = ( O , O , O , O ) . This phase is the differential attack
mentioned above.

2. Then we “backup” t o step 12, that is, we show how t o determine initial
values for step 12 that will force (5.9) t o hold. This second phase of the
attack requires a solution to a nonlinear system of equations.

3 . Then we complete the attack by backing u p further, all the way t o
step 0. This last phase of the attack is relatively straightforward.
5.3 MD4 215


At each of the three phases of the attack, some of the 32-bit words Xi of
the message M are determined. When the attack has successfully completed,
we will have specified a full 512-bit M and M˜ can be computed from (5.8).
Then M # M™, but they have the same MD4 hash value and we have found
the desired collision.

Steps 19 to 35
First, we describe the differential phase of the attack, which begins at step 19
and concludes at step 35. Often, differential cryptanalytic attacks use XOR
as the difference operation, but here the difference is defined as subtraction
modulo 232.
We assume that (5.9) is satisfied and, furthermore, that

G(Q™,,, Q™,,, (5.10)
=
G(Q19, Q18, Q I ˜ ) Q™,7).

If both of these assumptions hold, then the probabilities in Table 5.5 can be
shown to hold. Recall that Qj is the only output that changes at step j. Also,
in Table 5.5, the column labeled p gives the probability that A j holds, given
that A,-1 holds. The i column indicates the round-and therefore whether
function G, or H is used in the calculation of the corresponding row. Note
that the data blocks M and M˜ are the same at each step, except for step 35,
+
where Xi2 = X12 1. This is indicated by the two inputs for the j = 35
step. The 2 elements in Table 5.5 indicate entries that are not relevant to
the differential attack.
Consider, for example, the j = 35 row in Table 5.5. Assuming that
the j = 34 row holds true, then A34 = ( 0 , 0 ,0 , l ) and it follows from the
definition of step 35 in Table 5.2 that

+ H(Q34,Q33, Q32) + Xi2 + K2) << 15<
Q35 = (Q31

= ((Q™,, + 1) + H(Q™,,, Q&, Q i 2 ) + X12 + K2) << 15
<
= ( Q ˜ + H(Q$,, Q$3, Q$2) + (X12 + 1) + K2) << 15
<
I
Q&
=

which implies that A35 = ( 0 , 0 ,0,0), with probability 1. This is summarized
in the j = 35 row of Table 5.5.
Each of the remaining probabilities in Table 5.5 can also be verified di-
rectly, although some of the counting arguments are fairly technical. In Prob-
lems 11 and 12 we outline a straightforward computational approach that can
be used to determine the analogous probabilities for 8-bit words. These 8-bit
probabilities are essentially identical to those obtained using 32-bit words.
The product of the probabilities in Table 5.5 is about 1/230, which implies
that if we find about 230 inputs M that satisfy (5.9)--with the correspond-
ing M™ defined by (5.8)-then we can expect to obtain a pair of inputs for
HASH FUNCTIONS
216


Table 5.5: Differential Attack on MD4
˜
˜




A;
i Input
y
sj
J
** * *
19
0 225 1 3
0
20 -25 1 x1
21 225
0
0 -25 1/9
1 5 XS
o
-214
22 0 9 1/3
1
225 X9
26 -214
23 0 0 1 13 1/3 XI 3
24 0 0 3 1/9
1
26 -214 x
2
-214
26 Xs
0 0
25 5 1/9
1
-223 0 0
26 1 9 XlO
1/3
26
-223 0
27 0
219 1 13 1/3 x4
1
0 219
28 0
-223 1/9
3
1 X1
:
-223
219
0
0
29 1/9
1 5 x
7
219
0
30 0
-1 9
1 1/3 x1
1
0 0
-1
31 1 13 1/3
1 x5
1
˜




0 0
-1
1
32 X
O
3 1/3
2
0
33 0 -1
1 2 9 1/3 X8
0
34 0 0 1 1/3
2 11 x
4
2 15
0
0 0 0
35 1
1 X12,X12+
˜

˜




which A35 = (0, 0, 0,O). Given such a pair, we will have found a collision and
thereby have broken MD4.
Below, we show that there is a computationally efficient method to gener-
ate messages M for which the differential condition (5.9) holds. As a result,
an efficient attack exists for finding collisions. In [42], it is claimed that
the actual siiccess probability of the differential phase of this MD4 attack is
about 1/222, as opposed to 1/230, which is the probability indicated by the
approximations in Table 5.5. Assuming the higher probability holds, if we can
find 222 data values that satisfy the initial conditions of the differential at-
tack, then we expect to find a collision. In fact, it is easy to show empirically
that the higher probability does hold.
For the differential attack in Table 5.5, there are no restrictions on M . In
the remaining phases of the attack, we determine 111 so that A19 = (0,0,0,O)
and the technical condition (5.10) holds, in which case the analysis in Ta-
ble 5.5 is valid.
This completes our description of the differential phase of the attack. In
the next phase of the attack, we backup to step 12 and force the necessary
differential condition at step 19 to hold. This next phase is the most complex
part of the attack.
5.3 MD4 217


Steps 12 to 19
In this phase of the attack, we consider steps 12 through 19. This is simpler
than attempting to deal with steps 0 through 19 all at once. And if we can
solve the problem for steps 12 through 19, then, intuitively, it should be easy
to solve for steps 0 through 11, since Xj = Xi for all j # 12 and Xl2 first
appears in step 12.
Table 5.6 contains the relevant information for steps 12 through 19. Here,
i = 0 indicates that the function F is used, while i = 1 indicates that G is
used.




i sj M Input M' Input
j
+
12 03 Xl2 1
x2
1
13 0 7 x3
1 x3
1
14 0 11 Xi4 x4
1
15 0 19 Xi5 x5
1
XO
16 1 3 XO
17 1 5 x4 x
4
18 1 9 x8
x8
+1
19 1 13 Xi2 x2
1



To apply the differential attack in Table 5.5, it is necessary that the dif-
ferential condition A,, = (0, 225, -25, 0) is satisfied, which means that

Q16 = Qi6


(5.11)



We want to derive equations involving Qj and Qi, for j = 12,13,.. . , 19. We
can obtain eight equations by combining the corresponding equations in Qj
and Qi. For example, at step 12 we have

+ F(Qi1, Qg) + X12) << 3
< (5.12)
Qio,
= (Q8
Q12

and
QL = (Qk + F(Q:i,Q',,, Qk) + XIZ)<< 3.
< (5.13)
Since Xj = Xi for j = 0,1,2,.. . ,11, and these are the only data values used
in steps 0 through 11, we must have A11 = (O,O, O , O ) , which implies that

(Qk, Q$,Qh,Qii).
(Qx, Q9, (5.14)
QIO, Q11) =
H A S H FUNCTIONS
218


Consequently, subtracting (5.12) from (5.13) and simplifying yields


(QiZ << 29)
< << 29) = 1.
<
(Q12
-




As another example; consider step 18, where we have


+ G(Q17, Q16, Q15) + X g ) << 9
< (5.15)
Q18 = (Q14




Subtracting (5.15) from (5.16) and simplifying yields




Combining the corresponding equations for Qj and Ql, and making use
of (5.11) and (5.14), we obtain the system of equations


(5.17)
(5.18)
(5.19)
(5.20)
(5.21)
(5.22)


(5.23)


(5.24)

To solve these equations: we must find fourteen 32-bit words




so that all of the equations (5.17) through (5.24) are satisfied. Given such a
solution, then from the definition of steps 12 through 19, it is easy to verify
5.3 MD4 219


that the desired condition on will hold provided wc selcct
A19




That is; given a solution of the form (5.25) to the system of equations that
appears in (5.17) through (5.24), if we choose Xj, for j = 13,14,15,0,4,8,12,
and Q g and QS as specified in (5.26), then we can begin at step 12 and
arrive at step 19 with the necessary differential condition on A19 ˜ a t i s f i e d . ˜
Consequently, this phase of the MD4 attack reduces to finding a solution to
the system of equations in (5.17) through (5.24).
If we choose

-1 = Oxffffffff, Qi2 = 0, and (5.27)
0,
Q12 = Qii =


then (5.17) is satisfied, and equations (5.24), (5.23), (5.19), (5.22), and (5.18):
respectively, can be rewritten as8




Most of these equations follow immediately from the corresponding equation
above, but (5.30) and (5.32) require somewhat more work; see Problem 13.
With thc equations in this form, it is apparent that



7Whew!
˜Hopefully, we have corrected a couple of very annoying typos that appear in [42].
HASHFUNCTIONS
220


can be chosen arbitrarily, thereby determining

(5.34)

The two remaining equations, (5.21) and (5.20), can be rewritten, respec-
t>ively,as




We refer to these as the “check” equations, and, of course, these check equa-
tions milst both be satisfied before we have found a solution to the original
system of equations in (5.17) through (5.24).
Finally, a solution is said to be admissible if it satisfies the additional
constraint
(5.37)
G(Q19, Q18, Q17) = G(Qi9, Qi8, Q I ˜ ) .

If a solution is not admissible, then the j = 20 step of the differential attack in
Table 5.5 will fail, so we want to restrict our attention to admissible solutions.
To solve this system we proceed as follows. First, we randomly select val-
ues for the free variables in (5.33) and substitute these into equations (5.28)
through (5.32), thereby determining the values in (5.34). At this point, we
have determined values for all of the variables that appear in the the check
equations (5.35) and (5.36) and we can verify whether both of these required
conditions hold. If so, we have found a solution to the system of equations.
In this case, we can then verify whether the solution is admissible, that is,
whether (5.37) holds. If the solution is admissible, then the solution is a can-
didate for the differential phase of the attack. If any of these three conditions
fail, we can start over with another choice for the free variables in (5.28)
through (5.32).
Each iteration of this process is efficient, but it appears that an inordi-
nately large number of trials might be required before we can expect, to find
a solution that satisfies both of the check equations (5.35) and (5.36) and is
admissible, that is, (5.37) also holds. In fact, random 32-bit words would only
be expected to match with a probability of 1/232, and if these three equations
each hold with such a probability, thtm 296 trials would be required before
before i t single admissible solution could be found. This would give an overall
work factor much higher than an exhaustive collision search, which, by the
birthday paradox, has an expected work factor of about 264.
Here, Dobbertin cleverly makes use of what, he calls a “continuous ap-
proximation”, that is, he uses the fact that input values for F and G that
are “nearby” will generate output values that are “nearby” (see Problem 14).
This reduces the work required to solve the system of equations to a very
small arnount. which takes less than one second on a modern PC.
5.3 MD4 221


Recall that the notation (Y)i.,.jis used to represent bits i through j of Y ,
where the bits are numbered from left-to-right, beginning with 0. Also, we
use the notation (Y = 0)i...j to denote that bits i through j of Y are all 0.
Dobbertin™s continuous approximation algorithm can be stated as follows:

1. Let Q11 = 0, Q12 = -1, and Qi2 = 0, as specified in (5.27).

at random.
2. Select Q14, and
Q15r Q l 6 1 Q17, Q18, Q19

3. Compute Qi5, Q:4, Q13, Q;3, and Qlo using (5.28) through (5.32),
respectively.
4. If the check condition (5.35), holds, goto 5; otherwise goto 2.
5. At this point, all of the equations (5.28) through (5.32) are satisfied,
as well as the check condition (5.35). We now find a sequence of so-
lutions that converge to a solution that also satisfies the second check
condition (5.36). Denote the values specified in step 2 as the “basic”
variables and let j be the smallest index for which

+ (Q15 << 13) = 0)j.,.31,
(QiS << 13)
< <
(F™ F (5.38)
- -


where we have let F™ = F ( Q i 4 ,Qt3,0) and F = F(Q14, Q13, -1). Also,
we let j = 32 if the rightmost bit of (5.38) is not zero. If j = 0,
then we are finished. If not, transform the solution by changing one
randomly selected bit in each of the basic variables. Compute Qi5, Q™,,,
Q13, Qi3, and Qlo from (5.28) through (5.32), respectively, using these
transformed values. If the first check equation (5.35) is still satisfied,
and if (5.38) holds for a smaller value of j , set the basic variables equal
to the transformed variables, and update j accordingly. Repeat this
process until j = 0.
6. We have now solved the system of equations. If the solutions is admis-
sible, that is, if the additional constraint (5.37) holds, then substitute
into (5.26) to obtain the X j values and the initial values Q 8 , &9, & l o ,
and &11. If the solution is not admissible, goto 2.
As mentioned above, this phase of the attack takes less than a second
to complete. However, the work factor is not obvious. In the homework
problems, the work factor for the various parts of this equation solving attack
are estimated empirically.
For any solution found using the algorithm above, we obtain 512-bit mes-
sages M and MI, with M # MI, and initial values for step 12 so that we can
begin at step 12 and arrive at step 19 with the two conditions
A19 = (0, 225, -25, 0)
G(Q19,Q18, G(Q™,g,&is, Q17)
Q17) =
HASH FUNCTIONS
222


satisfied. Any such solution is a candidate for the differential attack discussed
above. Arid once we find about 222 such solutions, we expect that one of these
will satisfy the differential condition A35 = (0, 0, 0, 0), in which case we will
have found a collision. Dobbertin™s algorithm, as described in this section, is
extremely clever and extremely efficient.

Steps 0 to 11
Suppose that we have successfully completed the first two phases of the attack.
Then we have found ( Q g , Qg, Q10, Q11) such that

Q ˜ o Q11, XI).
,
Q9, QIO, Q ˜ I X ) = MD412...47(&8r
MD412...47(&8, , Q9,

All that remains is to show that we can satisfy the condition



where IV is the MD4 initialization vector. Recall that X j = X i , except
+
for j = 12, and that Xi2 = Xlz 1. Also, from Table 5.4 we see that X12
first appears in step 12.
In the previous phases of the attack we have determined input blocks X j ,
for j = 0,4,8,12,13,14,15. Therefore, we are free to choose each of the re-
maining X j , that is, for j = 1 , 2 , 3 , 5 , 6 , 7 , 9 , 1 0 , 1 1 so that (5.39) holds. All of
,
these X j appear in the first 11 steps, so we will have completely determined M
when this phase of the attack is completed.
The only data values that appear in (5.39) which have been previously
determined are Xo, X q , and Xg. Given the large number of free parameters
(that is, the X j values which are yet to be determined) it appears that it
should be relatively easy to complete this final phase of the attack, and, in
fact, that is the case.
First, we select XI, X2, X s , and X5 at random and compute the vrtl-
ues ( Q 2 , Q3, Q 4 , Q5), using the MD4 initialization vector, IV. Next, we want
to select X j , for j = 6,7,9,10,11, so that

Qs),
X) =
MD46...11(&2, Q 3 , Q4, Q5, ( Q i i , Q i o , Qg,

where were found in the previous phase of the attack. Since
( Q 8 , Q 9 , Q10, Qll)

+ F(Qio,Q9, Q s ) + X11) << 19,
<
Qi1 = (Q7

if we sclect
= (Qil << 13) - Q7
< F(Qlo, Q9, Q g )
Xi1 -

we obtain the desired value for Q11. Similar equations hold for Xl0 and X y .
However, Xg was prcviously specified, so we are not free to select X s in step 8.
Fortunately, all is not lost. We have

+ F ( Q 7 , Qs, Q s ) + X g ) << 3.
< (5.40)
Qs = (Q4
5.3 MD4 223


From basic properties of the function F , we see that if

<< 29) - Q 4 - XS,
<
Q7 = -1 and (5.41)
= (Q8
Q6

then (5.40) holds for any Xg. We can force the conditions in (5.41) to hold
by selecting




and




we are assured that



where ( Q s ,Q g , Q10, Q11) were computed in the previous phase of the attack.
This solution can then be tested to see whether the condition A35 = (0, O , O , 0)
is satisfied, and, if so, we have found a collision.

All Together Now
Here, we describe the complete MD4 collision attack. Recall that X i = X j ,
+
for j # 12, and Xi2 = Xl2 1, so if we determine M = (Xo,XI,. . . , X I S )we
,
will also have determined M™ = (Xh,Xi, . . . , X;5). Therefore, we ignore M™
in this description.
The attack proceeds as follows:
1. Find (&a, Q g , Q ˜ o , and Xj, for j = 0,4,8,12,13,14,15 as specified
Q11)
in the section labeled Steps 12 to 19, above. This phase of the at-
tack also determines the initial values required in the next phase of the
attack, namely, (Q16, Q17, Q18r Q19) and (Qifj, Q{7>Q i S , Q i g ) ™
HASH FUNCTIONS
224


2. Complete the attack described in the section labeled Steps 0 to 11,
above. In this phase, X j , for j = 1 , 2 , 3 , 5 are selected at random,
and X j , for j = 6 , 7 , 9 , 1 0 , 1 1 are determined.

3. Check whether the differential condition in the section labeled Steps 19
to 35, above, is satisfied. That is, compute



(O,O, 0,O) we have found a collision; if not goto 2.
and if A35 =

There are several ways to improve the efficiency of this attack, the most
significant of which involves number 3, above. Instead of computing all the
way from step 20 to step 35 before checking the validity of the result, we
can instead check at each intermediate step j = 21,22,23,. . . whether the
corresponding A j condition in Table 5.5 holds. Given the probabilities in the
table, the vast majority of trials will terminate within a few steps. With this
modification, the attack is so efficient that other improvements are probably
not worth the additional effort.
Notice that the continuous approximation phase of the attack only needs
to be completed once per collision. Dobbertin™s equation solving method is
so efficient that the overall work factor for the attack is dominated by the
testing of the differential condition in number 3 , above. Empirically, it can
be shown that about 222 iterations are required before we expect to find a
collision. This gives an overall work factor equivalent t o the computation of
about, 2” MD4 hashes; see Problem 17.

A Meaningful Collision
5.3.3
In [42], Dobbertin gives a meaningful collision that was generated with a
modified version of his attack. The two messages in Figure 5.4 yield a collision,
where each “*™™ represents a “random” bytes. The attacker might claim that
these random-looking bytes are present for security purposes, but these bytes
would actually be selected so that the resulting messages generate the same
MD4 hash values; see Problem 19 for more details of this particular collision.
If MD4 were used in practice, the attack illustrated in Figure 5.4 would
be a serious issue. Since MD4 is not used today, the attack is not a practical
concern, but it does illustrate the dangers inherent from meaningful collisions.
Below, we consider a collision attack on MD5-a hash function which is
widely used in practice. However, the MD5 attack is far costlier and more
restrictive than this MD4 attack presented here. Consequently, it is unclear
whether any meaningful MD5 collision could ever be constructed using such
an attack. For this reason, it is often claimed that the collision attack on
MD5 is of little consequence in the real world. However, after we present the
5.4 MDS 225


....................
CONTRACT

At the price of $176,495 Alf Blowfish
sells his house to Ann Bonidea ...

....................
CONTRACT

At the price of $276,495 Alf Blowfish
sells his house to Ann Bonidea ...


Figure 5.4: MD4 collision [42].


MD5 attack, we give an example that shows how a meaningless collision can
be used to break security in a very meaningful way.



MD5
5.4


“I can™t explain myself, I™m afraid, Sir,” said Alice,
“because I™m not myself, you see.”
- Alice in Wonderland



Message Digest 5, or MD5, is a strengthened version of MD4. Like MD4,
the MD5 hash was invented by Rivest [122]. Also, MD5 was obviously used
as the model for SHA-1, since they share many common features. It is un-
doubtedly the case that MD5 and SHA-1 are the two most widely used hash
algorithms today, but use of MD5 will certainly decline over time, since it is
now considered broken. At the time of this writing, it appears certain that
SHA-1 will soon share the same fate as MD5.


MD5 Algorithm
5.4.1

MD5 is similar to MD4 and in this section, we often refer to our previous
discussion of MD4. It is important to read Section 5.3 carefully before at-
tempting this section, since both the operation of MD4 and various aspects
of the MD4 attack will be referenced here.
HASH FUNCTIONS
226


Define the four functions

F ( A ,B, ) = ( AA B ) V ( 1 AA C )
C (5.42)
G ( A ,B, ) = ( AA C ) V ( B A -C)
C (5.43)
H(A,B,C) A @ B @ C
= (5.44)
I ( A ,B, C) = B @ ( AV -C) (5.45)

where A , B and C are 32-bit words, “A” is the AND operation, “V” is the
OR operation, “@” is the XOR, and “1A” is the complement of A.
The MD5 algorithm pads the message using the same rnethod as MD4.
As in the MD4 attack, the padding is not important for the attack we discuss
here. And, as with MD4, the MD5 hash operates on 512-bit blocks of data,
with the 128-bit output of one block being used as the initial value for the
next block. The IV used in MD5 is the same as that used in MD4, which
appears in (5.7) in Section 5 . 3 .
The MD5 algorithm is given in Table 5.7 and the four MD5 round func-
tions are given in Table 5.8. Here, we number the steps consecutively from 0
to 63, with the i t h output denoted by Q i . These Q values correspond t o
the A , B , C and D values in [122].
Each step of MD5 has its own additive constant. We denote the constant
for step i as Ki. Although these constants play no role in the attack, for
completeness, the I, are given in the Appendix in Table A-1. The shift for
(
step i is denoted si and the values of si are listed in Table 5.9.
In Table 5.7, the permutation applied to the input blocks is denoted by a,
that is, Wi = X,,(i). The values of ˜ ( i for i = 0 , 1 , 2 , . . . 63, are given in
), ˜




Table 5.10.
The significant differences between MD4 and MD5 are the following [122]:

1. MD5 has four rounds, whereas MD4 has only three. Consequently,
the MD5 compression function includes 64 steps, whereas the MD4
compression function has 48 steps.

2. Each step of MD5 has a unique additive constant, whereas each round
of MD4 uses a fixed constant.

3 . The function G in the second round of MD5 is less symmetric than
the G function in MD4.

4. Each step of MD5 adds the result of the previous step, which is not the
case with MD4. The stated purpose of this modification is to produce
a faster avalanche effect.

5. In MD5, the order in which input words are accessed in the second and
third rounds is less similar t o each other than is the case in MD4.
5.4 11105 227


Table 5.7: MD5 Algorithm

// M = (Yo, I.,. . ,YN-˜),
Y message to hash, after padding
// Each Y, is a 32-bit word and N is a multiple of 16
MD5(M)
// initialize ( A ,B , C,D ) = IV
c,
( A , , D ) = (0x67452301,Oxef cdab89,Ox98badcfe,0x10325476)
B
f o r i = 0 t o N/16 - 1
// Copy block i into X
xj = Y16i+j, f o r j = 0 t o 15
// Copy X to W
Wj = X g ( j l ,
for j = 0 to 63
// initialize Q
(Q-4, Q-3, Q-2, Q-1) = (A, D , C , B)
// Rounds 0, 1, 2 and 3
RoundO(Q, W )
Roundl(Q, W )
Round2 (Q,W )
Round3(Q, W )
// Each addition is modulo 2˜”
+
( A ,B, ,D ) = (Q6o + Q-4, Q63 Q-I, Q6z + Q-2, Q6i + Q - 3 )
C
next i
return A,B , C , D
end MD5


6. It is claimed in [122] (without further explanation) that in MD5, “the
shift amounts in each round have been approximately optimized, to
yield a faster ˜avalanche effect™.™™ Also, the shifts employed in each
round of MD5 are distinct, which is not the case in MD4.
A single MD5 step is illustrated in Figure 5.5, where
if 0 5 i 5 15


{
F ( A ,B , C )
if 16 5 i 5 31
G(A,B,C)
fi(A, C )=
B, H(A,B,C) if325i547
I ( A ,B , C ) if 48 5 i 5 63.
It may be instructive to compare Figure 5.5 to a step of the MD4 algorithm,
which is illustrated in Figure 5.3.
As in the MD4 attack of Section 5.3, here we denote rounds i through j
of the MD5 function as MD5i..,j(A,B , C ,D , M ) , where ( A , C ,D ) are the
B,
“initial values” at step i and M is a 512-bit input block. Similar to MD4, we
have
MD5o...6 3 w , MI # h ( M ) ,
HASH FUNCTIONS
228


Table 5.8: MD5 Rounds

RoundO(Q, W )
// steps 0 through 15
i = 0 to 15
for
+ F(Qi-1, + Wi + K i ) << s i )
<
Qi = Q i - 1 + ((Qi-4 Q i - 2 , Qi-3)
next i
end Round0

Roundl(Q, W )
// steps 16 through 3 1
f o r i = 16 to 31
+ ((Qi-4 + G(Qi-1, Q i - 2 , Q i - 3 ) + Wi+ K i ) << ˜
<
Qi = Qi-1 i)
next i
end Round1

Round2(Q, W )
// steps 32 through 47
f o r i = 32 to 47
+ W + Ky) << s i )
+ ( ( Q i - 4 + H(Qi-1, Qi-2, i <
Qi = Qi-1 Qi-3)
next i
end Round2

RoundS(Q, W )
// steps 48 through 63
f o r i = 48 to 63
++
+ I(Qi-1, &) << S i )
<
= Qi-1+ ra
Qi-3)
((Qi-4 Qi-2,
Qi
next i
end Round3


where h is the MD5 hash function. In other words, the hash value is not
just the output of this function, since there is a final transformation and the
message is padded. Next, we consider the final transformation; for details on
the padding, see Section 5.3.
Define
f(Iv, = ( Q ˜ o , Q62, Q61) + IV,
nil) Q63,

where (Qfjg,Q 6 2 , Q 6 1 , &so) = MD50 ..63(IV,M ) and the addition is computed
modulo 2'32,per 32-bit word. Then f is the MD5 compression function. If we
hash a message M = (Mo,M I ) consisting of two 512-bit blocks, we have

h ( M ) = f ( f ( I Vb,f o ) , Ml).
In effect, f(IV, Mo) acts as the IV for the second iteration of the compression
5.4 MD5 229




Stepi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Shift si 7 12 17 22 7 12 17 22 7 12 17 22 7 12 17 22
31
S t e p i 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Shift si 5 9 14 20 5 9 14 20 5 9 14 20 5 9 14 20
Step i 32 33 35 35 36 37 38 39 40 41 42 43 44 45 46 47
Shift si 4 11 16 23 4 16 23 4 16 23 4 16 23
11 11 11
SteD i 48 49 50 51 52 53 54 55 56 57 58 58 60 61 62 63
Shift s,I 6 10 15 21 6 10 15 21 6 10 15 21 6 10 15 21


Table 5.10: MD5 Input Word Order

1 13
Stepil 0 3 6 8 9
2 4 5 7 10 12 14 15
11
a(z) 0 13
1 3 11
2 4 5 6 7 8 9 10 12 14 15
SteD i 16 18 31
17 19 20 21 22 23 24 25 26 27 28 29 30
0 3 8
˜ ( i )1 11 13
6 5 10 15 4 9 14 2 7 12
Step i 32 33 38
35 35 36 37 39 40 41 42 43 44 45 46 47
11 0 3
a(;) 5 8 14 4 7 10 13 6 9 12 15 2
1
Step i 48 49 50 51 52 53 54 55 56 57 58 58 60 61 62 63
10
7 1
a(i) 0 3 13
14 5 12 8 15 6 4 2 9
11


function f . Figure 5.1 illustrates the general case.
At this point we have the necessary notation and background to begin
discussing the MD5 attack. The MD4 attack in the previous section finds
two 512-bit blocks that have the same MD4 hash value. The MD5 attack
presented here, which is due to Wang [157],finds a pair of 1024-bit messages
that have the same MD5 hash value. We denote the two 1024-bit messages
as M˜ = (M,™,,Mi) and 1 1 = (Mo,M I ) ,where each Ml and Mi is a 512-bit
1
block. As with MD4, each 512-bit block consists of 16 words, where each
word is 32 bits.
Initially, Wang gave a collision [155, 1561 without providing any expla-
nation of the underlying technique. This lack of information led to an im-
pressive attempt to reverse engineer the “Chinese method” [64]. Incredibly,
this reverse engineering was successful enough that it yielded a more effi-
cient attack [81] than Wang™s, and it has provided the basis for subsequent
improvements in the attack.
The Chinese team did eventually release some details of their attack [157].
Minor flaws and incremental improvements have been reported by various
HASH FUNCTIONS
230


Qi-2 Qi-3 Qia




\i
f
f
Qi Qi-1 Qi-2 Qi-3



Figure 5.5: MD5 step.


authors in subsequent papers [94, 127, 1611. To date, the most thorough
and insightful description of the MD5 attack methodology was published by
Daurri in his PhD dissertation [34].™
Below, we describe the MD5 attack which originally appeared in [157]. As
mentioned above, this attack can be used to efficiently find a pair of 1024-bit
messages whose MD5 hashes are the same. But before giving details of the
attack, we first present some background and motivation. This background
material relies primarily on information in Wang™s paper [157] and in Daum™s
PhD dissertation [34].

A Note on Notation
Unfortunately, everyone who writes about Wang™s attack seems to have their
own pet notation. Even more unfortunately, we are no exception. Our no-
tation is closest to that in [16], with the only major difference being that
we number bits from left-to-right-in our notation, the high-order (leftmost)
bit is bit 0, while the low-ordw (rightmost) bit of a 32-bit word is bit num-
ber 31. As noted above, we denote the step outputs for a message block as QO
through Q 6 3 , with the IV consisting of Q - 4 , Q-1, Q - 2 , Q-3. In contrast, in
several papers, including [81, 1441, the IV is denoted Q - 3 , Qo,Q-1, Q - 2 and
the computed outputs are Q1 t,hrough Q 6 4 (but, as if t o further confuse mat-
ters, these authors number thc message words 0 through 63).
The papers of Wang [155, 156, 1571 and various other authors, use a
completely different numbering of the outputs. Instead of Qj, the outputs
arc denoted as a j , b j , cj, or d j , where j = 1 , 2 , .. . ,16 (or, in some cases,
j = 0 , 1 , .. . , 15) depending on the round. While this is more consistent with

“Daurn™s work was supervised by Hans Dobbertin, whose MD4 attack is discussed in
Section 5.3.2.
5.4 11.105 231


the notation used in the original description of MD5 [122], it is awkward for
analysis of the algorithm. Strangely, Wang numbers the bits of 32-bit words
from 1 to 32 (right-to-left). Some authors use 6 for the modular difference
and A for the XOR difference, while we use A for the modular difference.
The bottom line is that considerable care must be taken when attempting to
analyze results culled from a variety of papers, since it is not a trivial task to
translate the results into a consistent notation.


A Precise Differential
5.4.2
Wang™s MD5 attack is a differential attack. Recall that Dobbertin™s MD4
attack [42] uses subtraction modulo 232 as the difference operator. Wang™s
attack uses this same modular difference for inputs. However, some parts
of the MD5 attack require more detailed information than modular subtrac-
tion provides, so a “kind of precise differential” [157] is also employed. This
differential combines modular subtractions with information on the precise
location of the bit differences. In effect, this precise differential includes both
a modular difference and an XOR difference, and also provides additional
information beyond what these two standard differentials provide.
To motivate this precise differential, consider the pair of bytes given
by y™ = 00010101 and y = 00000101 and another pair of bytes z™ = 00100101
and z = 00010101. Then

= z/ - = O O O ˜ O O O O= 24,
yi -



which implies that with respect to the modular difference, these two pairs are
indistinguishable. However, in the MD5 attack, we must distinguish between
cases such as these, and to do so, we need more information than modular
subtraction can provide. To this end, we employ a differential that includes
modular subtraction along with an explicit specification of the bit positions
that differ between the two terms.
While an XOR difference specifies the bit positions that differ, we actu-
ally require even more information than modular subtraction and the XOR
together can provide. Specifically, we need to know whether the difference in
each bit position corresponds t o a +1 or -1 in the modular difference, and
this level of detail is not provided by the XOR.
Let y = (yo, y1,. . . , y7) and y™ = (yb, y;, . . . , yb), where each yi and yi is a
bit. Using the same example as above, we have

oooioioi - O O O O O ˜ O ˜24
yi - y = =

and
y™ CE y = 00010101 @ 00000101 = 00010000.
HASH FUNCTIONS
232


In this case, the nonzero bit in the XOR difference occurs since y$ = 1
and y3 = 0. However, the same XOR difference in bit 3 would result if y$ = 0
and y3 = 1. For Wang™s attack, we need to distinguish between cases such
as these. To do so, we use a “signed” difference that is essentially a signed
version of the XOR difference. That is, when there is a 1 in bit i of the XOR
difference, we put a “+” if y = 1 and yi = 0 and we put a “-” if yi = 0
k
and yi = 1. We use a “.” to indicate those bits that are 0 in the XOR
difference, which simply means that y; = yi. We use the notation Vy this
signed difference.” As in the MD4 attack, we denote the modular difference
as Ay. Then for y™ = 00010101 and y = 00000101 and we have Ay = 24
and Vy is given by “. . .+ . . . . ™ I .
Now consider
z˜ - (5.46)
= 00100101- 00010101= 24.

In this case we have
z ‚¬3 2 = 00100101 00010101 = 00110000,
.
and hence Vz is “. .+-. . . . , since zh - 2 2 = 1 - 0 and zh - z3 = 0 - 1.
>?



From Vx, the XOR difference is easily computed. In addition, Problem 21
shows that Vx determines the modular difference. Consequently, all of the
relevant difference information is contained in Vz. However, for convenience
we retain the modular difference.
We refer to Wang™s precise differential as the signed differential. This
differential provides more information than the modular and XOR differential
combined, and, therefore, it allows us to have correspondingly greater control
over the results at each step. However, it is important to realize that there
is still a great deal of freedom in choosing values that satisfy a given signed
differential. Consider, for example, 8-bit bytes y™ and y. Then the modular
difference is y™ - y (mod a8). Suppose Vy is specified. Then for each “+”
in Vy, the corresponding bit of y™ must be 1, and the corresponding bit of y
rnust be 0. Similarly, for each “-” in Vy, the corresponding bit of y™ must
be 0, and the corresponding bit of y must be 1. But for any bit position that
is not a 1 in y™ @ y the bits of y™ and y must agree, and the value, of the bits
in each such position is arbitrary. That is, we have one bit of freedom for
each ”. ” i n Vy, and no freedom whatsoever for each “+” and “-”.
To make this more concrete, suppose we require that Vz be “. .+-. . . .” .
Then z and z in (5.46) satisfy this requirement, as do each of t™he pairs
(10100101,10010101)
(zh, 2 0 ) =
(11100000,11010000)
21) =
(Zi,
( z k , z z ) = (11101111, 11011111)

“™The symbol “0” is usually pronounced as “nabla” or “del”, but feel free to call it
“upside-down triangle” if you prefer.
5.4 MD5 233


and many others. The point here is that while the signed differential is
more restrictive than either a modular difference or an XOR difference (or a
combination of the two), it still allows for considerable freedom in the choice
of values that satisfy a given differential.

Outline of Wang™s Attack
5.4.3
Here, we attempt to provide some motivation for Wang™s attack. However, it
appears that the actual development of the attack was essentially ad hoc.”
Consequently, the motivation is not always clear, but Daum [34] has pulled
together enough threads to provide a plausible explanation for much of the
reasoning that most likely went into the development of the attack. The
remainder of this section draws primarily on material found in Daum™s dis-
sertation [34].
Below, we distinguish between input differences and output differences.
Input differences are modular differences between input words of messages M™
and M , whereas output differences are differences between corresponding in-
termediate values, Q: and Qi. The output difference operator is the signed
difference discussed above, which is more restrictive than the modular differ-
ence or the XOR difference, but offers correspondingly greater control.
Recall that Dobbertin™s MD4 attack discussed in Section 5.3.2 includes
a differential phase, but the attack is primarily based on a clever equation
solving technique. In the differential phase of Dobbertin™s attack, the input
modular difference is specified, but the output differences are not highly con-
strained. This is crucial since the continuous approximation technique (the
equation solving phase) makes heavy use of the fact that the output values
can be altered.
In contrast, Wang™s MD5 attack is more of a “pure” differential attack.
Wang™s attack completely specifies the input differences. In addition, Wang
places significant constraints on the output differences--in fact, the output
differences are much more tightly constrained than the input differences, since
the signed difference is applied to the outputs.
At a high level, Wang™s attack can be viewed as consisting of two phases.
First, appropriate input and output differential patterns must be found. Then
the computational part of the attack consists of finding messages that satisfy
the given patterns. These two phases can be further broken down as follows:
1. Specify an input differential pattern that behaves nicely in the later
rounds. Here, the modular difference is used.

2. Specify an output differential pattern that is easily satisfied in the early
rounds. For the output differential, the more restrictive signed differ-
11
Wang™s approach has also been described as “intuitive” and “done by hand” by other
baffled authors.
HASH FUNCTIONS
234


ence is used. This is the part of the attack that is most shrouded in
mystery, but we provide some hints on the methodology, below. In any
case, finding useful difference patterns is obviously extremely challeng-
ing, since all MD5 attacks to date are based on Wang™s lone differential
patterns.
3 . Given the differential patterns, derive a set of sufficient conditions on
the outputs (along with a few necessary conditions on intermediate
values). Provided all of these conditions are met, the differential path
will hold and we will therefore obtain a collision.

4. Finally, we must determine a pair of 1024-bit messages for which all of
the sufficient conditions are satisfied. This is the computational part of
the attack and Wang™s approach for solving it consists of the following.

Generate a random 512-bit message Mo.
Use “single-step modifications” (as described below) to modify Mo
so that all of the sufficient conditions in the early steps are forced
to hold. This is accomplished via a direct modification of mes-
sage words, and it can be done in a way that preserves the input
differential conditions and any previously satisfied conditions.
Use “multi-step modifications” (as outlined below) to force some
of the sufficient conditions in the middle steps for Mo to hold. This
a more complex modification technique than the single step modi-
fication. The difficulty arises since we must satisfy the differential
conditions while maintaining all previously-satisfied sufficient con-
ditions.
Check the conditions for all of the remaining steps. If any of these
conditions are not satisfied, goto 4b. These remaining sufficient
conditions are satisfied probabilistically, that is, the attack is iter-
ated until all of these probabilistic sufficient conditions hold. These
iterations can be done efficiently and, since the input differential
was chosen to behave nicely in the later steps, the probability of
success is relatively high.
Once Mo has been found, generate a random 512-bit message M i .
Use single-step modifications to modify M1 so that all of the con-
ditions for the early steps are satisfied. Note that the initial values
for M I are not the MD5 initial values. Instead, the MD5 output
from processing Mo must be used for the initial values.
Use multi-step modifications to force the sufficient conditions in
the middle steps for M I to hold.
Check the conditions for all of the remaining steps. If any of these
conditions are not satisfied, goto 4f.
5.4 MD5 235


+ +
(i) Compute MA = MO AM, and M i = M I AM1. The precise
values of AM0 and AM1 are specified by the input differential.
For Wang™s differential, these values are given in the next section.
(j) The MD5 hash of message M = ( M 0 , M l ) is equal to the MD5
hash of the message M™ = (MA,M i ) .

See Problem 25 for one simple improvement to the computational phase of
the attack as described here.
For Wang™s differential, the work factor for the computational part of the
attack is dominated by finding Mo. The work factor for finding MO is on
the order of 2n MD5 hashes, where n is the number of conditions for MO
that are not satisfied by the modification techniques mentioned above (and
described in more detail, below). As originally implemented by Wang, the
computational phase had a work factor significantly greater than 240. Subse-
quent improvements have steadily lowered the work factor and, to date, the
best claimed work factor is on the order of about 232.25 MD5 hashes [144]. It
is possible that this will be reduced further by incremental improvements to
Wang™s attack.
Below, we discuss each part of the attack, with the emphasis on the com-
putational aspects. But before diving into the details, we mention an interest-
ing insight due to Daum [34]. Suppose we have an MD-like hash function that
only has three rounds--such as MD4 but not MD5. Then we would expect
to find a collision using Wang™s technique, since, roughly speaking, the input
differential can be selected so that the third round conditions hold, single-
step modifications can then be used to ensures that the first round conditions
hold, and, finally, multi-step modifications can ensure that the second round
conditions hold. However, MD5 has four rounds, so some special property of
MD5 must be exploited to make Wang™s attack succeed. We briefly consider
this “special feature” after discussing the attack outlined above.

5.4.4 Wang™s MD5 Differentials
Here, we describe the theoretical part of Wang™s attack--at least we attempt
to do so. This is the least well-understood part of the attack, and Wang
has provided little information, which has led many people to conjecture on
possible motivations for the attack. We give Wang™s differentials and attack,
then we consider some of the explanations offered by cryptographers who
have attempted to analyze Wang™s methodology.

Input Differential Pattern
Denote the MD5 initialization vector as IV = ( A , , C, D ) and denote the
B
initialization vector for the second block (assuming that MOis the first block)
HASH FUNCTIONS
236


as IV1 = ( A A B B ,CC, D D ) . Note that
,



where
Mo)
MD50...63(IV,
( Q 6 3 , Q 6 2 , Q61, Q6o) =

Then the hash value of (Mo,M I ) is given by

+ ( A A ,B B ,CC, D D ) ,
h = (Q60,Q63,Q62, Qtj1)


where ( 0 6 3 , Q 6 2 , Q 6 l 1 0 6 0 ) = MD50.,.63(IV1, I ) . Define IV; and h similarly
M ™
using MA and M i .
For Wang™s attack, the input modular differences are specified as

AM0 = MA - Mo = ( O , O , O , O , 231, O , O , O , O , O , 0, O,O, 231, 0) (5.47)
215,
AM^ = M ; - M˜ = (o,o, o,o, 231,0,o,o,o,o, 0, -215, O , O , 231, 0). (5.48)

That is, messages Mo and Mh differ only in words 4, 11, and 14, and M I
and M i also differ in the same words-with the differences being the same as
for the first pair of blocks, except at word 11.
We also require that

AIV, = IV; - I V ˜ p 3 1 , 225 + 231,P5 + 231,225+ 231)
=
Ah = h - h = (O,O, 0,O).


The idea here is that if we can specify the initial value for the second block
(more precisely, the value of AIV,), then we can construct a collision in the
second block. In this way, we hope to force the Ah condition to hold, which
simply states that we have found a collision.

0utput Differential Pat tern
Wang™s output differential corresponding to the input differentials in (5.47)
and (5.48) appear in the Appendix in Tables A-2, A-3, A-4, and A-5. The
columns in Tables A-2 and A-3 have the following meaning: The j column
specifies the step, “Output” refers to the output when processing Mo, Wj
is the data element used at the given step, AW, is t.he modular difference
between the input for Mh arid Mo, AOutput is the modular difference in the
outputs for MA arid MO (the output is Q j in all but the last four rounds),
arid VOutput is the signed differential term corresponding to the modular
difference AOutput. Note that in these tables we use a compact notation
for sums of powers of two which is also used in Table 5.11 and defined on
page 239. In Tables A-4 arid A-5, the columns have the same meaning as
t,hose appearing in Tables A-2 and A-3.
5.4 MD5 237


Both the modular difference and the XOR difference are easily computed
from the signed difference. Consequently, the AOutput column is not strictly
necessary in Table A-2, A-3, A-4, or A-5. However, it is convenient to have
the modular difference available.

Derivation of Differentials
Wang has not provided much information about several crucial points in her
attack, and from the brief descriptions provided, it appears that her approach
was largely intuitive. But that has not prevented people from offering various
theories as to how the differential patterns were derived.
To date, the most ambitious attempt to analyze the “Chinese method”
has been provided by Daum [34], who also gives many interesting ideas for
analyzing hash functions in general. Although Daum™s analysis of Wang™s
method is indeed interesting, he focuses primarily on MD4, not the more com-
plex MD5, and in some cases it is not obvious how the techniques translate to

<<

. 9
( 16)



>>