mailing list archives
Re: MD5 To Be Considered Harmful Someday
From: Dan Kaminsky <dan () doxpara com>
Date: Wed, 08 Dec 2004 14:03:56 -0800
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.
The algorithm is far more complicated than "raw" MD5. It consists of
1000 iterations of MD5 with both output from the previous iteration
and the original input (plaintext password and salt) being rolled into
the hash on each iteration.
Not that brute force is the only approach available. There are numerous
attacks that might break "pure" MD5 but fail given such massive
overlapping. There are, however, others that abuse extra rounds to
great effect. For instance, SHA-0 is an 80 round algorithm. Biham's
paper (http://eprint.iacr.org/2004/146/) showed that an 82 round variant
is actually much weaker. And Joux's unreleased paper makes it very
clear that simply stacking primitives doesn't create nearly the level of
combinatorial complexity that you'd expect.
Of course, as I've said elsewhere passwords really aren't at all
vulnerable to the MD5 attack. But, if they were, extra iterations
wouldn't be helpful. Once the first round collided, all future rounds
would continue to collide.
Re: MD5 To Be Considered Harmful Someday Ruth A. Kramer (Dec 08)
MD5 To Be Considered Harmful Today Pavel Machek (Dec 08)
Re: MD5 To Be Considered Harmful Someday Joel Maslak (Dec 08)