Menu
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
MD5 Fixed Point
MD5 Hash Collisions
679
Generally, two files can have the same md5 hash only if their contents are exactly the same. Even a single bit of variation will generate a completely different hash value. There is one caveat, though: An md5 sum is 128 bits (16 bytes).
Another benefit of using a hashing algorithm like MD5 is that the resulting hashes have a known even distribution, meaning your ids will be evenly distributed without worrying about keeping the id values themselves evenly distributed. So that's not bad at all; less than a percent over/under for distribution per node.
Padding means adding extra bits to the original message. So in MD5 original message is padded such that its length in bits is congruent to 448 modulo 512. Padding is done such that the total bits are 64 less, being a multiple of 512 bits length.
Yes MD5 is deterministic, and this is considered a desirable characteristic for many applications of message digest functions.
(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
144
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
