A Python implementation for a Merkle-Damgård construction is available in my GitHub repository.


1978. Michael O. Rabin proposes his idea of a hash function. But what is so interesting about it? Hash functions were not something new for that time. Already a few years before Diffie-Hellman suggested their version of a one-way function for digital signatures. Well, Rabin’s function had a very useful property that Diffie-Hellman lacked. The input didn’t have to be a short message anymore. Thanks to a chaining mechanism, one function could produce a fingerprint of the whole book!

Unfortunately, this hash function was not secure. Already a year later in 1979, Gideon Yuval publishes an article, “How to swindle Rabin”, that makes it obvious: Rabin forgot to check one of the most important properties of a good hash function - collision resistance. In that time a construction was considered unbreakable if the attacker needed to brute force through more than $2^{56}$ operations to break it. This number comes from a collision formula $2^{n/2}$, where $n$ is the output length, which was created thanks to the Birthday Problem. For Rabin’s function, it was possible to find two different inputs that produced the same output already after only $2^{32}$ operations.


So how do we build a collision-resistant hash function?

Let’s not start from zero, but try to upgrade Rabin’s idea. He split the message into chunks, then built sort of a conveyer chain out of DES applications and used each chunk as a key for DES. The first plaintext that the conveyer took in was a predefined initial state (IV). Further, the plaintext input was used for the carry-on output of the previous round.

      M1     M2            M3
       |      |            |
IV -> DES -> DES -> ... -> DES -> h(M)

And everything seems to work well, but… DES is a block cipher. So yes, it compresses the input, but it still can be reversed by decryption. And if the foundation of the chain is so vulnerable, how can the chain itself be secure?

There’s a quick fix for this problem, though. All we have to do is XOR the DES’ output with the original plaintext:

$$f(\text{key}, \text{plaintext}) = \text{ENCRYPT}(\text{key}, \text{plaintext}) \oplus \text{plaintext}$$

This is called a Davies-Meyer compression function. It breaks the block cipher’s reversibility. Now even if you try to treat the output of $f$ as DES output, decrypt it, and get two valid inputs, to create a collision you would have to run these through $f$ again, and XOR will destroy the found “collision”. So the only way to find the input is to brute force.

Another minor change: instead of using message chunks as keys, we will treat complete DES input as a field for our message chunk. This will allow us to take in more bits per cycle.

What we have built is called a compression function. And we could have stopped here, but is $f$ really collision resistant?


How to make a compression function collision-resistant?

Right now the output of $f$ is only 64 bits long, the input is 120 bits. By the collision formula we mentioned earlier, for the security level of $2^{56}$ bits we would need an output of at least 112 bits. So what can we do to get 112 bits in the end? Nothing complicated. Let’s concatenate two outputs of our $f$ function and call it $F_1$:

$$F_1 = \text{First112bitsOf}\left( f(\text{"0"}, x) \,\|\, f(\text{"1"}, x) \right)$$

Outputs had to be different, otherwise such concatenation wouldn’t have made a lot of sense. That’s why we used two predefined bits: “0” for the first input and “1” for the second one. Of course, we had to shorten the input of $F_1$ by one bit, but that’s not such a big price to pay for security.


Why couldn't we just take the first and last 119 bits of the input?

While this idea saves us that one extra bit, it doesn't always guarantee different inputs. Imagine the input of $F_1$ was 1111...11111. Then both the first and the last 119 bits would be just 1s. But if we force the first bit of each input to be different, we will definitely get different inputs. Even if the difference is only by that one bit.

Why do we take only 112 bits of the output instead of leaving 128 bits for additional security?

As we already know, the compression function will be applied multiple times for longer texts in a chain, so we would wish for the carry-on output to be as much smaller than the input as it's possible without affecting security. And since in this case cutting the output of $F_1$ doesn't affect security in any way, we can just throw those bits away and free up some space.


We took care of security, but what about efficiency?

Our hash function needs to be secure but also efficient. No one would want to wait hours for a fingerprint to be computed. So let’s calculate the efficiency of $F_1$:

$$\begin{aligned} \text{input}_1 &: 119 \text{ bits} \\ \text{output}_1 &: 112 \text{ bits} \\ \text{input}_2 &: \text{output}_1 + \text{new bits} = 112 + \mathbf{7} = 119 \end{aligned}$$

Right now our compression function $F_1$ takes in only 7 new bits per iteration. And since each iteration has two DES applications, we’re using DES (the longest and the most computationally expensive part of our construction) every 3.5 bits. I bet we could do better.


How to make the compression function more efficient?

We could increase the difference between the input and the output. For that, let’s try and use more DES per cycle. Sounds inefficient at first, but let’s not go ahead of ourselves.

