[sclug] MD5 is compromised

[Will Dickson]

Roland Turner (SCLUG) wrote:
> Will Dickson wrote:
> 
> Interesting; this is newer information than I had received. It is
> certainly a step closer to MD5's being rendered useless for cryptographic
> purposes than what had been mentioned 24 hours earlier. That it was done
> so promptly suggests a big step, but we are yet to see whether this is so.
> (Roughly, if the speed with which the updated clash was derived indicates
> that the researchers have come up with a general-purpose clash generator
> for MD5 then it's a huge step; if they merely did something akin to
> correcting the endian-ness of their inputs to match the correction in the
> endian-ness of the IV, then the speed of release of the new clash is not
> so impressive. I've not yet seen enough information to determine this
> either way.)

Me neither for sure, but if I understand their announcement 
correctly they claim the latter.

http://eprint.iacr.org/2004/199.pdf for the announcement.

> 
> - In the very narrow sense that a single known clash exists, 

At least two, these are demonstrated in the paper referenced 
above.

> 
> - When/if the observed fact switches from "here is one known clash" to
> "here is a general purpose technique for generating clashing pairs" then
> MD5 becomes useless in many cryptographic applications.

Indeed. See above!

> 
> - When/if the observed fact switches from "here is one known clash" to
> "here is a general purpose technique for generating large numbers of
> clashes with the hash for an existing message" (i.e. the ability to trojan
> downloads, forge transactions, ...) then MD5 becomes useless in
> essentially all cryptographic applications.

AIUI this hasn't happened *yet*. OTOH I certainly wouldn't 
want to bet anything on how long it might take before it does.

You might find this thread informative (it's from the IETF 
SAAG [Security Area Advisory Group] list archive, and is 
more authorititive than me :-).

http://jis.mit.edu/pipermail/saag/2004q3/000913.html

> 
> It still is. Any "best current practice" that mandates suspending
> MD5-dependent applications immediately (before the end of today) until MD5
> can be replaced with something else is not a sound practice, it is an
> academic fantasy. 

Surely dependent on context. If the context makes certain 
assumptions about the security properties of the algorithm 
which have now been shown to be false, the system in 
question is broken; in this situation it may be more 
cost-effective to pull the plug now, and take whatever 
short-term hit that implies, than to keep it up and risk the 
longer-term consequences of a forgery being introduced in 
the meantime. Eg. if you guarantee the trustworthiness of 
the service you provide, the choice may be between losing N 
days' revenue now, or the risk of getting bankrupted by 
consequential-loss lawsuits further down the line.

OTOH any business for which this applies, which is still 
using MD5 at all, is probably too incompetent to appreciate 
this argument. So it goes...

This is probably the first time that an algorithm which is 
as massively deployed as MD5 has been broken this badly. In 
several places it's used in well-nigh universal protocols 
which don't include mechanisms to replace it; eg. BGP, 
apparently, and POP3 for sure. (The POP3 use is in an 
optional authentication mode which isn't used very much, so 
this example isn't too bad.)  Previous advances have mostly 
been incremental combinations of cryptanalysis (slicing off 
a few key bits wrt. exhaustive search) and Moore's Law 
making practical exhaustive searches that were infeasible 
when the algorithm was introduced. (Eg. DES was brought down 
more by faster cracking machines than it was by any 
cryptanalytic break.)

Here's hoping this attack doesn't get SHA-1.