2
$\begingroup$

In the paper "Cryptanalysis of the Hash Functions MD4 and RIPEMD" the authors introduce the following notation (paragraph 4.1):

$\Delta$$H_0$ = 0 $\xrightarrow{(M_,M')}$ $\Delta$$H$ = 0

What exactly does this mean? I understand that $\Delta$$H$ is probably the difference between hash outputs, but what about $\Delta$$H_0$?

Disclaimer: I have zero knowledge about differential cryptanalysis, so my apologies if the formula above is some kind of standard notation there.

$\endgroup$
2
$\begingroup$

In the MD4 algorithm, the message which is being hashed is split into a series of 512-bit blocks. The collision attack which you reference forms a collision in a single block. That is, the attack forms two colliding messages, X and X', which are identical for every block but one. The paper refers to the blocks of X and X' which differ from one another as M and M', respectively.

Because the parts of X and X' which come before blocks M and M' are identical, they have the same hash. The hash of these blocks is referred to as H$_0$. So $\Delta$H$_0$ = 0 is just saying that the intermediate hash of the messages before blocks M and M' are identical.

$\xrightarrow{(M_,M')}$ means that block M is hashed as a part of its message, and block M' is hashed as a part of its message.

Once these message blocks have been hashed, the hashes of the two messages are still identical, which is what $\Delta$H = 0 is saying.

So, what the equation as a whole is saying, in English, is: "The intermediate hashes of two messages are identical. Then, we process a single block of each message. These blocks are called M and M'. Even though these blocks are not identical, their final hashes are identical."

Note that in some papers for differential cryptanalysis, M and M' will refer not to a single message block, but to the message as a whole. So this is not standard notation.

When I was starting out in differential cryptanalysis, I also had a hard time understanding this equation, but I hope this has helped you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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