<<

. 8
( 16)



>>

b. Discuss one security problem this creates if CTR mode is used (see
Problem 3 for a definition of CTR. mode).
c. If the same IV is always used, why is CBC mode preferable to
CTR mode?

5. Consider a Fcistel Cipher with four rounds. Then P = (Lo,Ro)is the
plaintext. What is the ciphertext C = ( L 4 ,R4), in terms of ( L ORo),
,
for each of the following round functions?

a. F(Ri-1, Ki) = X , where X is a constant
b. F ( R i - l , K i ) = Ri-1
F(R,-1, K i ) = Ri-1 Ki
@
C.

d. F(Ri-1, K i ) = Ri-1 +Ki (mod 232),where and Ki are 32-bit
Ri-1
quantities

6. Trudy wants to attack a block cipher that has a 64-bit key and 64-bit
blocks. Each time she attacks this cipher, she can conduct a chosen
plaintext attack and the cipher is used in ECB mode.

a. Suppose Trudy does an exhaustive key search each time she attacks
the ciphcr. If she conducts the attack 220 times, what is the total
work, the storage requirement and the success probability?
b. Suppose Trudy pre-computes E ( P , K ) for a selected plaintext P
and every possible kcy K . For cacti attack, Trudy chooses the same
plaintext P and obtains the corresponding ciphertext C. Then she
simply looks up C in her pre-computed list to obtain the key K .
If she again conducts the attack 2” times, what is thc total work,
the storage requirement and the success probability?
c. Suppose Trudy implements Hellman™s TMTO attack and, as sug-
gested in the text, she chooses T = m = t = 264/3. If she conducts
the attack 220 times, what is the total work, the storage require-
ment and the success probability?
4.9 PROBLEMS 185


7. The key size of CMEA is k = 64 bits and the block size n is variable.
Suppose the key is restricted to 32 bits by setting all of the first 32 bits
of any key equal to 0. Then, effectively, Ic = 32. Choose the block size
to be n = 32 bits. Implement Hellman™s TMTO attack on this version
of the CMEA block cipher. In the TMTO attack, let m = t = T = 215.
Empirically determine the probability of success.

8. Derive the formula in equation (4.3) for the success probability in Hell-
man™s TMTO. Hint: See the “occupancy problem” in Feller [49].

9. Let C be the Cave Table of the CMEA cipher. Precisely determine
the probability that (x + i) @ 1 E C for a randomly selected x E C
and i E {1,2,. . . ,255).

10. Let xi,for i = 0 , 1 , 2 , . . . ,255, be the Cave Table entries for the CMEA
cipher. Show that for 28 of these, xi @ 1 is also in the Cave Table. Con-
sequently, for a randomly selected x in the Cave Table, the probability
that x @ 1 is also in the Cave Table is about 0.11.

corresponding to co and
11. Find the value of in (4.13) and (4.14),
c2 c1
respectively.

12. Consider the CMEA cipher with block size n = 3. Suppose that we
choose plaintext blocks of the form (po,pl,p2) = (1 - x,1 - x,O),
where x E {0,1,2,.. . ,255}. Show that

a. If is even, then ciphertext co is even
2

b. If x is odd, then ciphertext co is odd.

13. For the CMEA cipher with block size n = 3, suppose that



a. Apply the algorithm in Table 4.6 to determine the resulting ci-
phertext (co,el, c )
z.
b. Describe a chosen plaintext attack that uses this result to deter-
mine T(O).
14. The purpose of this problem is to determine the probability that the at-
tack on the CMEA cipher will succeed. Let n = 3 be the block size. In
the CMEA attacks discussed in this chapter, we first determine a puta-
then for each j = 1 , 2 , . . . ,255, we attempt to recover T ( j ) .If
tive T(O),
for any j we find xj - j # C and (xj@ 1)- j # C , then we know that the
putative T ( 0 )is incorrect. If this does not occur, then we assume T ( 0 )
is correct and for each j we have recovered either T ( j )or T ( j )@ 1.
Let z E { T ( j ) , T ( j ) 1) be the recovered value. If xj - j E C but
@
j
BLOCK CIPHERS
186


1) - j # C, then we know that x j = T ( j ) and, similarly, if
(zj @
(xj @ 1) - j E C but xj - ,j # C , then we know that xj @ 1 = T ( j ) .
However, if ( z j e 1 ) - j E C and xj - j E C, then we cannot, immediately
determine the value of T ( j )from xj.
Let A be the set of j E { 0 ) 1 , 2 , ...,255} for which T ( j )cannot he
uniquely determined. Also, let U be the set of indices for which T ( j )
has been uniquely determined. Then A U U = {0,1,2, . . . ,255}, and A
and U are disjoint. Note that 0 E U .

