6
$\begingroup$

Does MD5 map to all possible 128 bit numbers? To put it another way: For every 128 bit number y, does there exist at least one x for which md5(x) = y?

The answer probably is yes, for arbitrary x, and probably no proof exists. However, feel free to prove me wrong :)

But what if I impose some kind of limit on x, e.g. x <= x_max? Of course, for very small x_max the answer is no. But what is the minimum value of x_max for which the answer likely becomes yes? Or the maximum value for which the answer can be shown to be no?

I'm not really interested in the exact value for x_max, rather in the approximate order of magnitude.

$\endgroup$

migrated from stackoverflow.com Jun 3 '15 at 11:26

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ See stackoverflow.com/questions/2658601/…. In particular, the part in the accepted answer that talks about the "random oracle." It seems clear that the only way to prove surjectivity of a hash function is by exhaustive search. $\endgroup$ – Jim Mischel Jun 2 '15 at 16:16
  • 1
    $\begingroup$ @jim-mischel: I did see that, and the second comment to that answer claims that its main argument is wrong. I can't verify that, or else I hadn't asked that question here. The question/answer also is five years old and doesn't mention MD5, so I thought I might try to get a more specific response :) $\endgroup$ – Daniel Sk Jun 3 '15 at 7:08
  • 1
    $\begingroup$ I wonder if Computer Science was the best migration target. Information Security, Cryptography (because of the use of MD5 lies there) or even Mathematics (because you ask about mathematical properties of a function) may have been better. $\endgroup$ – Raphael Jun 3 '15 at 12:04
2
$\begingroup$

Q: Does MD5 map to all possible 128 bit numbers?

Taking into account the facts that MD5 accepts input of the arbitrary length, the output is "only" 128 bits, and the algorithm itself which behaves similarly to random functions, I would expect that the all outputs are possible. However, without any strong mathematical evidence, this is merely a speculation, or in the best case, the hunch.

Q: The answer probably is yes, for arbitrary x, and probably no proof exists.

Exactly, there is no proof (currently). Proving that MD5 is surjective would require either one of these:

  • Brute force check - taking into account coupon's collector problem, it takes something like 10^40 inputs to hit all 128-bit outputs. Assuming again that MD5 behaves similarly to random function, that should be enough to verify in the case that MD5 is surjective.
  • Concrete mathematical proof - eventual proof of surjectivity should be able for arbitrary 128-bit number y prove that there exists some input x such that MD5(x) = y. That should require deep mathematical analysis of MD5 function and it would probably shed some light on reversing this hash function. Even though MD5 is far from desirable hash function, it is still not known how to predict the input based on the given output.
$\endgroup$
  • 1
    $\begingroup$ "the existence of [a proof] would probably require breaking the hash function" -- how so? Popular PRNGs are surjective and you don't need to "break" them in order to show that. (However can you break a hash function, anyway?) $\endgroup$ – Raphael Jun 3 '15 at 12:06
  • $\begingroup$ @DavidRicherby You are aware that MD5 is far from this pathological example that you provided. More convincing example would be f(x)=2x, which at least takes x into account :) However, I got your point so I edited my answer. And I am curious, how would you represent 1000 with nine bits? $\endgroup$ – Miljen Mikic Jun 5 '15 at 7:37
  • $\begingroup$ @Raphael - nice example with PRNGs, thanks. $\endgroup$ – Miljen Mikic Jun 5 '15 at 7:39
  • $\begingroup$ "That should require deep mathematical analysis of MD5 function and it would probably shed some light on reversing this hash function." -- I still don't follow this train of thought. The simple hash function $x \mod n$ for $x$ a number encoding of your data is trivially surjective, assuming $x$ does not have a very weird domain. I don't see how this knowledge makes is worse as a hash function. (Security by obscurity is no security at all!) $\endgroup$ – Raphael Jun 5 '15 at 8:09
  • $\begingroup$ Thanks for the edit. Nine bits? It's not computer science if there aren't off-by-one errors. *cough* $\endgroup$ – David Richerby Jun 5 '15 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy