Anatomy of a hash function

The Merkle-Damgård construction

How do we concretely build a function that swallows a message of arbitrary size and returns a fixed digest? The dominant historical answer is called the Merkle-Damgård construction, named after its two inventors in 1979.

The principle: compress in small chunks

The idea is not to process the whole message at once, but to split it into fixed-size blocks and "digest" them one by one, keeping at each step an internal state that summarizes everything seen so far.

The heart of the mechanism is a compression function denoted f. It takes two fixed-size inputs — the current state and a message block — and returns a new state of the same size:

f(état, bloc) -> nouvel état

Padding

The message rarely has a size that is an exact multiple of the block size. So we pad it: we add bits to complete the last block. The classic Merkle-Damgård padding adds a 1 bit, then 0 bits, then encodes the length of the original message in the last bits.

message :  [ ..... utile ..... ]
rembourré: [ ..... utile ..... 1 0 0 ... 0 | longueur ]
                                            \-- bloc complété --/

Encoding the length at the end (Merkle-Damgård strengthening) is essential: it binds the digest to the size of the message and blocks certain attacks.

Chaining

Once padded, the message is split into blocks M1, M2, ..., Mk. We start from a constant fixed by the standard, the initial value or IV. Then we apply f in a chain:

 IV ---> f ---> f ---> f ---> ... ---> f ---> empreinte
          ^      ^      ^               ^
          |      |      |               |
         M1     M2     M3     ...       Mk

état0 = IV
état1 = f(état0, M1)
état2 = f(état1, M2)
...
étatk = f(état(k-1), Mk)   -> empreinte finale

Each step mixes the current block with the entire past. Since the compression function has the proper avalanche effect, the slightest modification of a block propagates to the whole state and therefore to the final digest.

An entire family relies on it

This construction is that of MD5, SHA-1 and the whole SHA-2 family (including SHA-256). It has an immense advantage: if the compression function f resists collisions, then the complete hash function resists them too — this is a theorem proved by Merkle and Damgård.

But it also has structural weaknesses inherited from this chaining, notably the length extension attack, which we will see in chapter 2.

In summary