# Generalize the Merkle–Damgård construction for any compression function

I am trying to figure out this question:

Generalize the Merkle–Damgård construction for any compression func­tion that compresses by at least one bit . You should refer to a general input length £' and general output length E (with £' > E).

It is in my understanding that the Merkle–Damgård takes an input of 2*l(n) and compresses it to l(n). How would I go about breaking up the input so that an arbitrary hash length L' can be outputted?

• Let $m = m_1 m_2 \dots m_n$. Suppose $y_0$ is fixed and let $y_i = f(y_{i-1}, m_i)$, $h(m) = y_n$. This is the basic Merkle-Damgård construction, but some extra tricks are needed. You first need to understand why these tricks are needed. Study how you recover a collision for $f(\cdot)$ from a collision in $h(\cdot)$. Then come up with a suitable trick. Hint: expansion. – K.G. Apr 24 '14 at 12:51

You understanding is a bit incorrect. There is no requirement that the output length of the compression function is exactly half of that of the input. Typical compression functions have an output which is much shorter than half the input length.

The Merkle-Damgård construction uses a compression function which takes an input with a length that is the sum of the internal state and one block and an output which is the length of the internal state.

If the size of input and output of the compression function differs by only a single bit, that would lead to a block size of just one bit.

A block size of just one bit would work most of the way. But it would fail in the final block which needs enough room for length padding. You couldn't do length padding in a single bit.

But you could create a new compression function by combining multiple invocations of the original compression function. For example if your original compression function compresses $k+1$ bit to $k$ bits, you could invoke it $k$ times in order to compress $2k$ bits to $k$ bits. Then you could build a Merkle-Damgård construction by using this new compression function.

A different but equivalent formulation would be that you ignore the requirement that the entire length padding fit in a single block in the Merkle-Damgård construction and compensate for any weaknesses that could be introduced from that by still padding to multiples of a block size, which would be large enough to hold the length field.

This construction assumes the compression function is collision resistant, which implies that the output is long enough. If the output was too short a collision could be found by brute force.