A one-way hash function, H(M), operates on an arbitrary-length pre-image message, M. It returns a fixed-length hash value, h.
h = H(M), where h is of length m
Many functions can take an arbitrary-length input and return an output of fixed length, but one-way hash functions have additional characteristics that make them one-way :
Given M, it is easy to compute h.
Given h, it is hard to compute M such that H(M) = h.
Given M, it is hard to find another message, M′, such that H(M) = H(M′).
If Mallory could do the hard things, he would undermine the security of every protocol that uses the one-way hash function. The whole point of the one-way hash function is to provide a “fingerprint” of M that is unique. If Alice signed M by using a digital signature algorithm on H(M), and Bob could produce M', another message different from M where H(M) = H(M′), then Bob could claim that Alice signed M′.
In some applications, one-wayness is insufficient; we need an additional requirement called collision-resistance.
It is hard to find two random messages, M and M′, such that H(M) = H(M′).
Remember the birthday attack from Section 7.4? It is not based on finding another message M', such that H(M) = H(M′), but based on finding two random messages, M and M′, such that H(M) = H(M′).
The following protocol, first described by Gideon Yuval , shows how—if the previous requirement were not true—Alice could use the birthday attack to swindle ...