[LINK] MD5 cracking

Rick Welykochy rick at praxis.com.au
Sun Jan 28 14:54:56 AEDT 2007

Paul McGowan - Yawarra wrote:

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

Actually this is a very interesting site. I hadn't gone to the home page
before writing the last post. The home page shows lots of (0 day?)
exploits. And the list should be sobering for all users of Apple,
Windows *and* Linux products.

As for fear mongering, perhaps. Better to be educated as to risks
that to live in fear and darkness I say :)

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

They do have a mil-dic.txt avilable with 36930 words (cracked passwds?)
in it. I wonder how they know they've cracked a password? Perhaps when
they obtain a completely ASCII (7-bit character only) string, probability
is 99.9999% that it is the password.

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

I wonder about the legality of such a site. It is (a) publishing
information on how to break into computer systems (zero day attacks)
and (b) providing cracked passwords.

Regarding MD5 vulnerabilities, <http://en.wikipedia.org/wiki/MD5#Vulnerability>
mentions this, for the technically-minded Linker:

    Because MD5 makes only one pass over the data, if two prefixes with the
    same hash can be constructed, a common suffix can be added to both to make
    the collision more reasonable. Because the current collision-finding techniques
    allow the preceding hash state to be specified arbitrarily, a collision can be
    found for any desired prefix; that is, for any given string of characters X,
    two colliding files can be determined which both begin with X. All that is
    required to generate two colliding files is a template file, with a 128-byte
    block of data aligned on a 64-byte boundary, that can be changed freely by
    the collision-finding algorithm.

Now of course this does not mean an end to downloading all of the MD5-summed
files out there, but it should encourage existing software librarians to
switch to SHA-256 as soon as possible.

When 56-bit DES was cracked, wasn't the move away from it to stronger
forms of encryption swift and decisive?


Rick Welykochy || Praxis Services

When I was a kid I used to pray every night for a new bicycle. Then I realized
that the Lord doesn't work that way so I stole one and asked Him to forgive me.
      -- Emo Phillips

More information about the Link mailing list