1
$\begingroup$

I am researching the collision probability of MD5 and various attacks against it. Can someone help me how to learn the least probability that there will be a collision in a specific attack on MD5?

For example: MD5 has a collision probability of $1 / 2^{64}$ under the Birthday Paradox. Does this apply to any input given to MD5?

Also, is the output of MD5 uniformly distributed to the randomized input? (If, please provide references.)

$\endgroup$
3
$\begingroup$

MD5 has a collision probability of $1 / 2^{64}$ under the Birthday Paradox. Does this apply to any input given to MD5?

As explained in the other answer, $2^{64}$ is the birthday bound of messages until probable collision, not a collision probability. For two random messages you'd expect a $1/2^{128}$ probability of a collision with a 128-bit hash.

However, MD5 is broken with regard to collision resistance, so for two (or any number of) attacker controlled inputs you can't put a bound on it, they can find a colliding pair easily. (In fact, they can produce any number of messages that all collide, unless there are e.g. restrictions on message length.)

Also, is the output of MD5 uniformly distributed to the randomized input? (If, please provide references.)

This translates to "is MD5 PRF?", which as far as we know is the case. For a reference to the fact that we don't know how to distinguish it from PRF you can use e.g. RFC 6151, which uses that to justify why getting rid of HMAC-MD5 "may not be urgent".

$\endgroup$
2
$\begingroup$

MD5 has a collision probability of $1 / 2^{64}$ under the Birthday Paradox. Does this apply to any input given to MD5?

Not quite. In the general case, the probability of a collision depends on the number of messages. The $2^{64}$ comes into play because we need $\approx 2^{64}$ messages for a $50$% probability that any two of those messages collide under MD5.

There are specific attacks against MD5 which generate collisions without requiring so many messages. The fastest collision attack on MD5 works in on average $2^{18}$ time.

$\endgroup$
  • $\begingroup$ But if there is no direct attack on MD5 e.g. Adversary has no direct access to hashing oracle. then by uniformity property of MD5 can we say probability of collision in md5 is 1/2^64 ? $\endgroup$ – rijndael Jul 17 '15 at 19:35
  • 1
    $\begingroup$ The probability of a collision is wholly dependent on the number of messages you have. If you have any two messages, the probability is 2^-128. $\endgroup$ – user13741 Jul 17 '15 at 21:04
  • $\begingroup$ is there any way of determining if for "n" message what is probability of collision ? $\endgroup$ – rijndael Jul 20 '15 at 21:28
  • 1
    $\begingroup$ A handy approximation for that is P(n,m) = (n^2 - n)/(2^(m+1)) for n messages and an m-bit hash function. $\endgroup$ – user13741 Jul 21 '15 at 20:59
1
$\begingroup$

MD5 is broken with regard to collision resistance, so for two (or any number of) attacker controlled inputs you can't put a bound on it, they can find a colliding pair easily. (In fact, they can produce any number of messages that all collide, unless there are e.g. restrictions on message length.)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.