7
$\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.

Improve this question
$\endgroup$
3
  • $\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, 2015 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, 2015 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, 2015 at 12:04

1 Answer 1

Reset to default
3
$\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.
Improve this answer
$\endgroup$
9
  • 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, 2015 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, 2015 at 7:37
  • $\begingroup$ @Raphael - nice example with PRNGs, thanks. $\endgroup$
    – Miljen Mikic
    Jun 5, 2015 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, 2015 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, 2015 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.