MerkleDamgård

The Merkle–Damgård construction is a method for constructing a wide range of cryptographic hash functions from a fixed-input-length compression function. It is named after its inventors, Ralph Merkle and Ivan Damgård, who described it in 1989. The construction is widely used in practice, most notably in the design of the MD5, SHA-1, SHA-2, and SHA-3 hash functions.

The core idea of the Merkle–Damgård construction is to repeatedly apply a compression function to successive blocks of the input message, chaining the output of each application to the input of the next. The process begins with an initial fixed value, often called the initialization vector or chaining value. The message is first padded to ensure its length is a multiple of the block size. Then, the padded message is divided into blocks. The first block is combined with the initialization vector using the compression function. The output of this compression function becomes the chaining value for the next block. This process continues until all blocks of the message have been processed. The final output of the compression function is the hash of the entire message.

The security of hash functions built using the Merkle–Damgård construction relies on the security of the underlying compression function. If the compression function is collision-resistant, then the Merkle–Damgård construction generally preserves this property for the resulting hash function. However, the construction has been shown to be vulnerable to certain types of attacks, such as length extension attacks, if not implemented carefully. Modern hash function designs often address these vulnerabilities or use alternative constructions.