Merkle–Damgård construction

The hash function then breaks the result into blocks of fixed size, and processes them one at a time with the compression function, each time combining a block of the input with the output of the previous round.

The last block is padded with zeros as needed and bits representing the length of the entire message are appended.

The finalisation function can have several purposes such as compressing a bigger internal state (the last result) into a smaller output hash size or to guarantee a better mixing and avalanche effect on the bits in the hash sum.

[citation needed] (Note that in some documents a different terminology is used: the act of length padding is called "finalisation".

[citation needed]) The popularity of this construction is due to the fact, proven by Merkle and Damgård, that if the one-way compression function f is collision resistant, then so is the hash function constructed using it.

In so doing the construction takes in longer message blocks every iteration than the original wide pipe.

Using the same function f as before, it takes n-bit chaining values and n + m bits of the message.

For example, suppose the message to be hashed is "HashInput" (9 octet string, 0x48617368496e707574 in ASCII) and the block size of the compression function is 8 bytes (64 bits).

To prevent this situation, the first bit of the first padding octet is changed to "1" (0x80), yielding: However, most common implementations use a fixed bit-size (generally 64 or 128 bits in modern algorithms) at a fixed position at the end of the last block for inserting the message length value (see SHA-1 pseudocode).