As we remember, each DES application had its own predefined bits to ensure the difference of the inputs. For four DES we will have to use bits 00, 01, 11, and 10, so each input of $f$ is now only 118 bits long.

$$F_2 = f\big(\text{"00"},\, f(\text{"01"}, x_1) \,\|\, x_2\big),\; f\big(\text{"10"},\, f(\text{"11"}, x_1) \,\|\, x_2\big)$$


The bit math for $F_2$ looks like this:

$$\begin{array}{lcl} & \text{"01"} + 118 \xrightarrow{\text{DES, XOR}} 64 \;\;+\;\; \text{"00"} + 54 \xrightarrow{\text{DES, XOR}} 64 & \\ 172 \text{ bits} \rightarrow & & += 128 \text{ bits} \\ & \text{"11"} + 118 \xrightarrow{\text{DES, XOR}} 64 \;\;+\;\; \text{"10"} + 54 \xrightarrow{\text{DES, XOR}} 64 & \end{array}$$


We left the output 128 bits long. Why not cut it down to 112 bits again?

To be honest, I had the same question. I tried to untangle it, but I'm still not 100% sure that I got it right, so read it with some criticism.

Look at our bit math. We are squeezing 118 bits into 64 bits twice. This creates sort of a bottleneck, which compromises the randomness of the function and the security of the proof. It can happen that the middle values collide, which will lower the security level from the desired $2^{56}$ operations.


Time to evaluate the efficiency of $F_2$:

$$\begin{aligned} 172 - 128 &= 44 \\ 44 : 4 &= 11 \end{aligned}$$

So our upgraded compression function takes 44 new bits per iteration and applies DES only every 11 bits. This is already much better than what we had after our first try.


But can it be even better?

Adding more DES worked, so let’s stick to it:

$$F_3 = f\big(\text{"00"},\, \text{First59bitsOf}(f(\text{"100"}, x_1)) \,\|\, \text{First59bitsOf}(f(\text{"101"}, x_2))\big) \,\|\, f\big(\text{"01"},\, \text{First59bitsOf}(f(\text{"110"}, x_1)) \,\|\, \text{First59bitsOf}(f(\text{"111"}, x_2))\big)$$


Now here’s the bit math:

$$234 \text{ bits} = 117\text{(F - first)} + 117\text{(L - last)}$$
$$\begin{array}{lll} & \text{"100"} + 117\text{(F)} \xrightarrow{\text{DES, XOR}} 64 \rightarrow 59 & \\ & & + \text{"00"} \xrightarrow{\text{DES, XOR}} 64 \\ & \text{"101"} + 117\text{(L)} \xrightarrow{\text{DES, XOR}} 64 \rightarrow 59 & \\ 234 \text{ bits} \rightarrow & & += 128 \text{ bits} \\ & \text{"110"} + 117\text{(F)} \xrightarrow{\text{DES, XOR}} 64 \rightarrow 59 & \\ & & + \text{"01"} \xrightarrow{\text{DES, XOR}} 64 \\ & \text{"111"} + 117\text{(L)} \xrightarrow{\text{DES, XOR}} 64 \rightarrow 59 & \end{array}$$


And the efficiency:

$$\begin{aligned} 234 - 128 &= 106 \\ 106 : 6 &= 17.7 \end{aligned}$$

This upgrade lets us add 106 new bits per iteration, which means we have to apply DES only every 17.7 bits. Now that’s progress!


How many more DES per iteration can we use?

The bit math scheme of $F_3$ looks like a binary tree, which means that theoretically it could grow bigger and bigger.

However, there are two “be careful” points: the distance between gained bits gets smaller and smaller ($3.5 \rightarrow 11 \rightarrow 17.7$) and the chance of collision without additional security methods gets bigger and bigger. Notice that already for the next upgrade, 128 bits won’t be enough to keep the $2^{56}$ operations security level. So it might not be worth it.

Therefore, let’s stop at $F_3$ for now.


And finally, what does the chaining look like?

There’s nothing new here. We can just take Rabin’s chaining, but instead of DES blocks, we use our $F_3$ function (let’s notate it as $F$ with indices for each cycle):

      M1     M2            Mn
       |      |            |
IV -> F_1 -> F_2 -> ... -> F_n -> H(M)

Let’s define the initial value as zero so that the first chunk $M_1$ could take all the input bits. Note that each message chunk should have the same length. That’s why if $M_n$ is too short, we complete it with padding zeroes.

Adding padding zeroes, however, creates a new problem. Imagine we have two messages that are less than one chunk long:

$$\begin{aligned} \mathrm{Mn}_1 &= 010101100 \\ \mathrm{Mn}_2 &= 0101011 \end{aligned}$$

And let’s say, each chunk has to be 16 bits. Then after padding, we get two identical strings for both $\mathrm{Mn}_1$ and $\mathrm{Mn}_2$:

