RSA Laboratories

2.4.6 What are some techniques against hash functions?

The essential cryptographic properties of a hash function are that it is both one-way and collision-free (see Question 2.1.6). 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 that will produce a given target output value y, then since each output is equally likely we expect to have to try on the order of 2n possible input values.

A birthday attack is a name used to refer to a class of brute-force attacks. If some function, when supplied with a random input, returns one of k equally-likely values, then by repeatedly evaluating the function for different inputs, we expect to obtain the same output after about 1.2k1/2 trials.

If we are trying to find a collision, then by the birthday paradox we would expect that after trying 1.2(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:

  • The adversary selects two messages: 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 key.

Pseudo-collisions are collisions for the compression function (see Question 2.1.6) that lies at the heart of an iterative hash function. While collisions for the compression function of a hash function might be useful in constructing collisions for the hash function itself, this is not normally the case. While pseudo-collisions might be viewed as an unfortunate property of a hash function, a pseudo-collision is not equivalent to a collision - the hash function may still be considered as reasonably secure, though its use for new applications tends to be discouraged in favor of pseudo-collision-free hash functions. MD5 (see Question 3.6.6) is one such example.

Top of the page