Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 12:51

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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