$$\begin{aligned} \mathrm{Mn}_1 &= \mathbf{010101100}0000000 \\ \mathrm{Mn}_2 &= \mathbf{0101011}000000000 \end{aligned}$$

This creates a collision. And we don’t want that to happen, so we add length blocks into those chunks. They can show the length of padding or the length of the message. It doesn’t really matter which length to encode, but we will go with the length of the message. You’ll see later why. So this is what our message chunks look like after we added a length block:

$$\begin{aligned} \mathrm{Mn}_1 &= \mathbf{010101100}000\mathbf{1001} \\ \mathrm{Mn}_2 &= \mathbf{0101011}00000\mathbf{0111} \end{aligned}$$


How do we know that the construction that we’ve built is secure?

We’ve built a collision-resistant compression function $F_3$. Now we need to make sure the chaining is also collision-resistant. Let’s prove it in two steps:


1. If compression function $F$ is collision-resistant, then a hash function $H$ is also collision-resistant for all the inputs of the same length.

This step can be proved by induction.

Basis:

If the input consists only of one chunk $M$, the compression function $F$ will be applied only once. So in this case, the hash function $H$ is just our compression function $F$. And if $F$ is collision-resistant, so is $H$.

Induction:

Now we can assume a compression function $F$ applied to $k$ inputs is collision-resistant. We will call the output of it $H(M_k)$. Now we need to prove that it’s also secure for $k+1$ inputs (that $H(M_{k+1})$ is secure).

To do that, let’s take two different messages $M$ and $M'$ of the same length that produce the same outputs and look at the last compression function application $F_{k+1}$ and the inputs of it: last chunks $M_{k+1}$ and $M_{k+1}'$ and outputs of $H(M_k)$ and $H(M_k')$.


Case 1: The inputs of $F_{k+1}$ are different.

$$\begin{aligned} (H(M_k), M_{k+1}) &\neq (H(M_k'), M_{k+1}') \\ H(M_{k+1}) &= H(M_{k+1}') \end{aligned}$$

The inputs were different, but the function $F_{k+1}$ produced the identical outputs. That’s a collision. This would mean that the compression function $F$ that is collision-resistant per definition is not collision-resistant. This is a contradiction.


Case 2: The inputs of $F_{k+1}$ are identical.

$$(H(M_k), M_{k+1}) = (H(M_k'), M_{k+1}')$$

We know that $M$ and $M'$ are two different messages, so either $M_{k+1}$ and $M_{k+1}'$ are different (contradicts the Case 2 assumption), or one of the chains $H(M_k)$ or $H(M_k')$ produced the same output for different inputs, and therefore, is not collision-resistant (contradiction to the induction hypothesis).

This means a hash function $H$ can produce the same output for two messages only if either those messages were identical or the compression function $F$ was not collision resistant.


2. If a hash function $H$ is collision-resistant for all the inputs of the same length, then it is collision-resistant for all the inputs of the different length (considering the input included the length block).

This one is even easier to prove. Assume we have two inputs of different lengths: $M$ and $M'$. Let’s say $M$ is shorter than $M'$, and their hashes happen to be equal:

$$\begin{aligned} M &\neq M' \\ |M| &\lt |M'| \\ H(M) &= H(M') \end{aligned}$$

But we know that the last chunks of $M$ and $M'$ must have been different, since they included the length blocks. And because the lengths of $M$ and $M'$ are different, the outputs should have been different. Or there was a collision in the last $F$, which is impossible, since, as we’ve said in the last proof, $F$ was defined as a collision-resistant function.

To sum this proof up: If the hashes match, there was a collision in the last application of $F$, so either the lengths of messages were equal (contradiction) or $F$ was not collision-resistant (also a contradiction).


Congratulations! We’ve built the…

Merkle-Damgård construction! It was developed simultaneously by Ralph Merkle and Ivan Damgård and presented by both of them independently on the CRYPTO’89 Conference. We’ve built Merkle’s version today. Damgård’s idea differs just slightly. For example, he uses the padding-length instead of the message-length, and therefore his proof also differs. If you’re interested in his version of this hash construction, check his paper “A Design Principle for Hash Functions”.

Merkle-Damgård construction became the base of the modern hash functions. Its core - chaining, the Davies-Meyer step, a secure symmetric block cipher inside - was used in MD5, SHA 1, and SHA 2. However, some of those hash functions were still broken later. Why? You’ll have to wait for my next post to find out.


My sources and further readings:

Ralph Merkle “One Way Hash Functions and DES”
Ivan Damgård “A Design Principle for Hash Functions”
Gideon Yuval “How to swindle Rabin”
Michael O. Rabin “Digitalized signatures”