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?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ Yes. MD is a domain extender which turns a fixed input size hash into a variable input size hash. $\endgroup$– CodesInChaosApr 22, 2015 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$– kasperdApr 23, 2015 at 7:47
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Apr 22, 2015 at 15:34
-
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, 2016 at 19:18
$\begingroup$
$\endgroup$
1
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$– wladApr 28, 2019 at 14:03