Merkle Tree

From CRYPTUTOR

Jump to: navigation, search

This page is under construction. Do not rely on its accuracy until it is finished. Please edit this page or use the talk page to leave comments.

A Merkle-Damgard iteration is an NMAC signing algorithm constructed as follows:


Image:Mdl.jpg


k\, is the key for each iteration.
x_i\, is a subset of a message x\,
H_k(m)\, is the final hash output.


H_k(m)\, can be utilized for any length n\,, but without recording the length, H_k(m)\, is not a CRHF. Consider the following situation:


Image:Mdc.jpg


Because the final output of H_k(m)\, is dependent only upon the inputs x_0\, ... x_n\,, if x_0\, was actually constructed from a prior iteration y_0\, ... y_n\,, there is no way to distinguish between the two hashes and a collision is created.

To alleviate this problem, the number of iterations is saved:


H'_k(m) = H_k(m) || length(m)\,


A Merkle-Damgard iteration can be made more effective by creating a tree structure rather than chaining H_k(m)\, blocks.


Image:Mdt.jpg


So long as H_k(m)\, is a CRHF, the final tree or chained construction will be a CRHF. The same is true if H_k(m)\, is a UOWHF. By using a OWF, it is possible to construct these hashing trees without needing to store every node (see OWF and seeding for more information).

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Merkle_Tree"