enciphering keys;brute-force attack; Yuval; Van Oorschot;collision;security">


Question 96. 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:

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