*****************
* HingOn Miu    *
* hmiu          *
*****************


Implementation descriptions:

1.) Find two 1024-bit messages (each block is 512 bits) <M0, M1> and <M0', M1'>
2.) Repeat the following steps until the first block is found
3.) Select a random block M0
4.) Modify M0 by message modification techniques
5.) M0 + ^M0' produce the first iteration differential
6.) Test if all characteristics hold by applying compression function on M0 and M0'
7.) Found M0 and M0'
8.) Repeat the following steps until a collision is found
9.) Select a random block M1
10.) Modify M1 by message modification techniques
11.) M1 + ^M1' produce the second iteration differential
12.) Test if M1 and M1' collide

The attack works on files of arbitrary length, since the attack only requires the 
128 bytes somewhere in the middle of the file to be different and all other message 
blocks are identical. Say we are generating 2 messages of N blocks. The first i - 1 
blocks can be chosen arbitrarily of your choice, and we apply the attack and 
generate two different sets of <Mi, Mi+1> and <Mi', Mi+1'> given the same internal 
state of the MD5 hash function of previous i - 1 blocks, and the remaining blocks 
can be chosen arbitrarily since the internal state of the MD5 has function will be 
the same after the attack.

The format of the document should be restricted. As we see in the program examples, 
most of the portion in the two programs are identical because only 128 bytes are 
different. So, the document should also have mostly identical content. Actually, we 
can just treat the document as a program since it is only a difference in the matter 
of file type extension. Therefore, the attack would not attack in a completely 
stealth manner on an ASCII document since we cannot view the content of the document 
(stealth manner), but the attack requires us to treat it as a program and make 
modification accordingly.


Reference:

Wang X., Yu H. (2005) How to Break MD5 and Other Hash Functions. In: Cramer R. (eds) 
Advances in Cryptology – EUROCRYPT 2005. EUROCRYPT 2005. Lecture Notes in Computer 
Science, vol 3494. Springer, Berlin, Heidelberg