Question

For an m-bit value, the adversary would have to try ____________ values to generates a given hash value h.

(a) 2^m

(b) 2^(m-1)

(c) 2^(m/2)

(d) (2^m) – 1

This question was posed to me during an interview for a job.

Origin of the question is Hash Functions Based on Cipher Block Chaining in chapter Other Public Key Cryptosystems and Cryptographic Hash Functions of Cryptograph & Network Security

Answer 1

Right choice is (b) 2^(m-1)

To explain I would say: The adversary would have to try 2^(m-1) values to generates a given hash value h.