question archive This is the foundation of the concept of the birthday attack on a hash function
This is the foundation of the concept of the birthday attack on a hash function
Subject:Computer SciencePrice: Bought3
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 211. different values. If n is suitably large, roughly Enfz inputs need to he tried before a collision is likely to he 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 Hashl 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 M1, H1 =Hash2[M1]. Assuming M2 #M1, how many of the possible values for H2 =Hash2[M2] are different than H1? [2 p125] [c] What is the probability that H 2 is different than H1? [3 pts] [d] Assume that H1 and H2 are different values. Assuming M3 JEM1 and M3 #M2, how many ofthe possible values for H3 =Hash2[M3] are different than both H1 and H2? [2 pts] [e] Assuming H1 and H 2 are different, what is the probability that H3 is different from both H1 and H2? [3 pts] [f] In general, what is the probability that H 1, H 2 and H3 are all different? [3 p125] [g] 'What is the probability that at least two of H 1, H 2 and H3 are the same? [3 p125] [[1] Continuing the process outlined in [d] through [g], how many different inputs must be tried before there is at least a (1.5 probability that two or more outputs have the same value? [3 pts]
