MD5 and SHA cracked/broken...

[Kirk Job-Sluder]

On 2004-09-11, Magnus Lie Hetland <mlh at furu.idi.ntnu.no> wrote:
> Basically, at Crypto 2004 preliminary papers were presented that
> pointed out weaknesses in MD5, SHA-0 and SHA-1. As far as I can tell,
> MD5 is broken and SHA-1 seems to be in a precarious position (even
> though I don't know the details at all).

It is always good to read carefully.  

An algorithm has been published that makes it easier than it should be
to find collisions in MD5.  On the other hand, weaknesses in MD5 have
been known for a few years now, so this is not much of a surprise.  What
this means is that it is possible to create two sequences that produce the
same MD5 hash result.  The sequences required to produce identical MD5
hashes seem to be meaningless except for the fact that they produce
identical MD5 hashes.  

Likewise, a similar problem has been found for SHA-0.  However, SHA-0
was known to be flawed early in the process of developing SHA so it was
strengthened to create SHA-1.  Extending the attack on SHA-0 to SHA-1 is
an open question at this time.  

In an unrelated development, an attack has been found on a reduced
version of SHA-1 using half the usual number of rounds.  Again, it is
not certain whether the attack is useful on the full version.  SHA-1
should still be good for now.

What does this mean in general?  Well, it depends on what you use MD5 or
SHA-1 for.  If, all you need to do is check to see if a file transfered
from one location to another intact, there probably isn't a rush to to
drop MD5 for SHA-1.  If your application depends on using MD5 as a
one-way encryption for passwords, then you probably should start
thinking about migrating to SHA-1. If your application depends on using
MD5 or SHA-0 to create keys and initialization vectors for symmetric
security, then you might want to worry about possible future discoveries
that might reveal a bias.  If as a part of your application, you make
the claim that you can prove a specific level of security based on the
collision avoidance properties of MD5 or SHA-0, then you have a lot more
to be concerned about.

It should also be mentioned that "broken" in terms of Cryptography is a
bit different from how we think about computer security in general.
"Broken" in this case means that there exists a known algorithm that
makes it easier than a brute force attack to violate one or more of the
desired properties for a good hash algorithm.  It DOES NOT mean that a
practical exploit exists for MD5 that permits one to slip a trojan into
downloaded files or crack a password file.  There are easier ways to
plant a trojan than to create an identical MD5 hash, or crack a password
file than to try to break preimage resistance.  

> Perhaps it would be appropriate to add a note, warning or "See also"
> to the library documentation for the md5 and sha modules?

I think that it would be a very good idea for MD5.  With SHA, I'm less
certain about wording however.  From what I've been reading on this, SHA
seems to be safe for now.

-- 
Kirk Job-Sluder
"The square-jawed homunculi of Tommy Hilfinger ads make every day an
existential holocaust."  --Scary Go Round