WebApp Sec mailing list archives
Re: MD5 math question
From: Tim <tim-security () sentinelchicken org>
Date: Tue, 3 Jan 2006 22:59:22 -0500
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 -------------------------------------------------------------------------------
Current thread:
- MD5 math question Jeff Robertson (Jan 03)
- Re: MD5 math question Chris Varenhorst (Jan 03)
- Re: MD5 math question Tim (Jan 03)
- RE: MD5 math question Vipul Kumra (Jan 04)
- Memo: Re: MD5 math question tim . m . james (Jan 04)
- Re: MD5 math question Charles Miller (Jan 05)
- Re: MD5 math question exon (Jan 06)
- Re: MD5 math question Tim (Jan 06)
- Re: MD5 math question exon (Jan 06)
- Re: MD5 math question Tim (Jan 07)
- Re: MD5 math question exon (Jan 07)
- Re: MD5 math question Tim (Jan 07)
- Re: MD5 math question exon (Jan 06)
- Re: MD5 math question Charles Miller (Jan 06)