Bugtraq mailing list archives
Re: MD5 To Be Considered Harmful Someday
From: Solar Designer <solar () openwall com>
Date: Sat, 11 Dec 2004 22:26:33 +0300
On Wed, Dec 08, 2004 at 02:03:56PM -0800, Dan Kaminsky wrote:
Brute force work efforts like password cracking tend to be an exponential times a constant -- say, 2^32 operations that take 100ms each. Increasing the complexity of a legitimate password verification increases the constant. Interestingly, the more efficient a legitimate verifier becomes, the more efficient your brute forcer is.
Well, it can be assumed that an attacker could always have used the better optimized implementation in a brute-forcer. But there's more to it. Legitimate verifiers (using your terminology - which I like) will always remain slower than optimal cracker programs. The primary factor which makes for the difference in favor of password cracking is the extra parallelism which may be brought down to instruction level (to make more effective use of resources of a non-special-purpose CPU). For bcrypt, there's already a 2x difference (cracking twice faster than verification) between potential optimal implementations on some newer real-world CPUs (Itanium). On the FreeBSD-style MD5-based password hashing:
Of course, as I've said elsewhere passwords really aren't at all vulnerable to the MD5 attack.
Yes. I did not want to bring the argument that there's still no way to produce a message for a given/fixed MD5 hash with little effort. I felt that the argument I did make is stronger. But you seem to feel otherwise. :-)
But, if they were, extra iterations wouldn't be helpful.
This is not simply extra iterations of MD5, re-using _only_ output from a previous iteration as input for a new one (if this was so, then your statement would be precisely correct).
Once the first round collided, all future rounds would continue to collide.
Not in phk's algorithm we're talking about. Somewhat simplifying things, let's say the first iteration would collide for {password1, salt} and {password2, salt}. But the second iteration would have something like {C1, password1, salt} and {C1, password2, salt} as its input, and subsequent iterations would use things like {password1, salt, password1, C2} and {password2, salt, password2, C2'} (notice the changes in ordering of inputs). We can't be sure whether C2 = C2' or whether subsequent iterations would collide or not based exclusively on the fact that the first iteration collided. -- Alexander Peslyak <solar at openwall.com> GPG key ID: B35D3598 fp: 6429 0D7E F130 C13E C929 6447 73C3 A290 B35D 3598 http://www.openwall.com - bringing security into open computing environments
Current thread:
- RE: MD5 To Be Considered Harmful Someday, (continued)
- RE: MD5 To Be Considered Harmful Someday David Schwartz (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Gandalf The White (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Keith Oxenrider (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Paul Wouters (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Dan Kaminsky (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Paul Wouters (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Adam Shostack (Dec 09)
- RE: MD5 To Be Considered Harmful Someday David Schwartz (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Solar Designer (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Dan Kaminsky (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Pavel Kankovsky (Dec 09)
- Re: MD5 To Be Considered Harmful Someday Solar Designer (Dec 13)
- Re: MD5 To Be Considered Harmful Someday George Georgalis (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Dan Kaminsky (Dec 08)
- Re: MD5 To Be Considered Harmful Today Dan Kaminsky (Dec 08)
- Re: MD5 To Be Considered Harmful Today Pavel Machek (Dec 08)
- Re: MD5 To Be Considered Harmful Today Dan Kaminsky (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Jack Lloyd (Dec 08)
- Re: MD5 To Be Considered Harmful Someday Jack Lloyd (Dec 08)