Merkle–Damgård construction

Merkle's meta- method (also Merkle - Damgård construction ) is a method for the construction of cryptographic hash functions, which draws on the work of Ralph Merkle and Ivan Damgård.

Where is a compression function that is collision safe, i.e., it is not possible with realistic cost to find two different inputs that are mapped by the same output. Through the use of Merkle's meta- method results in a collision- secure hash function which maps arbitrarily long messages on a hash value of bit length.

Method

The message will first be expanded with a padding process, so that the length of a multiple of being. Then into blocks of length is divided:

The compression function is iteratively applied to the output -bit of the previous iteration and the next bits of the enhanced message until it is completely processed. In the first iteration, the input consists of a long bit initialization vector, often with the value 0, and the first message block.

Either you take then as a hash value, or it is still used a finalize function on it that provides the hash value.

Padding

Thus, the collision safety of the compression function provable carries over to the hash function, the padding process must meet certain conditions. The following conditions are sufficient for it:

• Is an initial segment of, that is, the messages are not changed, expanded only with a tail.
• Two messages of the same length can be extended with equally long tails.
• Two different long messages are different extended so that it is in the last block to be entered into the final stage of compression are different.

Typically when padding a coding of the bit length is appended to the message, and in between bits with the value 0 if necessary, be inserted so that a multiple of is:

Weaken

A weakness is a possible extension attack ( Extension Attack): If one knows the hash value of an unknown message, and lacks the finalize function or one can calculate its inverse, then one can easily determine the hash value of a message from the above gepaddeten message seen by adding an extension. One can thus determine hash values ​​to messages that have as an initial piece, even if you do not know. Since a random oracle does not have this property, these may result in attacks on methods yield that have a proof of security only in the random oracle model. It also follows: once you have found a collision of two messages with the same block length, can be determined by expanding slightly more collisions.

To find multiple collisions, so multiple messages, all of which have the same hash value, requires little more effort than determining a single collision.

A Herding attack, ie at a self-selected hash value z and find a given initial segment of a message a fitting end piece so that the entire message to z hashes, that is to find one with, though requires more effort than finding a collision, but much less than it should be for a random oracle hash function as the case.

An attack to determine a second preimage (second preimage attack), in which a second searches for a given message with the same hash value, is possible with a message, the length of blocks by the time, and thus with long messages much faster than by systematic Try ( brute force ), which is about steps requires.

Improvements

In order to overcome said shortcomings, Stefan Luck has proposed wide -pipe hash construction: In order to calculate a hash value of bits in length, using a compression function, the output of which is longer than, typically twice as long. So compressed bit from the previous iteration and a bit long message block to an output bit. After the last iteration, the output will be reduced by a further compression function on bit, if not simply discards the half output and the other half used as a hash value.

Nandi and Paul have shown that this construction can be made about twice as fast (almost wide pipe hash) by entering only bit from the previous compression to the next compression, along with a bit long message block. The other half of the compression output is XORed with the following command:

In the last stage, the output of the penultimate fully processed, and the message block is only for bits wide (if you do not use here a different compression function with greater input ):

And thereby mean the first or the second half of the bit string.

In addition to the wide -pipe hash construction of the HAIFA construction is regarded as an evolution of the Merkle - Damgård method.