Is there any relation between two strings with the same MD5 hash?

Is there any relation between two strings with the same MD5 hash?

For example these two strings:

0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef


and

e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef


have the MD5 hash:

cee9a457e790cf20d4bdaa6d69f01e41


Does any regular relation between these two strings or any strings with the same MD5 exist?

• You might have to clarify what you mean by relation. They're clearly identical in nearly every byte. And obviously, they have the relationship that their MD5 hashes are identical. – Stephen Touset Nov 15 '15 at 20:43

In general, no: two bitstrings with the same MD5 need not be related by a simple relation (other than the obvious have the same MD5). Argument: take $2^{128}+1$ distinct random $1024$-bit bitstrings; by the pigeonhole principle, at least two are bound to have the same MD5; since less than $2^{257}$ pairs of distinct bitstrings can be picked among $2^{128}+1$, and our colliding bitstrings where generated with $1024$ bits of entropy each, they must be unrelated in the sense that at least $1024-257=767$ bits from one can't be deduced from the other.

However, some of the efficient methods we have to generate two bitstrings with the same MD5, and all efficient methods that work for 512-bit bitstrings as in the question, produce bitstrings of the same length, and differing only by very few bits within each 512-bit block. The question's example matches that given by Tao Xie and Dengguo Feng in Construct MD5 Collisions Using Just A Single Block Of Message, 2010. That seems to be the first 512-bit MD5 colliding pair published, tough without disclosure of the method. For public method and code, see Marc Stevens, Single-block collision for MD5, 2012; (alternate link to the paper). The location of the bit differences are characteristic of the method, and the differential path it uses.

Further, for some of the first methods discovered to efficiently generate MD5 collisions, bit differences are bound to occur in two adjacent pairs of 512-bit blocks; see in particular Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, in proceedings of Eurocrypt 2005.

To generate very different bitstrings with the same MD5 (including: starting with different chosen strings, and/or of different length), the best first known method required in the order of $2^{65}$ evaluations of the MD5 round function; see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website). This would be feasible, was attempted over 11 years ago, but remains a little hard, and never was publicly done AFAIK.

Update: as pointed by otus, we now have more efficient methods allowing to generate colliding bitstrings with any chosen prefix using approximately $2^{16}$ less work (with the restriction that the bitstrings must have the same length, and be nearly identical in their last block). See Marc Stevens, Arjen Lenstra, Benne de Weger: Chosen-prefix collisions for MD5 and applications, in International Journal of Applied Cryptography, Volume 2 Issue 4, July 2012, Pages 322-359; the HashClash page on Chosen-prefix Collisions; this striking application to images.

• @otus, Oh, I did not knew chosen prefix attacks on MD5, and made a very wrong answer! Thanks for correcting me!! – fgrieu Nov 16 '15 at 19:40
• I'm not sure your first argument holds. If you have $2^{128}+1$ bit strings, two of them will have the same MD5, but it doesn't necessarily follow that any two such bitstrings don't have some sort of simple function relating the two. It's unlikely that this is the case, but I would posit that the simple fact that we've found colliding strings in less than $2^{128}$ (thus, tautologically, they have a "more simple" relation than simply having equal MD5 hashes) actually makes this more probable. – Stephen Touset Nov 16 '15 at 20:13
• @Stephen Touset: Would you agree with my revised argument? I'm not claiming that it is rigorous, but hope it is closer. – fgrieu Nov 17 '15 at 6:58

Here is what I see from the two strings:

• 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef
• 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef

The bold characters are those that are different between the two strings. MD5 collisions occur due to the structure of the MD5 hash its self. Assuming the two strings are in hex notation, when translated into bits, the result is only a switched bit (0x70 to 0x74 is 0b01110000 to 0b01110100, and 0x5c to 0xdc is 0b01011100 to 0b11011100). Looking at This Wiki Link can give other examples and a more in-depth analysis of how collisions occur in the MD5 hashing algorithm.

• Hi Mr Public and welcome to Crypto! In your answer you show two things: 1) that the digest results are different and 2) a link that explains how collisions occur in MD5. Given that we already know that the strings differ, the answer should contain at least a short description on why they differ (according to the Wiki article). Answers on StackExchange should not just rely on external information. – Maarten Bodewes Nov 16 '15 at 13:55