How does the length of a hash value affect security?

The essential cryptographic properties of a hash function are that it is both one-way and collision-free (see Question 94). The most basic attack we might mount on a hash function is to choose inputs to the hash function at random until either we find some input that will give us the target output value we are looking for (thereby contradicting the one-way property), or we find two inputs that produce the same output (thereby contradicting the collision-free property).

Suppose the hash function produces an n-bit long output. If we are trying to find some input which will produce some target output value y, then since each output is equally likely we expect to have to try 2n possible input values.

If we are trying to find a collision, then by the birthday paradox (see Question 95) we would expect that after trying 2n/2 possible input values we would have some collision. Van Oorschot and Wiener [VW94] showed how such a brute-force attack might be implemented.

With regard to the use of hash functions in the provision of digital signatures, Yuval [Yuv79] proposed the following strategy based on the birthday paradox, where n is the length of the message digest:

  • Adversary selects the target message to be signed and an innocuous message that Alice is likely to want to sign.
  • The adversary generates 2n/2 variations of the innocuous message (by making, for instance, minor editorial changes), all of which convey the same meaning, and their corresponding message digests. He then generates an equal number of variations of the target message to be substituted.
  • The probability that one of the variations of the innocuous message will match one of the variations of the target message is greater than 1/2 according to the birthday paradox.
  • The adversary then obtains Alice's signature on the variation of the innocuous message.
  • The signature from the innocuous message is removed and attached to the variation of the target message that generates the same message digest. The adversary has successfully forged the message without discovering the enciphering keys.

To avoid an attack that depends on brute-force methods, the output from the hash function must be sufficiently long.

| Question 97|