MD5 Inverse Identity: Does (X,Y) exist such that md5(X)=Y and md5(Y)=X

Question

Do there exist two 128-bit values that hash to each other?

Find (X,Y) such that md5(X) = Y and md5(Y) = X

can they be found without brute force?

For extra credit: Am I allowed to make up the term "md5-itive inverse identity?"

The solution set will be sparse, if not empty.

For your LOL's today, here ya go:

https://github.com/flipmcf/playground/tree/master/md5-inverse-search

The first question has been discussed at length here and on XKCD forums. The second question prevents this from being a duplicate. — Bill the Lizard, Jun 03 '09 at 19:20
And here is perhaps the first non-comic link to XKCD on Stack Overflow. http://echochamber.me/viewtopic.php?f=12&t=29547 — Bill the Lizard, Jun 03 '09 at 19:21
[Exact duplicate of conjunction of 2 questions](http://meta.stackexchange.com/questions/122416/what-if-a-question-is-an-exact-duplicate-of-the-conjunction-of-two-other-questio): http://stackoverflow.com/questions/1756004/can-two-different-strings-generate-the-same-md5-hash-code and http://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x — Mechanical snail, Sep 15 '12 at 00:04
@Mechanicalsnail I don't believe Question 2 is a duplicate of http://stackoverflow.com/questions/1756004/can-two-different-strings-generate-the-same-md5-hash-code It is the search for two 128-bit numbers where the md5 operation acts as an inverse. For example, the values '1.618' and '0.618' (golden ratio) and the operation '1/x' — FlipMcF, Jul 16 '13 at 22:18
'md5 inverses' would be the appropriate term. analog to 'multiplicative inverses' which are easy: if f(x) = 1/x then the pair of #'s (2, 0.5) are inverses: f(2) = 0.5 f(0.5) = 2 The 'identity' or 'fixed point' for multuplication is '1': f(1) = 1 — FlipMcF, Jul 16 '13 at 23:11
Notch (Possibly the same guy who gave us the 'Creeper' and the 'Nether') used his powers of math and determined there is a %37 chance that an X exists for md5(X) = X http://echochamber.me/viewtopic.php?f=12&t=29547#p957471 — FlipMcF, Jul 19 '13 at 01:38
I am editing this post to MD5(X) = Y and MD5(Y) = X and letting the http://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x deal with the MD5(X) = X question. — FlipMcF, Jul 19 '13 at 01:41

score 4 · Answer 1 · answered Nov 13 '09 at 19:23

(Both answers were found while reading this link)...

To answer question (1), consider the following:

Brute forcing all md5(x)=x means checking 2.4x10^38 values. My quick test implementation can test some 2.3x10^9 values per hour, meaning it would take almost exactly 10^29 hours to brute force it. Let's say I get a million people to help me out, then we're down to 10^23 years.. And let's say the algorithm gets a million times faster with some clever optimization, and we're down to 10^17 years. And let's pretend computers get a million times faster over night, and we're down to 10^11 years, which is significantly longer than the universe has existed for.

I would imagine the above could be culled faster with some smart force algorithm†.

To answer question (2), the following two blocks have the same md5 hash:

d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70

and

d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70

6 bytes differ between the two blocks (bytes 39, 91, 119, 167, 219, and 247), and the hash is 79054025255fb1a26e4bc422aef54eb4. I would imagine the blocks were discovered by some kind of smart force algorithm†, though I don't know for sure.

†: brute force taking into account the analyzed weaknesses of md5

Question 2 not answered... you answered md5(X) = Y and md5(X') = Y Question 2 is find (X,Y) such that md5(X) = Y and md5(Y) = X (or prove that the solution set it empty) — FlipMcF, Jul 16 '13 at 23:18

defines · Answer 2 · 2009-06-18T16:04:52.147

This is not the same as the Kember Identity Search.

Consider the differences of the following cases:

md5(X) == X

For this to be true, X must be a 128-bit value.

This is not the same as the following:

bin2hex(md5('string')) == 'string'

Which is what the Kember Identity Search is actually seeking. If you take a look at any of the search implementations on their site, you can easily see that they are working with 32-character strings, not with 128-bit numbers, as the input to the md5 function, and thus are not seeking md5(X) == X.

I am not the first to point this out either, you might find This Article Directly Targeting The "Kember Identity" by Kris Thompson enlightening.

MD5 Inverse Identity: Does (X,Y) exist such that md5(X)=Y and md5(Y)=X

Related:

2 Answers2