With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

One-Way Hash Functions

18.1 BACKGROUND

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required