Collision in Merkle–Damgård without a collision in compression function

Is it possible to find a collision in Merkle–Damgård just by omitting the extra one bit that is appended to each input without having a collision in compression function?

• I don't think so -- the length suffix should be enough to make the reduction work. – CodesInChaos Nov 28 '14 at 14:15
• No, you don't need any extra bits. It is sufficient that the padding function be suffix-free (one possibility to get a suffix-free padding is to append the length of the message as the last block). This was shown independently by both Merkle and Damgard at CRYPTO'89 for a specific suffix-free padding, and later generalized by Andreeva et al. in "Security Reductions of the Second Round SHA-3 Candidates". The proof was also carried out mechanically in Verified Security of Merkle-Damgard, which I co-authored ;-) – Malte Skoruppa Dec 2 '14 at 23:53
• @kasperd We may be thinking of different meanings of the term "padding" here, and thus simply misunderstand each other. For me a "padding function" is a function that splits a message into a list of fixed-size blocks. Hence, the type of $padding$ is something like $\{0,1\}^*\rightarrow(\{0,1\}^k)^*$. So for me your last comment does not even type ;-) It would be my pleasure if you could read the beginning of Section III of my paper above (until Definition 4), where this is precisely defined (very short!). Under these definitions, would you still say that a suffix-free padding is not enough? – Malte Skoruppa Dec 3 '14 at 0:50
• @MalteSkoruppa That makes sense. If the set of padded messages is suffix free, then there cannot be collisions in the hash function without collisions in the compression function. If padding had simply been a one bit followed by a sequence of zero bits (without the length field in the end), then the padding itself would be suffix free, but collision resistance wouldn't be guaranteed. – kasperd Dec 3 '14 at 1:02

No, it is not possible.

If two inputs with different length produce identical hash outputs, then there would be a collision in the last invocation of the compression function. This is because the last input to the compression function always encodes the length of the original message.

If two inputs with identical length produce identical hash outputs, then there would be a collision in the compression function somewhere along the way. This is because considering the entire Merkle-Damgård hash as a hash tree build up of invocations of the compression function, then you will get two trees with identical structure, but those two trees have different inputs and identical output. By induction it can be shown that at least one of the invocations of the compression function in that tree structure must have a collision.

Yes, of course it is possible. Let's consider with below example:

Our compression function: $f:\{0,1\}^{(128+512+1)} → \{0,1\}^{128}$

Message $x$ has 1000 bits: ($y$'s are our input blocks and $z$'s are output blocks. Considered a Merkle–Damgård construction.)

• $y_1$ is first 512 bits of $x$
• $y_2$ is last 488 bits of $x||0^{24}$
• $y_3$ is $0^{480}||“32-bit\ binary\ representation\ of\ 24”$

Iteration results:

• $z_1 = f(0^{129}||y_1)$ where $z_1$ has 128 bits
• $z_2 = f(z_1||1||y_2)$
• $z_3 = f(z_2||1||y_3)$ where $z_3$ is the message digest $h(x)$

Now suppose that message $x′$ has 488 bits and $h(x)=h(x′)$ … there is a collision for $h$:

• $y_1′$ is $x′||0^{24}$
• $y_2′$ is $0^{480}||“32-bit\ binary\ representation\ of\ 24”$
• $z_1' = f(0^{129}||y_1')$ where $z_1$ has 128 bits
• $z_2' = f(z_1||1||y_2')$ where $z_2$ is $h(x)$

Then $f(z_1'||1||y_2')=f(z_2||1||y_3)$ and $y_3=y_2'$

• if $z_1′ \neq z_2$ then a collision is found for $f$
• if $z_1' = z_2$ then $f(0^{129}||y_1') = f(z_1||1||y_2)$, there is also a collision for $f$

For our above example – if there is a collision, it can only be in our $f$ function. But, if you erase $1$ for each input you'll get collision in your inputs.

• Welcome to crypto.SE! $\;$ Is your claim that SHA-1 without insertion of the extra 1 bit is breakable? Are you exhibiting an explicit collision? If yes, what are the two colliding messages? $\;$ I'm trying to follow you, but fail. If guess you mean $f:\{0,1\}^{128+512+1}\to\{0,1\}^{128}$ (written $f:\{0,1\}^{128+512+1}\to\{0,1\}^{128}$ on this nice website, which handles a subset of $\TeX$), but then I'm getting lost; what's $y$, why does the binary representation of 24 matters (I get that $24=512-488$ but fail to see the significance), what is $z$, what is "z1=f 0^129||y1 z1" meaning? – fgrieu Nov 28 '14 at 17:20
• yi =(y1,y2,..yn) are our input blocks and zi = (z1, z2,..., zn) are out blocks when we consider schema of Merkle-Damgard.I'm new that's why I don't know how to use it properly, yet. f is our function I forgot ()'s add. binary representation of 24 is matter because of shows if y2' and y3 are equal, we can calculate and see there is something wrong in f function. – aysebilgegunduz Nov 28 '14 at 21:54
• It is not clear to me what kind of padding function you are using here - why do you always append $0^{480}||“32-bit\ binary\ representation\ of\ 24”$ as the last block, independently of the message length? What seems clear is that your padding function is not suffix-free - if $x'$ equals the last 488 bits of $x$, then $pad(x')$ is a suffix of $pad(x)$. The strengthened Merkle-Damgard iteration however prescribes a suffix-free padding function. Only under this assumption is the "collision-resistance" of $f$ preserved by the Merkle-Damgard iteration. – Malte Skoruppa Dec 2 '14 at 23:37
• Your padding is incorrect. The correct padding ends with the length of the message (measured in bits). Thus since $1000 \neq 488$ it follows that $y3 \neq y2'$. – kasperd Dec 2 '14 at 23:40