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.

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 Qnew1=Q60+Q-4, Qnew2=Q61+Q-3, Qnew3=Q62+Q-2, Qnew4=Q63+Q-1. Why cant we directly take the computed values as the input to the next round without adding them to the initial values ?

share|improve this question
    
I'm a bit confused about your notation. If we take en.wikipedia.org/wiki/MD5#Pseudocode as a reference, are we talking about the last steps in the outer loop, where we compute $h_0 := h_0 + a$ and so forth? –  Maeher Jun 11 '12 at 10:16
    
yes i am referring to the steps h0 := h0 + a; h1 := h1 + b; h2 := h2 + c; h3 := h3 + d; I want to know that why do we need to add the values a, b, c, d to the initial values. Will there be any problem if i just take the values a, b, c, d as input to the next round. –  cryptofreak Jun 11 '12 at 10:40
    
Yes, it is required and you must do it (but it is only done at the very end of the compression function, not after each round). Are you asking for why it needs to be done or just if it is really necessary to do so? –  Thomas Jun 11 '12 at 10:55
    
I want to know that why it needs to be done. –  cryptofreak Jun 11 '12 at 11:23
add comment

2 Answers 2

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.

share|improve this answer
add comment

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"

  1. 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.

share|improve this answer
    
thanks for the answer Maeher. But I still dont get that how it can promote a faster avalanche effect. If you have any idea, please let me know. –  cryptofreak Jun 11 '12 at 11:10
    
MD4 has exactly the same step at the end of its compression function, hence this is not the answer. –  poncho Jun 11 '12 at 14:21
    
You are indeed correct. I must have misread that. Apparently the step they are referring to is each of the 64 round operations. –  Maeher Jun 11 '12 at 14:27
add comment

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.