Addition step in MD5 implementation

Question

In MD5, there are four rounds. After every round, why do we need to add the computed $Q$ values to the initial values and then take this value as input to the next round. For example after the first round, we compute $$Q^{\text{new}}_1=Q_{60}+Q_{-4}, \ Q^{\text{new}}_2=Q_{61}+Q_{-3}, \ Q^{\text{new}}_3=Q_{62}+Q_{-2}, \ Q^{\text{new}}_4=Q_{63}+Q_{-1}$$ Why cant we directly take the computed values as the input to the next round without adding them to the initial values ?

Answer 1

The reason we, at the end of the compression function, add the input to the compression function, well, that's because otherwise the compression function would be invertible, and that would be bad.

Without that final step, the compression function would be invertible in this sense: given a desired compression function output and a message block, we would be able to find the compression function input. We would be able to do this because the MD5 compression function is made of 64 steps, and each step is itself easily invertible. Adding in the compression input at the very end breaks up this invertibility, because the analyst is unable to invert that final step (because he doesn't know the compression function input yet). He could guess the input at that stage, and then run the rest of the compression function backwards; this turns out to be no more efficient that just guessing the compression function input, and running it forwards.

This invertibility would be bad, because it allows an attacker to do tricks we'd prefer him not to. For example, we'd want a preimage attack (that is, given a hash value, give me a message that hashes to that) to take (with a 128 bit hash like MD5) roughly $2^{128}$ steps; that is, there is no method that is drastically more efficient that trying random messages and hashing them until you stumble across one with the correct hash. However, if the compression function is invertible, here is what that attacker can do, given a $Target$ hash value:

• Generate $2^{64}$ message prefixes, and generate the partial hashes to that point

• Generate $2^{64}$ message suffixes. When these, he would start with the $Target$ hash value, and compute the hash backwards until he gets the inverse partial hash (having first applied the MD5 final padding).

• Given those two lists of 128 bit items, he then looks for a match (and, by the birthday paradox, there's a good chance of being one.

And, if the partial hash of $P_i$ is the same as the inverse partial hash of $S_j$, then he knows that $Hash( P_i || S_j ) = Target$. This is because, when we evaluate the hash, we first run the compression function on the blocks from $P_i$; at the end of this evaluation, he would come up with the common partial hash value. Then, he would run the compression function on the blocks from $S_j$ after padding; he knows that, starting at this common value, that results in $Target$.

So, because of this, an attack we had hoped would take $2^{128}$ steps could be done with roughly $2^{64}$ steps. Making the compression function noninvertible (which the real MD5 does) prevents this line of attack.

Answer 2

This answer is incorrect and resulted from a misinterpretation of the relevant RFC

---

In the relevant RFC the authors state under "Differences Between MD4 and MD5"

4. Each step now adds in the result of the previous step. This promotes a faster "avalanche effect".

So this seems to be their rationale for that step. If it is reasonable, I really can't say.

But irrespective of that, if you want to implement MD5, then yes that step is necessary, as otherwise your implementation would be incompatible with other implementations.