Merkle–Damgård construction

Short description: Method of building collision-resistant cryptographic hash functions

In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. This construction was used in the design of many popular hash algorithms such as MD5, SHA-1 and SHA-2.

The Merkle–Damgård construction was described in Ralph Merkle's Ph.D. thesis in 1979. Ralph Merkle and Ivan Damgård independently proved that the structure is sound: that is, if an appropriate padding scheme is used and the compression function is collision-resistant, then the hash function will also be collision-resistant.

The Merkle–Damgård hash function first applies an MD-compliant padding function to create an input whose size is a multiple of a fixed number (e.g. 512 or 1024) — this is because compression functions cannot handle inputs of arbitrary size. 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. In order to make the construction secure, Merkle and Damgård proposed that messages be padded with a padding that encodes the length of the original message. This is called length padding or Merkle–Damgård strengthening.

Merkle–Damgård hash construction

In the diagram, the one-way compression function is denoted by f, and transforms two fixed length inputs to an output of the same size as one of the inputs. The algorithm starts with an initial value, the initialization vector (IV). The IV is a fixed value (algorithm or implementation specific). For each message block, the compression (or compacting) function f takes the result so far, combines it with the message block, and produces an intermediate result. The last block is padded with zeros as needed and bits representing the length of the entire message are appended. (See below for a detailed length padding example.)

To harden the hash further, the last result is then sometimes fed through a finalisation function. 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. The finalisation function is often built by using the compression function. (Note that in some documents a different terminology is used: the act of length padding is called "finalisation".)

Security characteristics

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. Unfortunately, this construction also has several undesirable properties:

• Second preimage attacks against long messages are always much more efficient than brute force.
• Multicollisions (many messages with the same hash) can be found with only a little more work than collisions.
• "Herding attacks", which combines the cascaded construction for multicollision finding (similar to the above) with collisions found for a given prefix (chosen-prefix collisions). This allows for constructing highly specific colliding documents, and it can be done for more work than finding a collision, but much less than would be expected to do this for a random oracle.
• Length extension: Given the hash [math]\displaystyle{ H(X) }[/math] of an unknown input X, it is easy to find the value of [math]\displaystyle{ H(\mathsf{Pad}(X) \| Y) }[/math], where pad is the padding function of the hash. That is, it is possible to find hashes of inputs related to X even though X remains unknown. Length extension attacks were actually used to attack a number of commercial web message authentication schemes such as one used by Flickr.

Wide pipe construction

The Wide pipe hash construction. The intermediate chaining values have been doubled.

Due to several structural weaknesses of Merkle–Damgård construction, especially the length extension problem and multicollision attacks, Stefan Lucks proposed the use of the wide-pipe hash instead of Merkle–Damgård construction. The wide-pipe hash is very similar to the Merkle–Damgård construction but has a larger internal state size, meaning that the bit-length that is internally used is larger than the output bit-length. If a hash of n bits is desired, the compression function f takes 2n bits of chaining value and m bits of the message and compresses this to an output of 2n bits.

Therefore, in a final step a second compression function compresses the last internal hash value (2n bit) to the final hash value (n bit). This can be done as simply as discarding half of the last 2n-bit-output. SHA-512/224 and SHA-512/256 take this form since they are derived from a variant of SHA-512. SHA-384 and SHA-224 are similarly derived from SHA-512 and SHA-256, respectively, but the width of their pipe is much less than 2n.

Fast wide pipe construction

The Fast wide pipe hash construction. Half of the chaining value is used in the compression function.

It has been demonstrated by Mridul Nandi and Souradyuti Paul that the Widepipe hash function can be made approximately twice as fast if the widepipe state can be divided in half in the following manner: one half is input to the succeeding compression function while the other half is combined with the output of that compression function.

The main idea of the hash construction is to forward half of the previous chaining value forward to XOR it to the output of the compression function. In so doing the construction takes in longer message blocks every iteration than the original widepipe. Using the same function f as before, it takes n bit chaining values and n+m bits of the message. However, the price to pay is the extra memory used in the construction for feed-forward.

MD-compliant padding

As mentioned in the introduction, the padding scheme used in the Merkle–Damgård construction must be chosen carefully to ensure the security of the scheme. Mihir Bellare gives sufficient conditions for a padding scheme to possess to ensure that the MD construction is secure: it suffices that the scheme be "MD-compliant" (the original length-padding scheme used by Merkle is an example of MD-compliant padding). Conditions:

• [math]\displaystyle{ M }[/math] is a prefix of [math]\displaystyle{ \mathsf{Pad}(M). }[/math]
• If [math]\displaystyle{ |M_{1}| = |M_{2}| }[/math] then [math]\displaystyle{ |\mathsf{Pad}(M_{1})| = |\mathsf{Pad}(M_{2})|. }[/math]
• If [math]\displaystyle{ |M_{1}| \neq |M_{2}| }[/math] then the last block of [math]\displaystyle{ \mathsf{Pad}(M_{1}) }[/math] is different from the last block of [math]\displaystyle{ \mathsf{Pad}(M_{2}). }[/math]

Where [math]\displaystyle{ |X| }[/math] denotes the length of [math]\displaystyle{ X }[/math]. With these conditions in place, we find a collision in the MD hash function exactly when we find a collision in the underlying compression function. Therefore, the Merkle–Damgård construction is provably secure when the underlying compression function is secure.

Length padding example

To be able to feed the message to the compression function, the last block needs to be padded with constant data (generally with zeroes) to a full block. 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). We get two blocks (the padding octets shown with lightblue background color):

48 61 73 68 49 6e 70 75, 74 00 00 00 00 00 00 00

This implies that other messages having the same content but ending with additional zeros at the end will result in the same hash value. In the above example, another almost identical message (0x48617368496e7075 7400) will generate the same hash value as the original message "HashInput" above. In other words, any message having extra zeros at the end makes it indistinguishable from the one without them. To prevent this situation, the first bit of the first padding octet is changed to "1" (0x80), yielding:

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 00

To make it resistant against the length extension attack, the message length is added in an extra block at the end (shown with yellow background color):

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 00, 00 00 00 00 00 00 00 09

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). Further improvement can be made by inserting the length value in the last block if there is enough space. Doing so avoids having an extra block for the message length. If we assume the length value is encoded on 5 bytes (40 bits), the message becomes:

48 61 73 68 49 6e 70 75, 74 80 00 00 00 00 00 09

Note that storing the message length out-of-band in metadata, or otherwise embedded at the start of the message is an effective mitigation of the length extension attack, as long as invalidation of either the message length and checksum are both considered failure of integrity checking.

References

• Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone (2001), chapter 9.
• Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell. Chapman and Hall/CRC Press, August 2007, page 134 (construction 4.13).
• Cryptography Made Simple by Nigel Smart (2015), chapter 14.