Three way MD5 collision

Previously I explained how I created two images one of James Brown the other of Barry White with the same MD5 hash. At the end of the post I said I was going to try and create a three way collision where three images have the same MD5 hash. Neil K made a suggestion about the image

@natmchugh Image suggestion for the third hash collision: White, Brown, ...and Black -- http://t.co/yYEawVjPVa
— Neil K. (@kneil_) November 4, 2014

So I set to work.

After a couple of false starts where I started with the wrong image file I managed to achieve a three way collision. Here are the images.



If you want to check

$ curl -s http://www.fishtrap.co.uk/black.jpg.coll | md5
b69dd1fd1254868b6e0bb8ed9fe7ecad
$ curl -s http://www.fishtrap.co.uk/brown.jpg.coll | md5
b69dd1fd1254868b6e0bb8ed9fe7ecad
$ curl -s http://www.fishtrap.co.uk/white.jpg.coll | md5
b69dd1fd1254868b6e0bb8ed9fe7ecad

A new hash value

This isn't the same hash as before instead the 3 images now collide with a new hash value b69dd1fd1254868b6e0bb8ed9fe7ecad . This is because I had to add near collision blocks to all three images. In the case of the first two the blocks added are the same. This is probably best illustrated with a diagram.

1ZlLc9s4DIB/TaaneCzJz2OdpLuH3ZmdyaG7pw4t0RIbStRSdGz31xewAVmvdNKx7NgXW4RIiPwAASB1Fzyk2z+syJO/TST1nT+MtnfB453v+7ORD38o2R0kk+H8IIitig4i7yh4Vj8kCYckXatIFrWOzhjtVF4XhibLZOhqspXR9UfkImb1R8FzKHRb+lVFLjlIZ/7kKP9Tqjjhx3gTWkzhdqwjkiux1u5+L6LFp4J10aq2w0Pz3psMSbQj0YhU5iKrTeqHMWlNYGVxpEULVjQz0rk0NpK2JtIqe6mSC57AetYYGIhX6fZBarQgG+cw7Msbd0tgVma1R781gIC8Cr2mqbcAFonI8VKle2stXqV1Cmz0l1hK/Y8plFMG0SyNc4ik7PBZqxhvOJODlIY/Js5B8zNOyf+y2WwGK1UkDpx1EJrB+gWES2s22eB7HrcXQ+vDJ0hy6SM18HlpUunsDi3KBh3PyYDk8GMCvzk6lMeypOpM7AiCzBOXyo884YKQduMNrhDvJlFO9od3VsfrM7Yq31EXX44op/AdvYOvs+alDB+wlgUTT7cxxsjBSptNmAjrBikECnUfmXCd7pksekE08uuIpqSjQmg2awOa9MBnfBN8PFo9uxAruQAgyiR9ARJZZpzAN/YbdrTUgL733oymeyKtIOAE1YhTFVqd8YyFp+CatnA9GK1VgWtscoORUBRgSGNeoTZrULRoE12ZzFGt4U2hvY9Rz7kIUbIByH35mj+tv4teQAavhism2ns6ICf+yHQQiZ03h1yQQnvfqYCLXIX45w/n375KVRSD4XTwXYQvSw0/3w5D+koYwYyCElmgbFctwK921QLzHgxAxr/ueOg1Uuqo4w0/VzzkpHz+gNhXPBwGjTd6+r54WApPwsUTvm6HGtUTrDduB72zOVR7h3FbKWPOfsrVyagjXp0tY3jtHcSnTAr7ab/FLjlCGRNsxX7Fw6U2IWwpm2xhvehQgtJECEhwK9rKH6mKIhxzntp31lHadbDjDcNJ6NrF722ha5bFQdvxzsauXRffFLtWxOtICmdj1y6Sb4sdpwIuP7gmuAS7doXcOK74cDxjdiWuXy+Jp12/Ng7LPh7PhM5kylrjcnj4TLUbT/nCXZtH+ROqkcrzj8sF+nK+FWS46bsiPAEXXByPphfE03U+PtFIIcdwrkVx0D75f41H9oscVsPXcBXjf+mDsO1G7YfxuO3mHr+vs/ThHnWWhv+Fzm6PSFwKBB+9slCHEt/gd47MZOgHK6V1Q/R+J+oq7A30xl0TnnBAPwkD+nG25m4y6Ci6fD6Bq51OUL+TvI2K/eqOKIIPYtQ01iUmNpnQT0cpbKnXWSRRA3ywqlpCbpX7l8R4/R9eD8bYymBi5S1s8L23EBZmbff8K1HWCRtL3kyTDKf7S9BWajgAeK1/JvsNZtA8fhzb36t85wyefgI=

Again I created the files with HashClash. As inputs I used white.jpg and black.jpg images. To make brown.jpg.coll I just had to append the extra collision blocks to brown.jpg which was already a collision with white.jpg. 

I could go on adding more and more files in a tree structure to get many documents to collide. The number of collisions needed is n-1 where n is the number of files. It was this tree of collisions that allowed Marc Stevens to predict the 2008 US presidential election.

A word about file sizes

The files started out different sizes to each other, however, before each collision was generated between two files padding had to be added to one of the files to make it the same as the other. Without this step it would be impossible to extend a collision in the unpadded version to the full MD5 algorithm. This is because the padding includes the size of data processed.