1. Consider a hash function that starts with an 32-bit initial value of c09db506 and repeatedly XORs it with 32-bit blocks of the input to produce a 32-bit output. For example, the input de0fc223 would generate the following output: () = = and the input cd1aa915 f08d7db7 would generate the following output: ( ) = = (a) Approximately how many steps would be required to perform a brute force attack to find a preimage for a given output of this hash function? (2 pts) (b) Approximately how many steps would be required to perform a brute force birthday attack to find a collision for this hash function? (2 pts) (c) Use the properties of the XOR operation to find a 32-bit preimage for the output 666cdce9. (3 pts) (d) Find a 32-bit second preimage for the output fd0a61a4 calculated above. (3 pts) (e) Find a collision other than the one demonstrated by your answer to (d). (hint: pick a 32-bit input, then find a 64-bit input that generates the same output using the properties of XOR.) (3 pts) 2. The birthday problem poses the following question: how many people do you need in a room so that it is likely that two of them have the same birthday? Assuming that all 366 birthdays are equally likely (they aren't since February 29th only happens every four years or so, but it makes the problem slightly simpler to understand) we can determine the following: If there are two people in the room there is a 365 366 or 0.9973 probability that they have different birthdays, giving us a 1 0.9973 = 0.0027 probablity that they have the same birthday. If there are three people in the room there is a 365 366 364 366 or 0.9918 probability that all three people have different birthdays, giving us a 1 0.9918 = 0.0082 probability that at least two of them have the same birthday. Continuing this process, it turns out that only 23 people are needed for there to be a probability of at least 0.5 that two people have the same birthday.This is the foundation of the concept of the birthday attack on a hash function. A hash function that produces an -bit output can produce 2 different values. If is suitably large, roughly 2/2 inputs need to be tried before a collision is likely to be found. For smaller values of we can compute the number of inputs required using the process outlined above for the birthday problem. For the following questions, assume there is a hash function that generates a 4-bit output and that every possible output is equally likely to be generated. (a) How many different hash values can this function generate? (2 pts) (b) Assume that for a given input 1, 1 = (1). Assuming 2 1, how many possible values for 2 = (2) are different than 1? (2 pts) (c) What is the probability that 2 is different than 1? (3 pts) (d) Assume that 1 and 2 are different values. Assuming 3 1 and 3 2, how many possible values for 3 = (3) are different than both 1 and 2? (2 pts) (e) Assuming 1 and 2 are different, what is the probability that 3 is different from both 1 and 2? (3 pts) (f) In general, what is the probability that 1, 2 and 3 are all different? (3 pts) (g) What is the probability that at least two of 1, 2 and 3 are the same? (3 pts) (h) Continuing the process outlined in (d) through (g), how many different inputs must be tried before there is at least a 0.5 probablity that two or more outputs have the same value? (3 pts) 3. Given a 32-bit plaintext block and a 32-bit key , let (, ) = ( + ) mod 232 For example, if = and = ), (, ) = ( + ) mod 232 = mod 232 = Let be a compression function defined by using the Davies-Meyer construction with block cipher . Let be a hash function defined by using the Merkle-Damgrd construction using as the compression function and 0 = as the initial value for the 32-bit internal state. Compute the chaining values 1, 2, 3, and 4 for the following message (broken into four 32-bit blocks): = (4pts each value)