Is the "compression function" in Merkle-Damgård just a collision-resistant, one-way hash function but one that operates only on fixed size inputs?

If so, is MD just a way to extend it to work on arbitrary length strings?

  • 3
    $\begingroup$ Yes. MD is a domain extender which turns a fixed input size hash into a variable input size hash. $\endgroup$ Apr 22 '15 at 15:24
  • 2
    $\begingroup$ What I read in this question is that you already understand the idea, and that you just need to get confirmed that your understanding is correct. The answer to each of your two questions is yes. Your wording is an accurate description of what happens. $\endgroup$
    – kasperd
    Apr 23 '15 at 7:47

A compression function takes two fixed size inputs: a chaining value and a message and returns a fixed size value. So it's essentially a hash function with fixed input size.

Merkle-Damgård is a domain extender, which turns that compression function into a hash which supports arbitrarily long messages.

MD uses the output of the compression of one block as the chaining value when hashing the next block. It also describes how to pad the message so it consists of complete blocks.

  • 3
    $\begingroup$ Note that for Merkle-Damgård to work, you need the compression function to be collision resistant. This then guarantees that the overall hash function is collision resistant. $\endgroup$ Jan 28 '16 at 19:18

The merkel-damgard scheme highlights the point that for a hash function to be collision resistant, the compression function needs to be collision resistant. This guarantee helped in creation of hash functions like SHA, WHIRLPOOL, MD etc. According to this scheme, the input message can be of variable length, but the its length should be a multiple of a given number (say n), for ensuring this padding is used, then message is broken into m parts each of length n. The number of times the iteration runs depend on this number m. At first step an arbitary digest of fixed length (say p) is used, and after first iteration, compression function uses the first of m parts of input message M and this arbitary digest to create a new digest of the fixed length p, which is used by next iteration as input with 2nd of m parts of input message M, till m iterations. After m iterations, the final digest is of fixed length p. Hence input can be of arbitary size, but the digest is always of a fixed size.

In short, Yes, MD is a way to work on arbitary length input, while ensuring collision resistance.

  • 1
    $\begingroup$ I think you got downvoted because it's not clear how your answer is different from the accepted answer $\endgroup$
    – ogogmad
    Apr 28 '19 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.