3

All the examples of MD5 hash collisions I've come across comprise two different messages (inputs) of the same length. The first and second messages have different values for a number of bits and the resulting MD5's are equal.

Does the theory of finding an MD5 hash collision (exploiting the weakness in the algorithm) prescribe that the lengths of the messages be the same? In other words would the theory be unusable to find a collision of two messages of different length? Has such a collision ever been found?

|improve this question
  • Considering md5 is designed to work with any arbitrary string length as input and there is a finite domain for potential md5 hashes (128 bit output), there is (and i'll lay my neck out on the line here) definitely a collision between inputs of differing length (somewhere..). Do I have an example? Unfortunately no, but you can logically deduce that such a string must almost certainly exist. – d0nut Jan 26 '16 at 22:47
  • @mgr326639, Might have better answers if you ask on crypto.stackexchange.com/questions/tagged/md5 – Pacerier Jan 27 '16 at 0:11
4

According to this article, the chosen prefix collision algorithm has been used to

produce two executable files with the same MD5 hash, but different behaviors. Unlike the old method, where the two files could only differ in a few carefully chosen bits, the chosen prefix method allows two completely arbitrary files to have the same MD5 hash, by appending a few thousand bytes at the end of each file.

While the sample files may be of the same length, the authors claim;

Our chosen-prefix collisions have only the requirement that after the collision the files should be exactly equal. Before the collision the two files, for which a collision is to be found, can be anything: our chosen-prefix collision finding method will always produce a collision that can be incorporated into the two files, irrespective of what data is present before the collision.

So yes, there are flaws in MD5 that can find collisions of different lengths.

|improve this answer
  • Have you checked the files? They're both the exact same size. :b – Mark Buffalo Jan 27 '16 at 3:01
  • I think that is just because the examples were trivial. I've updated the text with more info. Thanks @markbuffalo. – Neil Smithline Jan 27 '16 at 4:35
  • What I hear them say when I read that article is that the original files "can be anything". But the original files don't collide. Only after they have added some well chosen bits at the end of the files, the hashes collide. They don't say that those treated files can be anything too. And if it can, their example certainly doesn't show it. Because the untreated as well as the treated set of files are of equal length, as @Mark states. So what I see is just one more example of an MD5 collision of 2 files of equal length. – mgr326639 Jan 27 '16 at 21:22
1

Proving the existence of two different length plaintexts that collide using MD5 only requires you know that the number of inputs (and number of different lengths of inputs) are far greater than the number of possible outputs.

Given that MD5 can receive inputs of any length and can only output a hash of size 128 bits, that means that for all strings of bytes of any length they must map to the same 2 ^ 128 possible MD5 hashes.

For each input plaintext of length 128, there is guaranteed to be a collision with a plaintext that is of a size less than 128, because if MD5 was a perfect hashing algorithm it would hash each of those 128 bit length plaintexts (Hint: there's 2 ^ 128 of them, same number as possible outputs) to it's own unique hash, but that same set of output hashes must have been used for hashes of size 127 bits or less as well, so there must be a collision somewhere! Given this information we can prove mathematically the existence of two plaintexts of different lengths that have the same hash.

|improve this answer
  • 1
    I think that the OP's question is Does the theory of finding an MD5 hash collision (exploiting the weakness in the algorithm) prescribe that the lengths of the messages be the same?. You've not answered that as you don't discuss any theory for finding collisions short of brute force. – Neil Smithline Jan 26 '16 at 23:42
  • I have no doubt they exist. The same goes for any other hash algorithm like SHA256 as well. It's not hard to work out that of all the 100-character strings you can construct using only lower case, about 27142878777681384656699861072619000000000000000000000000000000000 with have [any random SH256 hash you pick]. – mgr326639 Jan 27 '16 at 10:33

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.