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 [1065]:

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 [1635], shows how—if the previous requirement were not true—Alice could use the birthday attack to swindle ...

Start Free Trial

No credit card required