ńňđ. 8 |

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 )

0˜

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

i˜

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 |