O'Reilly logo

Applied Cryptography: Protocols, Algorithms and Source Code in C, 20th Anniversary Edition by Bruce Schneier

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

CHAPTER 18

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

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

Start Free Trial

No credit card required