Question

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: 365 • If there are two people in the room there is a or 0.9973 probability that they have different birthdays, giving us a 1 – 0.9973 = 0.0027 probablity that they have the same birthday. 365 364 • If there are three people in the room there is a 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. 366 366 This is the foundation of the concept of the birthday attack on a hash function. A hash function that produces an n-bit output can produce 2" different values. If n is suitably large, roughly 2n/2 inputs need to be tried before a collision is likely to be found. For smaller values of n 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 Hash, 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?
(b) Assume that for a given input M , H = Hash (M2). Assuming M2 M2, how many of the possible values for H2 = Hash2(M2) are different than H?
(C) What is the probability that Hy is different than Hy?
(d) Assume that Hy and H, are different values. Assuming M3 # M, and M3 # M2, how many of the possible values for H3 = Hash2(M) are different than both H1 and H2?
(e) Assuming Hy and H2 are different, what is the probability that H3 is different from both H, and H2?
(f) In general, what is the probability that H4, H, and Hz are all different? (hint: multiply the probability that Hy and H, are different by the probability that H3 is different from the two different values of Hy and H2.)
(g) What is the probability that at least two of H4, H, and Hz are the same?
(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?

Answer 1

The question is about the birthday problem and its application to hash functions. It asks for the number of different hash values, the number of different values for H^2, and the probability that H^2 is different from H. The remaining parts of the question can be solved using similar reasoning and calculations.

Step-by-step explanation:

The question is asking about the birthday problem and its relation to hash functions.

For part (a), the hash function generates a 4-bit output, so it can generate 2^4 = 16 different hash values.

Part (b) assumes the input M is squared (M^2) and asks how many possible values for H^2 are different from H. Since there are 16 possible hash values and the square function won't change the output value if it is the same as the input, there will be 16 - 1 = 15 possible values of H^2 that are different from H.

Part (c) asks for the probability that H^2 is different from H. Since there are 15 possible values of H^2 that are different from H out of 16 possible values, the probability is 15/16.

The remaining parts of the question can be solved using similar reasoning and calculations.