1
$\begingroup$

In one of my assignments, I came across this line

Due to MD5’s length-extension behavior, we can append any suffix to both messages and know that the longer messages will also collide. This lets us construct files that differ only in a binary “blob” in the middle and have the same MD5 hash, i.e. prefix || blobA || suffix and prefix || blobB || suffix.

I am not quite understanding what "binary blob" means in this context. Does the blob have to be something in particular to ensure that the two files will continue to have MD5 collision?

$\endgroup$
2
$\begingroup$

Here, I think BLOB is meant to be interpreted as binary large object, and it refers to the 128 bytes of data that differ between the two files but which produce the same MD5 hash output. Those are the two parts of the files that differ between the two programs but which yield the same MD5 partial result.

So look at it this way. You start out hashing each file at the beginning and compute the interim hash value through the prefix. Obviously both hashes will, at this point, be the same because the prefixes in both files are the same.

Now a new interim hash result is computed using the above mentioned result so far and the new chunk of data, the portion they refer to as BlobA and BlobB. These data chunks differ but were constructed to yield the same MD5 output. So after these middle sections are hashed, the partial hash for each file is still identical.

The hash process then continues on each file through the suffix, which like the prefix, is identical for both files. So the output (final) MD5 hash will be the same. At this point, my understanding of the passage you quoted is that if you have 2 files that hash to the same MD5 value, you can now append anything you like to the end of those files (as long as it is the same data for both files) and the MD5 hash will change for both files in exactly the same way, so they will continue to have identical hashes one to the other.

$\endgroup$
  • $\begingroup$ Yes, @otus, you are right of course. I was referring to the paper by Wang and Yu where their attack was on chunks of 128 bytes (1024 bits, or 2 blocks). I could have, and probably should have, specified that this attack as described in that paper generated collisions between 2 different messages each 2 blocks in length. From the caption under table 2, I believed the first pairs of blocks "set up" the collision for the next blocks. I confess I may have misunderstood and that better attacks might now exist... $\endgroup$ – WDS Oct 12 '15 at 10:18
  • $\begingroup$ Ok, thanks for clarifying. I know 1-block collision attacks exist, but I'm not sure they can be used here either. $\endgroup$ – otus Oct 12 '15 at 12:07
1
$\begingroup$

Binary blob refers to the two different blocks colliding. You need to align them with the message block boundaries. They are said binary blob because they are just binary data and they have no meaning per se. At this web page you can find a good explanaition. the important part is the following one. Given data1 and data2 the two colliding binary blobs, write the two following source codes:

Program 1: if (data1 == data1) then { good_program } else { evil_program }

Program 2: if (data2 == data1) then { good_program } else { evil_program }

if data1 and data2 are well aligned the two sources will collide.

$\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.