Re: MD5 math question

[Tim <tim-security () sentinelchicken org>]

> Assume that a password between 1 and 24 ASCII characters was stored as
> an MD5 hash. No salt. What is the probability that someone cracking the
> password will find not the password that the user originally chose, but
> a different password that happens to collide with it? Intuitively it
> seems so unlikely that you wouldn't ever expect to see it. But what is
> the probability really?

It's been a while since I've worked this out, but a few semesters back,
we had to solve this problem in a class I took.  Please someone correct
me if I mess this up.

If you consult a random oracle, then the probability of a single
plaintext colliding with another plaintext's hash would be 2^-128, since
MD5 has a 128 bit output block.  The size of the input really doesn't
matter.  The probability of a single text colliding with another
specific one will be the same. This seems unintuitive at first, but when
you realize that the only way you can actually find a collision reliably
is to try a LOT of inputs, you'll be forced to work in a larger input
space.

Now, if you are actually wondering what is the chance that you crack the
hash via a different input, instead of the real password...  Well, you
might want to look into what the probability is that two plaintexts
exist in your specific input space which have the same hash.  And then,
what's the probability that three exist?  and so on ad infinitum.  Once
you know all of those, which of course will be incredibly small, then
you should be able to figure out a precise probability that one of those
others will be hit first.

That last part is just speculation though.
tim

-------------------------------------------------------------------------------
Watchfire's AppScan is the industry's first and leading web application 
security testing suite, and the only solution to provide comprehensive 
remediation tasks at every level of the application. See for yourself. 
Download AppScan 6.0 today.

https://www.watchfire.com/securearea/appscansix.aspx?id=701300000003Ssh
-------------------------------------------------------------------------------