Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.)
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".
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.
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.)
