4.2 Cryptographic hash functions

According to [4], a hash function is a function h that has, as a minimum, the following two properties:

h maps an input x of arbitrary finite bit-length, to an output h(x) of fixed bit-length (compression);
Given h and x , h(x) is easy to compute (ease of computation).

In addition, hash functions that are relevant for cryptographic applications (i.e., cryptographic hash functions) may fulfill one or several of the following requirements:

A hash function is preimage resistant (or one-way) if for essentially all prespecified outputs, it is computationally infeasible to find any input that hashes to that output, that is, to find any preimage x such that h(x ) = y when given any y for which a corresponding input is not known.
A hash function is second-preimage resistant (or weak collision resistant ) if it is computationally infeasible to find any second input that has the same output as any specified input, that is, given x , to find a second preimage x ( x such that h(x) = h(x ) .
A hash function is collision resistant (or strong collision resistant ) if it is computationally infeasible to find any distinct inputs x , x that have the same output, that is, such that h(x) = h(x ) .

In the literature, the term one-way hash function (OWHF) or weak one-way hash function is often used to refer to a hash function that is both preimage resistant and second-preimage resistant, whereas the term collision resistant hash function (CRHF) or strong one-way hash function is often used to refer to a hash function that is collision resistant. Furthermore, the term cryptographic hash function is used to refer to either of them (i.e., OWHF or CRHF).

Mainly because of their efficiency, cryptographic hash functions are of central importance for cryptographic algorithms and protocols. For example, cryptographic hash functions can be used to compute and verify digests for arbitrary messages. In this context, these functions may also be called message digest algorithms , and in this book we use both terms synonymously and interchangeably. Also, keyed cryptographic hash functions can be used to compute and verify message authentication codes (MACs). Almost all cryptographic security protocols make use of MACs in one way or another.

All definitions given above are not precise in a mathematically strong sense, because they do not resolve what the terms easy and computationally infeasible actually mean. Nevertheless, we want to use these definitions in this book. It is important to note that the existence of OWHF (or even CRHF) is still an unproven assumption and that, until today, no function has been shown to be preimage resistant (i.e., one-way) in a mathematically pure sense. Obviously, a sufficiently large domain prohibiting an exhaustive search is a necessary but not sufficient condition for a function to be preimage resistant.

Most cryptographic hash functions in use today work on similar principles. They have a basic compression function that is iteratively applied on subsequent blocks of data (until the result of the last compression step is taken as output value). Examples of cryptographic hash functions include MD2 [15], MD4 [16], MD5 [17], and the Secure Hash Algorithm 1 (SHA-1) [18]. MD2, MD4, and MD5 produce 128-bit hash values, whereas SHA-1 produces 160-bit hash values. RIPEMD is another example of an iterative cryptographic hash function. It was developed as part of a European research project and is basically a variation of MD4. RIPEMD-160 is a strengthened version of RIPEMD producing another 160-bit hash value [19]. As of this writing, MD5 and SHA-1 are by far the most widely used and deployed cryptographic hash functions. Due to some recent results in the cryptanalysis of MD5, SHA-1 is the preferred choice.