Re: MD5 To Be Considered Harmful Someday

[Solar Designer <solar () openwall com>]

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