Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Cryptographic Hash Function
3.
Iterated Cryptographic Hash Functions
4.
Merkle-Damgard Scheme
5.
Security Characteristics of the Merkle-Damgard Scheme
6.
Frequently Asked Questions
6.1.
What is Merkle-Damgard Scheme?
6.2.
What is a Message Digest?
6.3.
Is Merkle-Damgard a one-way function?
6.4.
What are some popular algorithms where the Merkle-Damgard Construction Scheme is used?
6.5.
What is Digital Signature?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

The Merkle-Damgard Construction in Hash functions

Introduction

Cryptographic Hash Functions are a particular class of hash functions with specific properties that make them proper for use in cryptography. Cryptographic Hash Functions are mathematical algorithms that map data of random size to a fixed-size string called a hash.

The Merkle-Damgard Construction in Hash functions

This article will discuss one such cryptographic hash function called the Merkle-Damgard Construction.

Cryptographic Hash Function

Cryptographic Hash Functions are special hash functions. These functions have certain properties that make them suitable for use in cryptography. The hash function is designed to be a one-way function meaning it is difficult to invert. It is an algorithm that maps data of random size to a hash (a bit string) of fixed size.

Collision-resistant hash functions help prevent attacks on the cryptographic hash. If the attacker finds two messages with the same digests(output of the hash function), it becomes easier to break the hash. 

Iterated Cryptographic Hash Functions

In an iterated cryptographic hash function scheme, a function with an input of fixed size is created and is used a required number of times.

This fixed-size input function is known as the compression function. This function compresses an n-bit string to an m-bit string, preferably n>m.

Merkle-Damgard Scheme

The Merkle-Damgard Scheme is an iterated hash function. It is used in the compression of messages to create message digests. It involves the following steps:

Step 1:

The message length and padding are appended to create a larger message. This message should be evenly divisible in blocks of n bits. Here n is the size of the block to be processed by the compression algorithm. 

Message

Step 2:

The message is now divided into ‘t’ blocks. Each block has a size of n bits. The blocks are named M1, M2, M3, M4, … Mt. Since there are t blocks, there will be t iterations, and each iteration would produce a digest. And the digests created at t iterations are called H1, H2, H3, … Ht.

Message Splits

Step 3:

There are t iterations of the compression function. At ith iteration, the compression takes in input the parameters Hi-t and Mi to create the digest Hi. Hi-1 is the digest created by the compression function in the previous iteration. For the first iteration, H0 is provided as the initialization digest value.

f(Hi-1,Mi) = Hi

Thus in the first iteration, the compression function operates on the block of message M1 and the initialized digest (constant value) H0. This gives the digest H1, which along with M2, is then used to compute H2 and so on. 

Merkle-Damgard

Step 4:

The digest Ht that is obtained in the end is treated as the digest for the original message M. 

Security Characteristics of the Merkle-Damgard Scheme

Since Merkle-Damngard uses a one-way compression function, it is also collision resistant. Below are some properties of the Merkle-Damgard Scheme:

  • As compared to brute force, the second preimage attack(finding a message with a specific hash value) works more efficiently on long messages.
     
  • Multiple messages with the same hash (Multicollisions) can be found with just a little work.
     
  • Given a hash of message X, it is easy to find the value of X+Y (padding on X).

Frequently Asked Questions

What is Merkle-Damgard Scheme?

The Merkle-Damgard scheme is an iterated compression scheme used to create cryptographic hashes called message digests.

What is a Message Digest?

A message digest is a cryptographic hash that is obtained as the output of a hash function.

Is Merkle-Damgard a one-way function?

Since Merkle-Damngard is built to resist collisions, it is built as a one-way hash function.

What are some popular algorithms where the Merkle-Damgard Construction Scheme is used?

Merkle-Damgad Construction scheme is used in popular algorithms such as MD5, SHA-1, and SHA-2.

What is Digital Signature?

A Digital Signature is a hash value calculated using the message and a unique key that helps determine the message's originality.

Conclusion

In this article, we discussed what a Cryptographic Hash Function is. We also discussed Iterated Cryptographic Hash Functions and the Merkle-Damgard Scheme.

Recommended Reading:

Also, check out some of the Guided PathsContestsInterview Preparation, and many more things on Coding Ninjas Studio.

Happy Learning!

Live masterclass