Dedicated Conventional Cryptographic Primitives - A Classical Introduction to Cryptography: Applications for Communications Security - page 65

In the integrity protection scenario, the goal of the adversary is to replace a given
message x by another message x with the same hashed value. This clearly corresponds
to the second preimage attack.

In the commitment scenario, the participant who commits to x may try to cheat by
replacing x by a different x with the same hashed value before opening the commit-
ment. In this case he has control on x so he can also choose it. Hence this corresponds to
the collision attack scenario. The other participant of the commitment scheme may try
to retrieve information about x from the commitment. This is a kind of first preimage
attack.

So, as we can see, many security properties may be required for hash functions
depending on the threat model.

As usual, it is pretty hard to formally define these security properties. From the
viewpoint of complexity theory, we should consider families of hash functions instead
of a single one engraved in stone. In practice, the hash function is really fixed and we
consider an intuitive notion of security.

3.1.3 From Compression to Hashing

A classical cryptographic hash function design, due independently to Ralph Merkle
and Ivan Damgard, consists of iterating a compression function . As with encryption,
which can be based on a block cipher by using a mode of operation, we can construct a
cryptographic hash function from a compression function. Here, a compression function
is a function which takes fixed length inputs and returns a fixed length output (which
is shorter than the total input length).

For instance, the MD5 cryptographic compression function (see below) has two
inputs, H of length 128 bits and B of length 512 bits, and outputs a 128-bit string. As
depicted in Fig. 3.2, hashing an arbitrary length message M proceeds as follows.

1. We pad M with one bit equal to 1, followed by a variable number of zero bits,
and 64 bits encoding the length of M in bits, so that the total length of the
padded message is the smallest possible multiple of 512 (see Fig. 3.3). Let

M

denote the padded message .
2. We cut

M into a sequence of 512-bit blocks B 1 ,...,

B n .

3. We let H 0 = IV,afixed initial value .

Message

···

Pad

512 512

Initial
value

128 128

C C

···

C

Figure 3.2. The Merkle-Damgard scheme.