Merkle–Damgård construction


In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building 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, and .

The Merkle–Damgård construction was described in Ralph Merkle’s in 1979. and independently proved that the structure is sound: that is, if an appropriate is used and the compression function is , 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.

  • 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.
  • : Given the hash H(X) of an unknown input X, it is easy to find the value of H(pad(X) || Y), 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 attack was actually used to attack a number of commercial web message authentication schemes such as one used by .

Contents

Wide pipe construction

Due to several structural weaknesses of Merkle–Damgård construction, especially the length extension problem and multicollision attacks, 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

It has been demonstrated by Mridul Nandi and 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. gives sufficient conditions for a padding scheme to possess to ensure that the MD construction is secure: the scheme must be “MD-compliant” (the original length-padding scheme used by Merkle is an example of MD-compliant padding).Conditions:

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

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, let’s say the message to be hashed is “HashInput” and the block size of the compression function is 8 bytes (64 bits). So we get two blocks looking like this:

But this is not enough since it would mean that distinct messages starting by the same data and terminated by zero or more bytes from the padding constant data would get fed into the reduction function using exactly the same blocks, producing the same final hash sum.

In our example, for instance, the modified message “HashInput00” would generate the same blocks as the original message “HashInput”.

To prevent this, the first bit of the padded constant data must be changed. As the constant padding is generally made of zeroes, the first padding bit will be mandatorily changed into “1”.

In our example, we get something like this:

To harden the hash even further also, the length of the message can be added in an extra block.

So in our example, we would get three blocks like this:

To avoid ambiguity, the message length value must be itself resistant to . Most common implementations use a fixed bit-size (generally 64 or 128 bits in modern algorithms) and a fixed position at end of the last block for encoding the message length value.

Now that is a bit wasteful since it means hashing one full extra block for the length value. So there is a slight speed optimisation that most hash algorithms use. If there is space enough among the zeros padded to the last block the length value can instead be padded there.

Let’s say here that, in our example the length value is encoded on 5 bytes (40 bits), thus it gets padded in the final block as “00009”, not just “9” or with too many unnecessary zeroes. Like this:

Source

http://wikipedia.org/

See Also on BitcoinWiki