Davies-Meyer Construction and Merkle-Damgård Paradigm

Definition

Davies-Meyer construction is a method of building a compression function from a block cipher by encrypting the message block with the previous hash value as the key and then combining the result with the previous hash value using a bitwise XOR or addition-like feed-forward step.

Merkle-Damgård paradigm is a general framework for building a variable-length hash function from a fixed-size compression function by processing the message in blocks, chaining the output of one block into the next, and using a carefully designed padding rule.

In simple terms:

Davies-Meyer

• tells us how to make one compression step.

Merkle-Damgård

• tells us how to repeat that step over many message blocks to hash an entire message.

Main Content

1. Davies-Meyer Construction

Core idea of compression

• The Davies-Meyer construction converts a block cipher into a compression function.

• If a block cipher encryption is written as E_k(m) where k is the key and m is the block, then the compression function typically uses: h_i = E_{m_i}(h_{i-1}) XOR h_{i-1}

• Here, the message block acts as the key, and the previous chaining value acts as the plaintext.

• The output becomes the next chaining value, which is usually the same size as the block cipher block size.

Feed-forward mechanism

• The XOR with the previous hash value is called feed-forward.
• Without this step, the output would just be the block cipher ciphertext, which may not behave as a robust hash compression function.
• Feed-forward improves diffusion and helps ensure that every round depends on both the input block and the previous state.
• This makes it harder to reverse the compression function directly, even if the underlying block cipher is well understood.

Example:

Suppose the chaining value is H_{i-1} and the message block is M_i.

H_i = E(M_i, H_{i-1}) XOR H_{i-1}

ASCII flow for the idea:

H_{i-1} -----> [ Block Cipher E with key M_i ] -----> Ciphertext
    |                                                   |
    +-------------------- XOR --------------------------+
                            |
                            v
                           H_i

2. Merkle-Damgård Paradigm

Iterative hashing structure

• The Merkle-Damgård paradigm hashes a long message by splitting it into fixed-size blocks.
• Each block is processed one at a time using a compression function.
• The output of the previous block becomes the input chaining value for the next block.
• This chained sequence continues until all blocks are processed.

Padding and initialization

• Since messages may not be a multiple of the block size, a padding rule is required.
• The padding usually appends a 1 bit, followed by enough 0 bits, and finally the length of the original message.
• This prevents ambiguity between different messages that could otherwise produce the same block arrangement.
• An initial value, called the IV (Initialization Vector), is used as the starting chaining value.

Example structure:

IV -> f(M1, IV) -> f(M2, H1) -> f(M3, H2) -> ... -> final hash

Where:

• M1, M2, M3 are message blocks
• f is the compression function
• the last output is the message digest

3. Relationship Between Davies-Meyer and Merkle-Damgård

Davies-Meyer as a building block

• Davies-Meyer provides one secure way to create the compression function f needed by Merkle-Damgård.
• Merkle-Damgård itself does not require Davies-Meyer specifically; it only requires a suitable compression function.
• However, Davies-Meyer is one of the most famous and practical constructions used for this purpose.

Why the combination is important

• A block cipher alone encrypts fixed-size data, but hashing must support messages of arbitrary length.
• Davies-Meyer turns a block cipher into a compression function.
• Merkle-Damgård repeats the compression function across the full message.
• Together, they give a complete framework for designing hash functions.

Security intuition

• The compression function should be hard to invert or collide.
• The chaining process ensures that any small change in the message affects all later states.
• Proper padding and length encoding help preserve uniqueness of message parsing.

ASCII representation of the full pipeline:

Message
  |
  v
Padding + Split into blocks
  |
  v
M1, M2, M3, ... , Mn
  |
  v
IV -> DM(M1, IV) -> DM(M2, H1) -> DM(M3, H2) -> ... -> Hn
  |
  v
Final Hash

Working / Process

1. Initialize the hash

• Start with a fixed initial value (IV).
• The IV is predefined by the hash algorithm and acts as the first chaining value.
• This ensures all users of the hash function begin from the same known state.

2. Pad and divide the message

• The message is padded so that its length becomes compatible with the block size.
• A common padding method includes:
  • a single 1 bit,
  • followed by 0 bits,
  • followed by the message length.
• After padding, the message is divided into fixed-size blocks M1, M2, ..., Mn.

3. Apply the compression function repeatedly

• For each message block:
  • Use the current chaining value as input.
  • Use the message block as the key or control input in the compression step.
  • Produce a new chaining value.

• In Davies-Meyer form: H_i = E(M_i, H_{i-1}) XOR H_{i-1}

• After the last block, the final chaining value is the hash digest.

Advantages / Applications

Efficient design from existing primitives

• Converts a block cipher into a hash compression function without needing a completely separate cryptographic primitive.
• This is useful because block ciphers are often well-studied and optimized in hardware and software.

Supports arbitrary-length messages

• The Merkle-Damgård paradigm allows hashing of messages of any length by processing them block by block.
• This is one of the main reasons hash functions became practical for real-world use.

Widely used in classical hash algorithms

• Many older and historically important hash functions follow the Merkle-Damgård style.
• The paradigm has been used in the design of hashes for:
  • integrity verification
  • digital signatures
  • password hashing frameworks
  • file fingerprinting
  • message authentication constructions

Summary

• Davies-Meyer is a way to build a compression function from a block cipher.
• Merkle-Damgård is a method for turning a compression function into a hash function for long messages.
• Together, they form an iterative hashing approach based on chaining and padding.
• Important terms to remember: block cipher, compression function, chaining value, IV, padding, feed-forward, Merkle-Damgård, Davies-Meyer