11
x
a. Determine E(IA1) and E ( I U ( ) ,
where is the cardinality of the
set X , and E is the expected value. Write a program to empirically
verify your results.
b.” Let a = IAJ and u = 256 - a = IUI. Let k E A. What is the
probability that we can find some C E U and an index j such
that l@ (zj V 1) = k . Note that if no such e and j can be found,
the CMEA chosen plaintext attack described in this chapter cannot
resolve the ambiguity in the low-order bit of T ( k ) .

15. For the SCMEA cipher, find the equations for c1 and c2 that correspond
to the equation for cg in (4.18).

16. The results in Table 4.8 refer to the known plaintext attack on SCMEA.
Empirically determine the analogous results for the known plaintext
attack on CMEA.

17. Implement the CMEA known plaintext attack in a way that minimizes
the amount of known plaintext required. Empirically determine the
minimum number of known plaintext blocks required to correctly de-
termine the key. Your results should be based on at least 1000 successful
attacks. Hint: A successful attack may need to be repeated multiple
times to determine the precise minimum number of known plaintext
blocks required.

18. For the Akelarre cipher, let X O XI, X 2 ,X s be the input to round T and
,
Z,,Z1,22, Z, be the output of round T , let X << l denote a left rota-
<
tion of X by l. Also, let AR(X, Y )be the addition--rotation structure.
R,ecall that the inputs to the addition-rotation structure are two 32-
bit words and tht: output consists of two 32-bit words. Next, define
(Uo, U1, U2, U s ) = ( X o , X I X 2 ,X s ) << lT, where l is the rotation in
<
, ,
round T , and define (To, I )= AR(U0 @ U2, U1 @ U s ) .
T
4.9 PROBLEMS 187


19. Show that rotation and XOR commute, that is, show

( X @ Y) << n = ( X << n ) @ (Y << n)
< < <
for any 32-bit words X and Y and for any rotation n.

20. A crucial step in the Akelarre attack is solving (4.23) for the subkey
words. In this problem, we consider a similar equation, but t o simplify
the problem, we use 8-bit bytes instead of 32-bit words. Let a, b, c,
d , el f , g and h be bytes and let X and Y be 32-bit words, where
X = (zo,z1, z3) and Y = (yo, y1,9 2 , 7 ˜ 3 and each z and yi is a byte.
i
z2, )
Consider

6 f @ (Y3 - h))
((Yo - e ) @ Y2 Yl 9
@ 9,
+
+ a ) @ 2 2 E c, 2 1 @ b @ (
E (4.39)
˜ 3d ) ) .
= ((20

Note that this equation is a 16-bit version of (4.23), with a shift of 0,
and a through h playing the role of the unknown subkeys, and with X
and Y playing the role of the plaintext and ciphertext, respectively.
Solve for a through h,given the following five pairs of X and Y .

Xo = (Ox53,0x8d,
Ox86,Ox80), YO= (Ox74,Ox2i,Ox9c,
OxOa)
Y1
(Ox54,0˜77,Oxd5,0˜2b), = (Oxf7,Ox92,0x4d,
Oxee)
x=
1

OxfO, 0 ˜ 7 f ) , ; = ( 0 ˜ 7 5 , O x b 9 , 0 ˜ 3 f ,
Y!
x= (Ox21,0˜32, OxfO)
2
X3 = (Oxea,0x75,Oxaa,Oxd3), Y = (0x39,Oxif ,0x22,Oxlb)
3
X4 = (Ox27,0˜95,Oxb7,0˜2d), = (0x19,Oxbc,Oxa2, OxcO).
Y4


21. Consider a n equation of the form (4.39), and suppose that we know the
values of a through h are given by

( a , b, c, d, e , f ,g, h) = (Oxdb,Ox2a,Oxcd, 0x43,Oxbl,Ox46,0x07,0x79).

Suppose also that we suspect that the bytes of each X consist only of
lower-case ASCII characters, that is, each byte is in the range of 0x61
through 0x7a1inclusive.

a. Determine the number of four-byte X i that are consistent with
each of the following Y,.

Y = (Ox22,0˜78,0x9f,
o 0x52)
Y = ( 0 ˜ 7 d0 ˜ 3 f0 ˜ 3 f0x00)
i , , ,
Y 2 = (Oxlb,0 ˜ 7 3 , 0 ˜ 9 1 , 0 ˜ 4 b )
Y = (0x28,Oxf d,Ox8e, Oxca)
3
Y = ( 0 ˜ 3 0 , 0 ˜ 7 b ,9 5 , 0 ˜ 4 c )

4
BLOCK CIPHERS
188

b. What do these results imply about the Akelarrt: attack discussed
in this chapter?

22. Consider an equation of the form (4.39), where all quantities are 32-bit
words instead of bytes. Suppose that we know that a through d are

( a , b, c, d ) = (Ox14dbde7d,0x84aec735,0x6d66ff0l,Oxa533ee71)

and e through h are

( e ,f , g , h ) = (Oxed541eOf,Ox94c94221,0x94fa57bd, Ox48d082c7).

Suppose also that we suspect that the bytes of each X consist only of
lower-case ASCII characters, that is, each byte is in the range of 0x61
through Ox7a, inclusive.

a. Determine the number of corresponding X i that are consistent
with each of the following Y,.

YO= (0x241fb061,0x6b119143,Oxd4021163,0x4f73aca9)
Y= (Ox47dc28e3,0˜424f
e3bf,Oxb4498cd8,0˜75b4ddef)
1

Y2 (Oxlb72328c,Ox4a05f 4c8,0x39a9974f,0x72750024)
=


b. Describe a practical attack that, could be used t o recover a plaintext
message consisting of multiple blocks, provided that you know the
underlying message consists of English text, represented as ASCII.

23. The purpose of this problem is to explore the subkey recovery in the
Akelarre attack. Show that in (4.23) it is possible to recover L™ and
either
K O K3, K4, K7 and K1 @ Ks, K2 @ Ktj
, (4.40)
or
KO, K3, K4, K7 and K1CE K6, K2 G3 K5 (4.41)
assuming that a sufficient number of known plaintext blocks are avail-
able. In which cases do we obtain the results in (4.40) and in which
cases do we obtain the results in (4.41)?

24. Suppose that L™ = 0 in (4.23).

a. Show that
4.9 PROBLEMS 189




Show that




where A and B can be any 32-bit words.

25. Modify the Akelarre cipher so that it is more secure. As noted in the
text, any such modification must force the attacker to deal with the AR
structure.

26. Show that FEAL-4 is a Feistel Cipher.

27. The original description of FEAL-4 differs from that given in this chap-
ter. The purpose of this problem is to show that the two descriptions
are equivalent. The original encryption diagram for FEAL-4 can be
given as




In this schematic, each subkey Ki for i = 0 , 1 , 2 , . . . , 1 1 , is 16 bits. The
diagram corresponding to the function f is
BLOCK CIPHERS
190




Yi
Yo Yz Y3




The functions Go and GI are defined in (4.24) and (4.25), respectively.

a. Give equations for yi, for i 1 , 0 , 2 , 3 ,analogous to those in (4.26).
=

b. Denote the 32-bit keys in Figure 4.16 as ˜ ? i ,for i = 0 , 1 , 2 , . . . , 5 .
Write the K in terms of the 16-bit keys Ki, for i = 0 , 1 , 2 , . . . , 11,
i
in the diagram above so that any plaintext P yields the same
ciphertext C in both versions of the FEAL-4 cipher.

28. Consider the F function for the FEAL-4 cipher. This function is illus-
trated in Figure 4.17 and an algebraic description appears in (4.26).

a. Show that if A0 @ A1 = 0x80800000,then with a probability of
one we have F ( A 0 )@ F ( A 1 ) = 0x02000000,regardless of the k q .
b. Show that if A0 @ A1 = Oxa0008000,then with probability 1/4,
we have F ( A 0 )@ F ( A 1 ) = 0x80800000,regardless of the key.

29. Consider the differential attack on FEAL-4 discussed in this chapter.
Determine the expected number of surviving putative values of K3 when
exactly k pairs of chosen plaintexts are used, for k = 1 , 2 , 3 , 4 . where
each pair of chosen plaintexts satisfies (4.27).

30. A differential attack on FEAL-4 to recover the subkey Ks is discussed in
this chapter. Pseudo-code for the primary phase and secondary phase
of this attack appears in Tables 4.12 and 4.13, respectively, but each of
these assume that a single chosen plaintext pair is used. If available, we
would use four chosen plaintext pairs in this attack. Give pseudo-code
for both phases of the attack assuming that multiple chosen plaintext
pairs are used.

31. In Section 4.7 a differential attack on the FEAL-4 cipher is discussed
and the recovery of subkey K3 is discussed in detail.
4.9 PROBLEMS 191


a. Complete the attack by giving pseudo-code to recover K2, then K1,
then K O ,and finally, K4 and Kg. Hint: To find K2, use the char-
acteristic 0xa200800022808000. Then to recover the remaining
subkeys, arbitrary chosen plaintext pairs can be used.
b. The same characteristic that was used to recover cannot be
K3
used to recover K2. Why not?
c. What is the minimum number of chosen plaintexts required to
complete the attack?

32. Consider the two formulations of FEAL-4 given in Figures 4.16 and 4.20.
Denote the subkeys in Figures 4.16 as l?i, for i = 0,1,. . . ,5. Show
that these two formulations of FEAL-4 are equivalent by writing each
subkey Ki in Figure 4.20 in terms of the subkeys K in Figure 4.16.
i
33. In the linear cryptanalytic attack on FEAL-4, the fundamental equa-
tion (4.37) was derived from (4.36). Find the analogous equations for
each of (4.33), (4.34), arid (4.35).

34. Implement the linear cryptanalytic attack on FEAL-4 given in Ta-
ble 4.14. Augment the attack by including the results of Problem 33.

a. Estimate the time required to exhaust over all 232 choices for KO.
Specify the hardware used to obtain your timings.
b. How many known plaintexts are required to minimize the number
of surviving putative K O ,and what is this minimum number of
survivors?

35. Using the results of Problem 33, implement the improved linear attack
on FEAL-4 discussed at the end of Section 4.7.3.

a. Describe each step of the attack and give the overall work factor.
How efficient is this attack as compared to the attack in Prob-
lem 34?
b. Determine the number of known plaintext required to complete
this attack.
c. Implement this attack and verify your answers to parts a and b.

36. Could you improve the linear attack on FEAL-4 if you were able to
choose the plaintext, instead of just using known plaintext?
This Page Intentionally Left Blank
Chapter 5

Hash Functions

HASH, x. There is no definition for this word-nobody
knows what hash is.
- Ambrose Bierce, The Devil™s Dictionary




Introduction
5.1
A cryptographic hash function, denoted by h ( z ) ,must provide all of the
following.

Compression: For any input z, output y = h(x) is small. In practice,
the
0

cryptographic hash functions produce a fixed size output, regardless of
the length of the input, with typical output lengths being in the range
of 128 to 512 bits.

Eficiency: It must be efficient to compute h ( z ) for any input x. Of
0

course, the computational effort depends on the length of z, but the
work should not grow too fast, as a function of the length of z.

One-way: It is computationally infeasible to invert the hash, that is,
0

given y, we cannot find a value x such that h ( z )= y.

Weak collision resistance: Given x and h(x),it is computationally in-
0

feasible to find any w, with w # z, such that h ( w ) = h(x).

Strong collision resistance: It is computationally infeasible to find any
0

pair x and w, with z # w, such that h(x) = h(w).

It might seem that there is a hierarchy among the hash function require-
ments, in that strong collision resistance implies weak collision resistance
which implies one-way. The reality of the situation is not so simple; see
Problem 1 and [130]. Also, note that the terms pre-image resistance, second

193
HASH FUNCTIONS
194


pre-image resistance and collision resistance are often used for one-way, weak
collision resistance and strong collision resistance, respectively.
Note that collisions do exist--lots of thern-but we require that it is com-
putationally infeasible to find any collision. If one collision is found, a hash
function is considered broken. This is certainly a conservative definition of
“broken”, but, as we show in Section 5.4, there are legitimate real-world
concerns when even one collision is known.
In hash function design, the goal is to have a large and rapid aualanche
eflect, meaning that any small change in the input should quickly propagate
into a large change in the intermediate steps. This is comparable to what
happens in so-called chaotic systems, where a small change in initial condi-
tions results in a large change in the result. Another (imprecise) analogy is
that a strong avalanche effect is, intuitively, the opposite of continuity [34].
For a continuous function, small changes in the input will result in small
changes in the output, but for cryptographic hash functions, we want a small
change in the input to result in a large change in the output. Furthermore,
for a hash function, we want this large change to occur in just a few steps,
since it is often possible for the attacker to, in effect, reduce the number of
steps where the avalanche can occur. Reducing the effective number of hash
function steps is a crucial part of the attacks covered later in this chapter.
We require so much of a cryptographic hash function that it is somewhat
surprising that any exist. But, in fact, practical cryptographic hash functions
do exist. The number of clever--and often not-so-intuitive-uses for crypto-
graphic hash functions is truly amazing. Yet another surprising fact about
cryptographic hash functions is how often they are not used when they should
be; see the discussion of WEP in Section 3.4 for a prime example.
Next, we briefly give some background on hash functions, and we discuss
two cryptographic uses for such functions. The applications mentioned here
are only the tip of the iceberg when it comes to uses for hash functions. Then
in the next two sections, we dive head first into hash function cryptanalysis.
A hash function provides a “fingerprint” of data, in the sense that if two
files differ at all, their hash values will differ in a seemingly random way. For
one thing, this allows us to make digital signatures more efficient, since we
can sign t™he hash value, instead of the full message.™
Here, we adopt the notation used in [79] for public key encryption, de-
cryptlion, and signing:
Encrypt message M with Alice™s public key: C ={M}˜li˜˜.
0


Decrypt ciphertext C with Alice™s private key: M = [C]*lice.
0


˜Hashing is not just. for efficiency-it is actually necessary for the security of many
sigriat,ure schemes. For example, the ElGamal signat.ure scheme discussed in Section 6.8 is
insecure if the message is not hashed before signing. In this section, we ignore the security
implications of hashing before signing.
5.1 INTRODUCTION 195


Signing and decrypting are the same operations, so the notation for
0

Alice signing message M is S = [M]Alice, where S is the signed message.

Encryption and decryption are inverse operations so that

{[MIAlice)Alice = kf.
[{M)AlicelAlice

Since Alice™s public key is public, anyone can compute C = { M } ˜ l i ˜ ˜ .
However, only Alice can compute 111 = [ C ] ˜ lor ˜ ˜ signature S = [M]*lice,
i the
as Alice is assumed to be in sole possession of her private key. That is, anyone
can encrypt a message for Alice, but only Alice can decrypt the ciphertext.
Furthermore, only Alice can sign a message but anyone can verify the signa-
ture by using Alice™s public key.
Suppose that M is a message that Alice wants to sign. Then Alice could
compute the signature as S = [ M ] ˜ l and ˜ i ˜ send S and 1 1 to Bob. Suppose
1
Bob receives S™ and M™, which may or may not equal S and M , respectively.
Then Bob checks whether M™ = {S™}Alice, and, if so, he has verified the
integrity of the received message. That is, Bob knows with virtual certainty
that M˜ = M .
While it is also possible to provide integrity using symmetric key cryptog-
raphy (see the discussion of MAC in Section 4.2 and the discussion of HMAC,
below), digital signatures provide integrity and non-repudiation. With sym-
metric keys, both Alice and Bob share the key, so Alice can claim that Bob
forged the integrity operation, and thereby repudiate the message. But Alice
cannot repudiate a message she digitally signed, since only she has access to
her private key.
However, private key operations are costly to compute and sending both S
and M requires twice as much bandwidth as sending M . To reduce the
bandwidth usage, Alice could instead compute S = [ h ( M ) ] A l i c e and send M
and this small S to Bob. In this case, when Bob receives M™ and S™ he must
verify that h(M™) = { S t } ˜ l i c e . Assuming that hashing is more efficient than
private key operations, we not only save bandwidth, but we also increase
signing efficiency. In fact, hashing is orders of magnitude more efficient than
private key operations. Consequently, this method of signing the hash of M
is virtually always used in practice.
However, it is important to note that by signing the hash, the security
of the signature now depends not only on the security of the public key
system, but also on the security of the hash function. To see why this is
so, suppose that Alice computes S = [ h ( M ) ] ˜ l i , , and sends M and S to
Bob. If Trudy can find a collision with M , that is, if Trudy can find M˜
such that h ( M ) = h ( M ™ ) ,then Trudy can replace M with M™, and Bob will
erroneously verify the integrity of M™.
Before considering collision attacks on particular hash functions, we men-
tion one more cryptographic application of hashing. Suppose Alice wants
H A S H FUNCTIONS
196


to send a message M to Bob, and she wants to ensure the integrity of the
message. That is, Alice wants Bob to be able to automatically check that
the message he receives is the message that was actually sent. Alice has the
clever idea that she will compute y = h ( M ) and she will send y and M to
Bob. Then Bob can compute the hash of the received message and compare
it to y. Bob can thereby verify the integrity of the message, that is, Bob can
be confident that he actually received M .
There is a serious problem with Alice™s integrity scheme. If Trudy inter-
cepts M and y, she can replace M with M™, and replace y with y™ = h(M™).
Then when Bob computes the hash of the received message, it will match
the received hash value, and he will not suspect that the message has been
altered.
Seeing the flaw in her scheme, Alice decides instead to compute a keyed
hash, that is, y = h ( M ,K ) , where K is a symmetric key that Alice and Bob
share and ( M ,K ) denotes the concatenation of M and K . Then, provided
that Trudy does not know K , she cannot change the message without the
change (almost certainly) being detected.
To eliminate some possible attacks, Alice really should compute a so-
called HMAC instead of simply appending (or prepending) the key to the
message and hashing the result [142]. To understand the potential problem
with appending or prepending the key, we need to delve a little deeper into
the way that hash functions perform their magic.
Most cryptographic hash functions process the message in blocks through
several rounds in a manner analogous to the way that block ciphers work.
For the two hash functions we consider in this chapter, each round consists
of several steps, with each individual step performing a relatively simple op-
eration. The overall hash operation is similar to the way that block cipher
CBC mode encryption works (see Section 4.2 for a discussion of CBC mode),
since the hash function processes the current block together with the output
of the previous block to generate the output for the current block. For the
first block, a fixed constant is used in place of the output of the previous
block (since there is no previous block), and the output from the last block
is the hash value.
For the hash functions we consider, the block size is 512 bits, and the
hash result is 128 bits. To hash a multi-block message, the 128-bit output of
the compression function for block i is added2 to the initial value for block i,
+
and this is used as the “initial value” when compressing block i 1. The
output from the final block is the hash value. Also, the initial value to the
first block is denoted as “IV,” which is a fixed value that is specified as part
of the algorithm. The process used to hash multiple blocks is illustrated

˜The 128-bit blocks are treated as four 32-bit words and the addition is computed per
word. mod1110 z3™.
5.1 INTRODUCTION 197


in Figure 5.1. This method of hashing is known as the MerkleeDamghrd
construction (or Damg8rd-Merkle construction, depending on who you ask).
It can be shown that if the compression function is collision resistant, then
so is the corresponding hash function. This is somewhat analogous to the
Feistel construction for block ciphers (see Section 4.3), where the security of
the resulting cipher essentially reduces to the security of the round function.

IV


M˜l- II
{I
T
compression
512




1
function 128



Ml 512
function 128




128


c
hash value

Figure 5.1: Hashing multiple blocks.

Suppose that a message consists of one 512-bit block M . Let IV be
the constant initial value for the first block. Then the hash is computed
as h ( M ) = f ( I V , M ) , where f is a known function. For the hash func-
tions MD4 and MD5 we consider later in this chapter, the output h ( M ) is
always 128 bits, as is the initial constant IV. Then f corresponds to the
compression function together with the addition operation as illustrated in
Figure 5.1.
On the other hand, suppose that M = ( M o ,M I ) consists of exactly two
512-bit blocks. Then f is applied twice and we have3



3For both MD4 and MD5, the message is padded before hashing-even if the message
is already a multiple of 512 bits. Here, we implicitly assume that the message A 4 includes
the padding.
HASH FUNCTIONS
198


This easily generalizes to any number of blocks, so that for a given message
of the form M = (Mo,M I , .. . , Mn-l), we apply the function f a total of n
times. It is easy t o verify that

h ( M ) = f(h(Mo, M1,. . . , Mn--2),Mn-l).
One consequence of this approach to hashing is that if we have any two
messages M and M™ with h ( M ) = h(kJ™), then h ( M , X ) = h ( M ™ , X ) for
any X. That is, given a collision, we can extend the colliding messages with
any common value.
Now consider the keyed hash problem mentioned above. In this case,
Alice wants to incorporate a key into the hash of the message M . Alice
decides to compute the keyed hash of her message M as y = h ( K ,M ) and
she sends y and M to Bob. Suppose that the length of ( K ,M ) happens to be
a multiple of 512 bits. Now suppose that Trudy intercepts the message and
she replaces M with M™ = ( M , X ) ,where X consists of exactly one block.
Since Trudy does not know the key K , it appears that her tampering will be
detected. However, since Trudy knows h ( K ,)
, she can use the fact that,
[A
h ( K ,M™) = h ( K ,M , X ) = f ( h ( K M ) ,X )
,
to conipute y™ = h ( K ,M ™ ) , without knowledge of the key K . This defeats the
purpose of the keyed hash.
Suppose that instead of pre-pending the key, Alice appends the key to
the message before hashing. Then Alice sends y = h ( M ,K ) along with M to
Bob. If it should happen that there is a collision for M , that is, if there exists
some M with h ( M ™ ) = h ( M ) ,then, assuming the message M is a niultiple
of the block length,

h ( M ,K ) = f(h(AJ),K ) = f ( h ( M ™ ) K ) = h(M™,K ) .
,
In this case, Trudy can replace M with M™ and the resulting keyed hash value
would not need to be altered. Again, this defeats the purpose of the keyed
hash.
Although this second attack is perhaps less serious than the first -since
a collision must be found, in which case we consider the hash broken-both
attacks are easily prevented by computing a hashed message authentication
code, which is mercifully shortened t o HMAC. In effect, the HMAC more
thoroughly mixes the key into the hash value.
HMAC is defined in RFC 2104 [86] as follows. Let B be the number of
bytes in a hash block. For most popular hash functions, B = 64. Define

repeated U times
ipad = 0x36

and
repeated B times.
opad = Ox5C
5.1 INTRODUCTION 199


Then the HMAC of the message M is
HMAC(M, K ) = h ( K @ opad, h ( K C‚¬ipad, M ) ) ,
where h is a cryptographic hash function. For the HMAC, two hashes are
computed, but the outer hash is only computed over a small input, not the
entire message M (which could be extremely large). An HMAC can be used
to provide message integrity, as can a MAC or a digital signature. However,
an HMAC has many other nifty uses as well.
Note that an HMAC can be used to detect errors that occur in trans-
mission. However, as with any cryptographic integrity protection scheme,
the HMAC provides much more than any error detection method (such as
a cyclic redundancy check, or CRC) can provide. By using a cryptographic
hash, the HMAC is resistant to attack by an intelligent adversary, whereas
any error detection scheme can be defeated by such an adversary. See Sec-
tion 3.4 and [142] for examples of the perils of using an error detection scheme
when a cryptographic integrity check (such as HMAC) is required.
We note in passing that a symmetric cipher can be used as a hash function
and vice versa. However, there are certain subtle issues that arise. For
example, a block cipher that is used as a hash function must resist certain
attacks that are not relevant when it is used as a cipher; see Problem 2.
In the next two sections we consider the cryptanalysis of the hash func-
tions MD4 and MD5. The function MD4 was designed to be fast and in hash
function design, as with most crypto, there is an inherent tradeoff between
speed and security. It did not take long before fundamental weaknesses in
MD4 were discovered, but it still took some time before anyone was able
to produce an actual collision. We discuss Dobbertin™s original attack on
MD4 [42], which is a very clever and elegant piece of work.
MD5 is a much different story. After some chinks were visible in the MD4
design, it was modified and strengthened (at the expense of some speed)
and the result was dubbed MD5. The hash function MD5, and its close
cousin SHA-1, proceeded to become the mainstays of hashing. Recently,
an MD5 collision was found due to some extraordinary cryptanalysis, which
we outline in this chapter. However, the cryptanalysis of MD5 is not so
elegant as that of MD4, and the attack has never been clearly explained by
its inventor (or anyone else, for that matter). At the time of this writing,
the kinks are still being worked out of the MD5 attack. In spite of this,
many computational improvements to the original attack have been found
recently. Whereas the original attack took several hours on a supercomputer,
the current best attacks take about two minutes (on average) on a PC.
Another significant difference between the MD4 and MD5 attacks is that
the former can be used to find a “meaningful” collision, while the latter
cannot. However, we present an example that shows that both the MD4
attack and the MD5 attack create realistic security threats.
HASH FUNCTIONS
200


Birthdays and Hashing
5.2

“HOW many days are there in a year?”
“Three hundred and sixty-five,” said Alice.
“And how many birthdays have you?”
“One.”
“And i f you take one from three hundred and sixty-five, what remains?”
“Three hundred and sixty-four, o f course. ”
Hurnpty Dumpty looked doubtful.
˜(I™drather see that done on paper,” he said.
Through the Looking Glass
˜




In this section we discuss the so-called birthday problem and its implications
for hashing. The birthday problem provides the necessary background for
a discussion of brute force attacks on hash functions, which are roughly the
equivalent of exhaustive key search attacks on symmetric ciphers. We also
consider a clever hashing attack that relies on the birthday problem to create
a shortcut attack for certain applications, provided the hash function employs
the IllerkleeDamg8rd construction.


The Birthday Problem
5.2.1
Suppose that Trudy is in a room containing a total of N people (including
herself). What is the probability that at least one of the other N - 1 people
has the same birthday as Trudy? Assuming that birthdays are uniformly dis-
tributed among the 365 days in a year, the answer is not difficult to compute.
As with many discrete probability problems, it is easier to compute the prob-
ability of the complement and subtract t h e result from one. In this case, the
complement is that none of the other N - 1 people have the same birt,hday
as Trudy. For each person this probability is 364/365, so that for all N - L
people, the probability is (364/365)N-1. Consequently, the probability we
want is
(5.1)
1 - (364/365)Ne1.

By setting (5.1) equal to 1/2 and solving for N , we can find the number
of people that must be in a room before we expect someone to have the same
birthday as Trudy. Doing so, we find that if N 2 254, then the probability
is greater than 1 / 2 and we therefore expect to find someone with the same
birthday as Trudy. Intuitively, the answer should be about the number of days
in a year, and since there are 365 days in a year, the answer 254 is reasonable.
Note that in this version of the birthday problem we are comparing every
birthday to one specific birthday, namely, Trudy™s. Also note that, more
5.2 BIRTHDAYSA N D HASHING 201


generally, if there are 111 possible outcomes, we expect to need about 11 1
comparisons before we find a “collision”.
On the other hand, suppose that we want to find the probability that
any two (or more) people in a room share the same birthday, where there
are N people in the room. It is again easier to compute the probability of the
complement and subtract from one. Here, the complement is that all people
have different birthdays, so that the desired probability is given by

+ 1)/365,
1 - 365/365 .364/365 .363/365.. ˜ (365 - N (5.2)
provided that N 5 366.
In this case, to find the number of people that must be in the room before
we expect two or more to share the same birthday, we set (5.2) equal to 1/2
and solve for N . Doing so, we find that if N 2 23, then the probability
in (5.2) is greater than l/2. That is, provided that there are at least 23
people in a room, we expect two or more to share the same birthday.
This fact is sometimes referred to as the “birthday paradox” because, at
first glance, it appears paradoxical that only 23 people suffice when there
are 365 days in a year. However, this result is not as paradoxical as it might
seem. We are comparing every birthday to every other birthday, so with N
people in the room, we are making ):( comparisons, and once we have made
about 365 comparisons, we expect to find a match. By this logic, the solution
to this version of the birthday problem is the smallest value of N for which




which yields N = 28. This is close to the precise value of N = 23. As
m, where M is the number of possible
an approximation we often use
= 19, which is
outcomes. For actual birthdays, 111 = 365 and we have
indeed a good approximation to the precise result N = 23.

5.2.2 Birthday Attacks on Hash Functions
Recall that a cryptographic hash function must provide weak collision resis-
tance and strong collision resistance. If we are given a particular hash value,
h ( z )and we can find a w such that h ( w ) = h ( z )then we have “broken” the
hash function, since we have violated the weak collision resistance property.
The brute force attack is to randomly generate w, compute the hash and
compare the result to h ( z ) ,repeating until a collision is found. If the hash
function h generates an n-bit output, the first version of the birthday problem
discussed above implies that we will need to compute about 2n hashes before
we expect to find such a w. Therefore, for h to be considered secure, it is
necessary (but not sufficient) that it is infeasible for Trudy to compute 2”
hashes. This is comparable to an exhaustive search for a cryptographic key.
HASH FUNCTIONS
202


If we can find a pair x and w such that h(x) = h(w) then we have broken
the hash h , since we have violated the strong collision resistance property.
In this case, Trudy can conduct a brute force attack by randomly generating
values, computing the hash, and comparing the result t o all previously com-
puted results. From the second version of the birthday problem discussed
above, the number of hashes required to find a collision is about @ = 2n/2.
Consequently, a hash function that generates an n-bit output can, at best,
provide a level of security comparable to a symmetric cipher with an n/2-bit
key. In [110] the authors discuss how to use parallel computation to gain a
significant improvement in this birthday attack on a hash function.
Of course, it is always possible that a cryptanalyst will find a shortcut
attack. In any case, these two birthday attacks give upper bounds on the
theoretical security of a hash function.
Next, we discuss two attacks that illustrate the way that these birthday
attacks could be put to practical use. First we consider a generic attack on
digital signatures. Then we outline a birthday attack that applies to any hash
function h that employs the Merkle-Damggrd construction.


Digital Signature Birthday Attack
5.2.3
The important role of hashing in the computation of digital signatures is
discussed in Section 5.1, above. Recall that if M is the message that Alice
wants to sign, then she computes S = [h(M)],41ice and sends S and A4 t o
Bob, where [X]*licedenotes “encryption” with Alice™s private key.
Suppose that the hash function h generates an n-bit output. As discussed
in [162], Trudy can, in principle, conduct a birthday attack as follows:

Trudy selects an “evil” message E that she wants Alice to sign, but
0

which Alice is unwilling to sign. For example, the message might state
that Alice agrees t o give all of the money in her bank account to Trudy.

Trudy also creates an innocent message I that she is confident Alice is
0

willing to sign. For example, this could be a message that appears to
be routine business of the type that Alice regularly signs.

Then Trudy generates 2n/2 variants of the innocent message by making
0

minor editorial changes. These innocent messages, which we denote
by Ii, for i = 1 , 2 , . . . , 2n/2, all have the same meaning as I , but since
the messages differ, their hash values differ.

Similarly, Trudy creates 27L/2 variants of the evil message, which we
0

denoted by Ei, for i = 1 , 2 , . . . ,2n/2. These messages all have the same
meaning as the original evil message E , but their hashes differ.
5.2 BIRTHDAYSA N D HASHING 203


Trudy hashes all of the evil messages E, and all of the innocent mes-
sages Ii. By the birthday problem, she can expect to find a collision,
say, h ( E j ) = h ( l k ) . Given such a collision, Trudy sends I , to Alice,
and asks Alice to sign it. Alice agrees to do so and she returns I ,
and [h(lk)]*lice to Trudy. Since h ( E j ) = h ( l k ) , it therefore follows
that [ h ( E j ) ] ˜ l =˜[h(lk)]Alice and, consequently, Trudy has effectively

obtained Alice™s signature on the evil message Ej.

Note that in this attack, Trudy has obtained Alice™s signature on a mes-
sage of Trudy™s choosing without recovering Alice™s private key, or attacking
the underlying public key system in any way. This attack is a brute force
attack on the hash function h, as it is used for computing digital signatures.
To prevent this attack, it is necessary (but not sufficient) that n, the number
of bits the hash function generates, is large enough so that Trudy cannot
compute 2n/2 hashes.

Nostradarnus Attack
5.2.4
Finally, we describe an interesting attack due to Kelsey and Kohno [80]that is
applicable to any hash function that employs the Merkle-Damggrd construc-
tion (see Figure 5.1, above). The hash functions MD4 and MD5 discussed
later in this chapter are of this type, as are the popular SHA-1 and Tiger
hashes.
Hash functions are often used in practice to prove prior knowledge or
to commit to something without revealing the “something.” For example,
suppose that Alice, Bob and Charlie want to place sealed bids online. Since
they do riot trust that their bids will remain secret, neither Alice, Bob nor
Charlie wants to submit their bid until the other two have submitted theirs.
One possible solution to this problem is the following. First, Alice determines
her bid A, Bob determines his bid B and Charlie determines his bid C. Then
Alice submits h ( A ) ,Bob submits h ( B ) ,and Charlie submits h ( C ) . Once all
three bids have been received, they are posted online, at which point Alice,
Bob and Charlie can submit their respective bids, namely, A, B , and C . If
the hash function h is one-way, there should be no disadvantage to submitting
a bid before the other bidders. Also, if h is collision resistant, it should not
be possible for Alice to change her bid once B and C have been revealed (and
similarly for Bob and Charlie).4
Now consider the following scenario [80]. Trudy claims that she can pre-
dict the future. To prove it, on January 1, 2008 she publishes y, which she
where 2 gives the final Standard and Poor™s 500 (S&P 500) in-
claims is h(z),
dex5 for December 31, 2008, along with various other predictions about events
“However, without modification, this protocol is insecure; see Problem 6.
˜The S&P 500 is a well-known stock market index.
HASH FUNCTIONS
204


that will occur in 2009 and beyond. Suppose that on January 1, 2009, Trudy
reveals a message z such that y = h ( z )and z correctly predicts the S&P 500
index for December 31, 2008, followed by a rambling set of predictions about
future events that have not yet occurred.
Does this prove that Trudy can foretell the future? It would seem that
by publishing y in advance, Trudy is committed to a specific x, unless she
can violate the one-way property of the hash function h. It is generally much
more difficult to violate the “one-way-ness” of a hash function than to find
collisions. Barring any shortcut attack, if h generates an n-bit hash, then
about 2n hashes need to be computed before Trudy could expect to find a
message x that hashes to a specified value y, while only about 2n/2 hashes
need to be computed to find a collision. So, in the scenario outlined in the
previous paragraph, it would seem that if n is sufficiently large so that it is
infeasible for Trudy to compute 2n hashes and no shortcut attack on h exists,
then Trudy can legitimately clairn to be thc new Nostradamus.˜
However, in [SO] it is shown that, Trudy can cheat, provided the hash
function h uses the Merkle-Damggrd construction and that Trudy is able to
compute collisions. By the birthday problem, if 2n/2 is a feasible amount of
work (where the hash h generates an n-bit output), Trudy can find collisions.
Of course, if there is a shortcut collision attack on h, then Trudy may be
able to compute collisions even more efficiently than via the birthday attack.
But for the remainder of this discussion, we assume that Trudy computes
collisions by the birthday attack and that 2”12 is a feasible amount of work,
while 2n is not. Under these assumptions, we describe how Trudy can cheat.
Trudy must specify the value y in advance. Then when she knows the
S&P 500 index for December 31, 2008, she wants to create a message that
includes the S&P 500 result and hashes to y. More precisely, on January 1,
2009 Trudy knows the final S&P 500 index for December 31, 2008, and she
sets P , the prefix, equal to this index result. Then Trudy must determine a
suffix S so that h(P,S) = y, where y is the previously specified “hash” value.
That is, the prefix P and y are specified, but Trudy is free to choose the
suffix S so that y = h(P,S). Of course, if Trudy can randomly 2n suffixes S
arid compute the corresponding hashes, then she would expect to find one for
which y = h(P,S ) . But we assume that this is an infeasible amount of work,
that is, Trudy cannot perform a brute force pre-image attack.
Kelsey and Kohno [80] describe their attack as a “herding” attack, since
a specified prefix P is “herded” into the specified hash value by selecting
suffixes S and computing collisions (as opposed to pre-images). Furthermore,
in this attack Trudy can has considerable control over S , so that it is possible
for her to construct meaningful suffixes-instead of random gibberish, which
˜Nostradamus (1503 ˜1566)published numerous prophecies. His modern supporters
clairn that he predicted most of the major events of recent history. Ironically, Nostradamus™
predictive powers seen1 to work best in retrospect.
5.2 BIRTHDAYSA N D HASHING 205


might raise suspicions about her prognosticating abilities.
The attack relies on a data structure, the “diamond structure”, which
is essentially a cleverly constructed directed tree. An example of a small
diamond structure appears in Figure 5.2. In this figure, the vertices dij rep-
resent intermediate hash values (that is, compression function results) and IV
is the IV associated with the hash h (although any compression function out-
put could be used in place of the IV in the diamond structure). The edges all
represent messages, and the edges that meet at a vertex represent a compres-
sion function collision. The message blocks MOthrough M7 can be selected
arbitrarily, but the blocks Mij must be chosen so that the denoted collisions
occur. For example, in Figure 5.2, we have

dlo = f ( d o 0 , Moo) = f ( f ( I V , Mo),Moo)
and
MOl) = f ( f ( I V , Ml), MOl),
dlo = f(do1,

where f is the compression function of the hash h, See Figure 5.1 and the sub-
sequent discussion for more details on the compression function f in relation
to h.

f




\

1 \
% M,
l
d,, d,,
M07



Figure 5.2: A small diamond structure.

Note that in Figure 5.1 the messages in the rightmost diamond must
include any necessary padding so that d30 is a legitimate hash value. For
hash functions such as MD4 and MD5 this is easily accomplished.
By the birthday problem we expect to find a collision within any diamond
if we generate 2n/2 + an/™ messages. To see why this is the case, consider, for
example, the diamond corresponding to

dl0 = f(doo, Moo) = f(do1, Moll. (5.3)
When determining a pair of message blocks Moo and for which (5.3)
holds, we only compare the hashes computed using putative Moo with those
HASH FUNCTIONS
206


computed from putative M o and vice versa. A collision between two hashes
˜
values (or two different putative Mol) is of no
with different putative MOO
use since such a collision would not yield the “diamond” that we seeks. Con-
sequently, to generate the necessary 2n comparisons, it is most efficient to
conipute 2n/2 putative M o o and 2n/2 putative M o and compare the resulting
˜
hashes.
Thc “height” of the diamond structure is the number of doj elements in
the directed graph. For example, the diamond structure in Figure 5.2 has
a height of eight. Suppose that the height of a given diamond structure
is 2 k . Then there are 2k - 1 diamonds, so the work required to construct the
structure is, by the birthday problem, about
2 . 27L/2(2k - 1) 2n/2+k+l

It is claimed in [80] that this work factor can be reduced to about 2n/2+k/2+2.
Now we have the necessary machinery to describe the Nostradamus attack
in detail. The attack consists of two phases. In the first phase, Trudy con-
structs a diamond structure and she determines the value y that she will claim
as the hash of her prediction. Then in phase 2 , a prefix P is given (consisting
of Trudy™s prediction) and Trudy must choose ;t suffix S so that, y = h(P,5 ).
In phase 1 of the attack, Trudy constructs a diamond structure of height 2k
and she claims that the hash of her stock market prediction is d k ˜ the right-
,
most value in the diamond structure. That is, Trudy claims that y = &” is
the hash of 2 , whcre 5 includes her prediction for the closing S&P 500 index
on December 31, 2008, along with other unspecified predictions for 2009 and
beyond.
Then on January 1, 2009, Trudy is ready to begin phase 2 of the attack.
Trudy creates the prefix P which consists of the closing S&P 500 index for
Decernber 31, 2008. She then creates a series of suffixes S, each consisting
of some vague prediction of future events, and for each of these she applies
the compression function of h to ( P ,S). Assuming that ( P ,5) is a single
message block, let u = f(IV, P, S™), where f is the compression function

of h,. Trudy compares each computed u to all 2k of the doj and she repeats

this until a mat™ch is found. Once Trudy finds such a match, she simply
extends ( P ,5 by following the directed edges in thc diamond structure until
)
she arrives at y = dkO. Appending the block on the traversed edges of the
directed graph to ( P ,S), Trudy obtains a message M that hashes to y. Most
importantly, the message M contains P , the S&P 500 index for December 31,
2008, along with other predictions of future events. This is precisely what
Trudy promised to deliver.
For example, suppose Figure 5.2 is Trudy™s diamond structure. Further,
suppose that, Trudy determines S™ such that f( IV, P, S) = d02. Then

h ( P ,s M02, m111, fi120)
, =y
5.2 BIRTHDAYSA N D HASHING 207


and Trudy™s “prediction” is the message



In [go], the authors refer to the process of following the directed path in the
diamond structure as “herding” the prefix to the desired hash value.
Since the diamond structure is of height 2k and h is an n-bit hash, the
expected work for phase 2 of the attack is 2n-k. As mentioned above, the
claimed work for phase 1 is 2n/2+k/2+2.To minimize the total work, we set
the phase 1 and phase 2 work factors equal to each other and solve for k .
Doing so, we find
n-4
k=-.
3
Note that the message (P,S™)is padded with k additional blocks to obtain M
+
so that the overall message consists of k 1 messages. It would be possible to
insert additional blocks, but it is probably desirable to minimize the overall
size of the message.
Suppose the Nostradamus attack is applied t o the MD5 hash function,
which generates a 128-bit output. Then




which implies that the diamond structure has a height of 241 and the overall
work for the attack is about 2n-k = 287. While this is an enormous amount
of work, it is far less than the 212™ work that would be required in a naive
brute force pre-image attack.
There are several possible refinements to this attack. For example, Trudy
has a great deal of control over the message blocks, so that when creating
the diamond structure, she can choose messages that provide meaningful
predictions. That is, Trudy can use a similar approach t o that discussed in
Section 5.2.3, above, to make the messages meaningful.
In [80],several interesting potential applications for the Nostradamus at-
tack are discussed. These attacks include stealing credit for an invention,
editing a message without changing the hash (which has unpleasant implica-
tions for digital signatures) and random number “fixing”, among many oth-
ers. In effect, any application where a hash is used to commit to something
is potentially susceptible to this attack.
In the remainder of this chapter, we discuss cryptanalytic attacks on two
well-known hash functions, namely, MD4 and MD5. Although the MD4 at-
tack is more efficient, both of these attacks provide highly efficient methods
for generating collisions. Unlike the more generic attacks presented in this
section, to understand the attacks in the next two sections, we must dig deep
into the internal workings of the MD4 and MD5 hash functions.
HASH FUNCTIONS
208


MD4
5.3

“My dear! I really must get a thinner pencil. I can™t manage this one a bit;
it writes all manner o f things that I don™t intend--”
- Through the Looking Glass



Message Digest 4, or MD4, is a hash algorithm proposed by Rivest in 1990.
MD4 was designed to be fast, which necessitated taking a few risks, with re-
spect to security. By 1992 significant weaknesses had been found (although no
true collision was forthcoming) which led Rivest to produce a strengthened-
but slower--version known as MD5.
In 1998, Dobbertin [34, 41, 421 found the first true MD4 collision, and he
gave an extremely clever and efficient algorithm for generating such collisions.
Furthermore, Dobbertin demonstrated that his algorithm can be used to find
collisions that might actually matter in the real world. In this section, we
describe Dobbertin™s attack on MD4. Other attacks on MD4 are now known,
but none provide as much insight into the underlying weakness of the hash
function as the attack presented liere.
Part of Dobbertin™s attack relies on differential cryptanalysis, while the
heart of the attack depends on finding a solution to a system of nonlinear
equations. The attack is fairly technical and involved, but the resulting al-
gorithm is practical, with a work factor that is approximately equal t o the
computation of 220 MD4 hashes.


MD4 Algorithm
5.3.1
The MD4 algorithm is described by Rivest in RFC 1320 [ l a l ] , where an
efficient implementation (in C) is given. Here, we only provide enough details
to implement the attack described below, and we use different notation than
is found in [ l a l ] .
MD4 operates on 32-bit words. The four bytes of each word are inter-
preted so that the leftmost byte is the low-order (least significant) byte. That
is, a little-endian convention is followed. This is not a concern for the attack
described here, but it does become an issue if we want to construct meaningful
collisions.
Let M be the message t o be hashed. The message M is padded so that
its length (in bits) is equal to 448 modulo 512, that is, the padded message
is 64 bits less than a multiple of 512. The padding consists of a single 1 bit,
followed by enough zeros to pad the message to the required length. Padding
is always used, even if the length of M happens to equal 448 mod 512. As a
result, there is at least one bit of padding, and at most 512 bits of padding.
Then the length (in bits) of the message (before padding) is appended as a
5.3 MD4 209


64-bit block. Padding is not a concern for the attack presented here; for the
precise details, see [lal].
The padded message is a multiple of 512 bits and, therefore, it is also
a multiple of 32 bits. Let M be the message and N the number of 32-bit
words in the (padded) message. Denote the message words as Y,, so that
M = (Yo,Yl,. ,Y N - ˜Due to the padding, N is a multiple of 16.
.. ).
Define the three functions
F ( A , B , C )= ( A A B ) v ( ˜ A A C ) (5.4)
G ( A , B , C ) ( AA B ) v ( AA C ) v ( BA C) (5.5)
=

H(A,B,C) A @ B @ C (5.6)
=

where is the bitwise AND operation, “V” is the bitwise OR operation,
˜˜@™ is the XOR, and “1A” is the complement of A. Each of these functions
has a simple interpretation. The function F uses the bits of A to select
between the corresponding bits of B and C , the function G is a “majority
vote” in each bit position, while H can be viewed as a bitwise parity function.
The MD4 hash algorithm appears in Table 5.1. In this algorithm, addition
of 32-bit words are to be taken modulo 2”.
In MD4, each 512-bit block is processed through three rounds, denoted
as RoundO, Roundl, and Round2 in Table 5.1. Taken together, these three
round functions and the final addition operation comprise the MD4 compres-
sion function, since they compress the 512-bit block and the 128-bit initial
value into a 128-bit result. Table 5.2 shows how each of the three rounds is
expanded into 16 steps, where the function F is used in round 0, the func-
tion G in round 1, and the function H in round 2, and “<<<” is a left rotation.
Round i use the constant Ki, where
KO= 0x00000000, and K2 = OxGed9ebal.
K1 = Ox5a827999,

Note that KO= 0, but we include it here to simplify some of the notation.
The three rounds give a total of 48 steps, each involving one application
of F , G or H . We number these steps consecutively, from 0 through 47, where
in round 0, steps 0 through 15 occur, in round 1, steps 16 through 31 occur,
and round 2 consists of steps 32 through 47.
The shift for step i is denoted s i . The values of s i , for i = 0 , 1 , . . . ,47,
are listed in Table 5.3. In Table 5.1, the permutation of the input words is
The values of CJ(˜), i = 0, 1 , 2 , . . . ,47,
denoted by 0, that is, Wi = X a ( z ) . for
are given in Table 5.10.
At step i of MD4, only the 32-bit value Qi changes. A single MD4 step is
illustrated in Figure 5.3, where
+
F ( A ,B ,C ) KO if 0 5 i 5 15
+
G ( A , B , C ) K1 if 16 5 i 5 31
H ( A ,B , C ) + K2 if 32 5 i 5 47.
H A S HFUNCTIONS
210


Table 5.1: MD4 Algorithm

// Y1,. . ,Y N - ˜ ) ,
.
iLf = (Yo, message to hash, after padding
// Each Y, is a 32-bit word and N is a multiple of 16
MD4(111)
/ / initialize (A,B, C , D ) = IV
c,
( A ,B , D ) = (0x67452301,Oxef cdab89,Ox98badcfe,0x10325476)
for i = 0 t o N/16 - 1
// Copy block i into X
X j = Y l ˜ i +for j = 0 t o 15
j,
// copy to w
x
Wj = Xocj,, f o r j = 0 to 47
/ / initialize Q
(Q-4, Q-3, Q-2, Q-1) = (A, D , C , B )
/ / Rounds 0, 1 and 2
RoundO(Q, X )
Roundl(Q, X )
Round2(Q, X )
// Each addition is modulo 232
+ +
+
(A,B , C ,D ) = (Q44 Q-4, Q47 Q-I, Q46 Q - 2 , Q45 + Q - 3 )
next i
return A, B !C, D
end MD4


MD4 Attack
5.3.2
The attack described in this section is due to Dobbertin [42]. Our descrip-
tion uses different notation than the original, and we have rearranged and

Qi-2 Qi-3 Qi-4

I

Wi
<<< s.
si



Qi- 1
Qi Qi-2 Qi-3



Figure 5.3: MD4 step.
5.3 MD4 211


Table 5.2: MD4 Rounds

RoundO(Q, W )
// steps 0 through 15
for i = 0 t o 15
+ Wi+ K O )<<
+ F(Qi-I, <
Qi-3)
Qi = (Qi-4 ˜i
Qi-2,
next i
end Round0

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

Round2(Q, W )
// steps 32 through 47
for i = 32 t o 47
+ Wi+ K2) << si
+ H(Qi-1,Qi-2, <
Qi = (Qi-4 Qi-3)
next i
end Round2


expanded on the exposition at several points.
This attack finds two distinct 512-bit blocks that hash to the same value,
thereby yielding a collision. As noted in Section 5.1, if any common bit
string is appended to two colliding blocks, the resulting strings will also yield
a collision.
Dobbertin™s attack includes a differential phase, where we require that the
pair of 512-bit inputs satisfy a certain differential property at an intermediate
stage of the algorithm. When this differential property holds, then with a


Table 5.3: MD4 Shifts

8
7
Stepi 1 0 3 4 5 6 9 10 13 14 15
2 11 12
1
7 7
Shift s;I 3 19 3 19 3 19 3 19
7 7
11 11
11 11
Step i 16 17 19 23 24 25 26 27 28 29 30 31
20 21 22
18
Shifts, 3 5 9 13 3 5 9 3 5 9 13 3 9 13
13 5
37
Step i 32 33 35 35 36 38 39 40 41 42 43 44 45 46 47
9
Shift s7 3 9 15 3 9 15 3 9 15 3 15
11 11 11 11
HASH FUNCTIONS
212


Table 5.4: MD4 Input Word Order

4 5 6 7 1011 12 131415
Stepi 0 1 3 8 9
2
2 4 5 7 10 11 12 13 14 14
˜ ( i )0 1 3 6 8 9
Step i 16 17 24
23 29 30 31
19 20 22 25 26 27 28
18 21
5
o(z) 0 4 8 13
12 1 6 10 14 7 11 15
9 2 3
Step i 32 33 35 35 36 37 38 39 40 41 42 43 44 45 46 47

<<

. 8
( 16)



>>