Can someone give me an example of a Merkle–Damgård transformation?

Question

I started reading "Bitcoin and Cryptocurrency Technologies - Princeton University" (coursera) and in the first chapter it talks about Merkle–Damgård transformations for SHA-256. I was trying to understand it by working out an example, but I keep getting problems.

Here is my work:

1. Take a compression function that takes inputs of 4-bits and outputs 2-bits
2. For our hash function we create an arbitrary input of 6-bits
3. Since input-output = # of blocks, the 6-bit input should be divided into two blocks, each with the 3-bits
4. Now from my understanding the initialization vector should be 1-bit because 3-bits+1-bit = 4-bits which is the input the compression function takes
5. Now the output of the first pass is 2-bits, which is a problem because if I add on the other 3-bits, the total is 5 and the compression function only takes in 4-bits. What am I doing wrong?

If someone can help explain where I am messing up or explain the idea in a different way, with an example, I will greatly appreciate it.

Answer 1

You get it wrong when saying

Since input-output = # of blocks, the 6-bit input should be divided into two blocks, each with the 3-bits

because you have a

…compression function that takes inputs of 4-bits and outputs 2-bits

You don't split the message in half and then fiddle with some initialisation factor to make all pieces fit. That's not how it works.

Instead, if the bits you feed to the compression function are too many, you split them up in according pieces; in your example 4 bit inputs. If you end up with the final piece not being 4 bits, you pad it with the number of missing bits so that you can again feed the expected 4-bit length to the compression function.

So, you would feed those 6 bits into your compression function like this:

• You take the first 4 bits of the message, which you feed to the compression function.
• Next, you take the remaining 2 bits of the message, followed by 2 bits of padding to fill it up to 4 bits so that you can again feed 4 bits to the compression function-

Simplified example: Let your message be 6 bits 111111, the padding be 0, and the compression function takes a 4-bit length input. You first feed 1111 to the compression function, finally, you feed 1100 (notice the two padding bits) to the compression function.

Same example using bit positions: Let your message be 6 bits at positions 654321, the padding be 0, and the compression function takes a 4-bit length input. You first feed 6543 to the compression function, finally you feed 2100 to the compression function.

As you can see, the initialization vector is rather irrelevant at this stage where you're feeding the message to the compression function. All that's done is splitting up your message into appropriately sized pieces, and using padding at the end (final block) to fill up what's missing.

---

Nota Bene: You only asked about a specific part of SHA-256, but I nevertheless would like to point out that (when talking about SHA-256 and alike cryptographically secure hashes) the final block doesn't only contain padding but also includes the length of the input message to avoid length extension attacks. In case the message happens to fit the compression function input length and/or doesn't leave enough room to append the input message length, an additional piece (containing nothing but padding | length of the input message) is fed to the compression function.

If this last note confuses you, you might want to check the “Length padding example” at Wikipedia’s article about the “Merkle–Damgård construction”, or maybe even read the complete article offered there as it practically covers all points mentioned here… and more.