bugtraq - Re: MD5 To Be Considered Harmful Someday

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <41B77A4C.3010103@doxpara.com>
Date: Wed, 08 Dec 2004 14:03:56 -0800
From: Dan Kaminsky <dan@...para.com>
To: Solar Designer <solar@...nwall.com>
Cc: Gandalf The White <gandalf@...ital.net>, davids@...master.com,
	BugTraq <bugtraq@...urityfocus.com>
Subject: Re: MD5 To Be Considered Harmful Someday

>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.
>  
>
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.

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.

--Dan
www.doxpara.com