= 1/9

H ( X ,Y , = H ( X ,Y + l,z - l ) , 2)

1/3.

H ( X ,Y , = H ( X ,Y , 2) 2

+ 1)

1/3.

12. Consider the formulas given in Problem 11. Suppose that we replace the 32-bit words X, Y ,and Z with 8-bit bytes x, y and z . Then we can compute the probabilities exactly. Write a computer program to verify the claimed probability in each part of Problem 11 using 8-bit words instead of 32-bit words.

260 13. Verify equations (5.30) and (5.32).

14. The continuous approxiniation phase of the MD4 attack relies on the fact that for the functions F and G in (5.4) and (5.5), nearby inputs produce nearby outputs. Suppose that the 32-bit words A , B and C are rcplaced with 8-bit bytes a , b and c. Furthermore, suppose that a differs from u in exactly one randomly selected bit position, b differs from b in exactly one randomly selected bit position, and c differs from c in exactly one randomly selected bit position. Write computer programs to answer the following.

a. Find the probability that F ( u , b. c ) and F(a , b , c ) differ in exactly k bit positions, for k = 0 , 1 , 2 , . . . .8.

b. Find the probability that G ( a , b . c ) and G(a ,b ,c ) differ in exactly k bit positions, for k = 0 , 1 , 2 , . . . ,8.

c. Find the probability that H ( a , b , c ) and H(a ,b ,c ) differ in exactly k bit positions, for k = 0 , 1 , 2 , . . . , 8 , where H is defined in (5.6). 15. Implement tho continuous approximation equation solving phase of the MD4 attack. Use your program to provide empirical estimates of the following. a. How many iterations, on avcrage, are required before the chcck condition in (5.35) holds

b. In the continuous approximation, on average, how many iterations are required before the solution converges That is, given a solution to (5.35) how many iterations are needed before (5.36) is satisfied

c. The continuous approximation can sometinies fail to converge. Using a cutoff of 100,000 iterations, what is the probability that the continuous approximation fails to converge

d. How marly nonadmissiblc solutions are computed, on average, before one admissible solution is found

16. mJrite a program to implement the differential phase of the MD4 attack. Use your program to empirically estimate the probabilities that appear in Table 5.5.

17. Dobbertiri [42] claims that the probability of siiccess of the differential phase of the MD4 attack is 1/222. Assuming this is the case, show that the work factor for Dobbertin s attack is roughly equivalent to the cornputation of 220 h4D4 hashes.

18. Approximately how many MD4 collisions can be found using Dobbertin s attack 19. Let M = ( X OX i , . . . , X i s ) ,where ,

= 0~9074449b,

= Ox8bf37fa2, = Ox63247e24,

= 0~1089fc26, = Oxld630daf,

X s = 0x4e4f430a1 = 0x43415254, X7 = Ox410aOa54, = 0x68742074, Xg = 0x72702065, = 0x20656369, Xi1 = 0 ~ 2 4 2 0 6 6 6 f ,

X = 0 ~ 2 ~ 3 6 3 7 3 1 , i 3 = 0x20353934, Xi5 = 0 ~ 7 7 6 f 6 ~ 4 2 . = 0~20666~41,

a. Compute the MD4 hash of M . b. Let MI be the same as M , with the exception that Xi2 is replaced by X i 2 = X12 1, that is, X i 2 = 0x2~363732.Compute the MD4 hash of MI.

c. Interpret 111 arid M as ASCII text, where the byte order of each X i is little endian. Then, for example, X6 consists of the bytes

(0x54,0x52,0x41,0x43)