[LINK] MD5 cracking

[Paul McGowan - Yawarra]

Rick postulated:

> 
> We have know for a while now that the MD5 digest is insecure, i.e. it
> is now possible to make changes to a file such that its MD5 matches
> a desired (bogus) MD5.
> 
> I ran across this site today:
> 
> http://milw0rm.com/cracker/list.php
> 
> As they say, it's "in the wild". The web page provides a service to
> crack MD5 digests. Sigh.
> 
> I mention this because practically all software we download is 
> cross-checked and vetted against its MD5 digest, and nothing more
> secure. This implies that updates from Winders, downloads of
> FOSS etc.etc. could easily be compromised if the desire to do so
> is there. And it is probably only a matter of time before a
> jacked/hacked but secure-looking version of software product XYZ is
> released on the 'Net.

I'm not so sure that the site you reference is a good example of the 
consequences you subsequently claim Rick.  Though I doubt it was your 
intention, such claims could appear to be scaremongering.

Yes, it has been shown that collisions in MD5 are possible and have 
been demonstrated.  That, however, is not the same as being able to 
make arbitrary changes to a downloadable file.  The page you 
reference appears (to me) to demonstrate that MD5 _password_ digests 
have been cracked successfully.  How they (milw0rm) do this, we don't 
really know, but given the size of the passwords I would have thought 
that a distributed attack was fairly likely (try every combo).  
Moreover, if the site has access to a large number of bots, then the 
generation of a rainbow table would also seem to be a possibility.

The consequences of this however, are not necessairly that any 
software downloaded and checksummed using MD5 is now untrustable, 
just that a password file (or the shadow file) can now be attacked in 
much the same way as its predecessors which used lesser hashes.

Say, for example that I demonstrate that I can create a file that 
hashes to the same thing as the latest Firefox download.  In itself, 
this would be a useful crytographic result, and probably qualify me 
highly (I can't, btw).  However, this would not be the same as being 
able to create executable, malicious, and similar size code.  Those 
constraints make the task much, much harder.  

What the milw0rm site demonstrates is not even the first part.  They 
can take an MD5 digest and extract the *very short* string that was 
used to create it (some of the time). That's all...

Regards,

Paul McGowan
-----------------------------
Yawarra Information Appliances Pty Ltd
http://www.yawarra.com.au/
Tel: 1300 859 799 / (03) 9800 2261
Fax: (03) 9800 2279
PO Box 606, Boronia VIC 3155