Merkle-Damgård construction

Merkle-Damgård construction

In cryptography, the Merkle-Damgård construction or Merkle-Damgård hash function is a method to build cryptographic hash functions. All popular hash functions follow this generic construction.

A cryptographic hash function must be able to process an arbitrary-length message into a fixed-length output. This can be achieved by breaking the input up into a series of equal-sized blocks, and operating on them in sequence using a one-way compression function that processes a fixed-length input into a shorter, fixed-length output. The compression function can either be specially designed for hashing or be built from a block cipher. In many cases, including the SHA-1 and SHA-0 ciphers, the compression function is based on a block cipher that is specially designed for use in a hash function. The Merkle-Damgård hash function breaks the input into blocks, 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 Merkle-Damgård construction was described in Ralph Merkle's Ph.D. thesis. [R.C. Merkle. [http://www.merkle.com/papers/Thesis1979.pdf "Secrecy, authentication, and public key systems."] Stanford Ph.D. thesis 1979, pages 13-15. ] Ralph Merkle and Ivan Damgård independently proved that the structure is sound: if the compression function is collision-resistant, then the hash function will be also. [R.C. Merkle. "A Certified Digital Signature". In Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 218-238. ] [I. Damgård. "A Design Principle for Hash Functions". In Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 416-427.] In order to prove that the construction issecure, 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.

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 instead 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:

* Length extension — once an attacker has one collision, he can find more very cheaply.
* 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" (first committing to an output h, then mapping messages with arbitrary starting values to h) are possible for more work than finding a collision, but much less than would be expected to do this for a random oracle.

Length padding example

Let's say the message to be hashed is "Wikipedia" and the block size of the compression function is 8 bytes (64 bits). (Note that a hash function needs to have at least 160 bits block size to be secure, but we use 64 bits in this example for simplicity.)

To be able to feed the message to the compression function the last block needs to be zero padded to a full block. So we get two blocks looking like this:

Wikipedi a0000000

But this is not enough since it would mean that for instance the message "Wikipedia00" would get the same hash sum. To prevent this a single "1" can be padded before the zeros. Like this:

Wikipedi a1000000

To harden the hash even further also the length of the message is added in an extra block. So we get three blocks like this:

Wikipedi a1000000 00000009

Now that is a bit wasteful since it means hashing one extra block. 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. Like this:

Wikipedi a1000009

To avoid ambiguity the length value must be of a fixed bit-size, say 40 bits. Thus the length value padded in the end is "00009", not just "9".

See also

* Cryptographic hash function
* One-way compression function
* Ralph Merkle - One of the two inventors of the Merkle-Damgård structure.
* Ivan Damgård - The other inventor of the Merkle-Damgård structure.

References

* " [http://www.cacr.math.uwaterloo.ca/hac/ Handbook of Applied Cryptography] " by Menezes, van Oorschot and Vanstone (2001), chapter 9.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Merkle–Damgård construction — In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method to build collision resistant cryptographic hash functions from collision resistant one way compression functions.[1]:145 This construction was used in… …   Wikipedia

  • Construction De Merkle-Damgård — Dans le cadre des fonctions de hachage cryptographiques, la construction de Merkle Damgård est une construction algorithmique qui permet de résoudre le problème du hachage cryptographique en acceptant un message de taille quelconque tout en… …   Wikipédia en Français

  • Construction de Merkle-Damgard — Construction de Merkle Damgård Dans le cadre des fonctions de hachage cryptographiques, la construction de Merkle Damgård est une construction algorithmique qui permet de résoudre le problème du hachage cryptographique en acceptant un message de… …   Wikipédia en Français

  • Construction de merkle-damgård — Dans le cadre des fonctions de hachage cryptographiques, la construction de Merkle Damgård est une construction algorithmique qui permet de résoudre le problème du hachage cryptographique en acceptant un message de taille quelconque tout en… …   Wikipédia en Français

  • Merkle-Damgard — Construction de Merkle Damgård Dans le cadre des fonctions de hachage cryptographiques, la construction de Merkle Damgård est une construction algorithmique qui permet de résoudre le problème du hachage cryptographique en acceptant un message de… …   Wikipédia en Français

  • Merkle-Damgård — Construction de Merkle Damgård Dans le cadre des fonctions de hachage cryptographiques, la construction de Merkle Damgård est une construction algorithmique qui permet de résoudre le problème du hachage cryptographique en acceptant un message de… …   Wikipédia en Français

  • Construction de Merkle-Damgård — Dans le cadre des fonctions de hachage cryptographiques, la construction de Merkle Damgård est une construction algorithmique qui permet de résoudre le problème du hachage cryptographique en acceptant un message de taille quelconque tout en… …   Wikipédia en Français

  • Construction De Davies-Meyer — Une construction de Davies Meyer (ou fonction de Davies Meyer) est une technique utilisée dans les fonctions de hachage cryptographiques. Elle consiste à effectuer un XOR entre la sortie de la fonction de compression et la sortie de la… …   Wikipédia en Français

  • Construction De Miyaguchi-Preneel — Une construction de Miyaguchi Preneel (ou fonction de Miyaguchi Preneel) est une technique utilisée dans les fonctions de hachage cryptographiques. Elle a été inventée par Bart Preneel et Shoji Mayaguchi. Cette structure utilise un algorithme de… …   Wikipédia en Français

  • Construction de davies-meyer — Une construction de Davies Meyer (ou fonction de Davies Meyer) est une technique utilisée dans les fonctions de hachage cryptographiques. Elle consiste à effectuer un XOR entre la sortie de la fonction de compression et la sortie de la… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”