Question

For an m bit hash value, if we pick data blocks at random we can expect to find two data blocks with the same hash value within ____ attempts.

(a) 2^m

(b) 2^(m-1)

(c) 2^(m/2)

(d) (2^m) – 1

I had been asked this question in exam.

My query is from Hash Functions Based on Cipher Block Chaining in portion Other Public Key Cryptosystems and Cryptographic Hash Functions of Cryptograph & Network Security

Answer 1

Right option is (c) 2^(m/2)

Easy explanation: This is known as the birthday paradox. If we choose random variables from a uniform distribution in the range 0 through N-1, then the probability that a repeated element is encountered exceeds 0.5 after root (N) choices have been made.