[sclug] MD5 is compromised

[Will Dickson]

Roland Turner (SCLUG) wrote:
> 
> 
> Before anybody panics, the break is that two different plaintexts have
> been found which, when put through an algorithm similar[1] to MD5 generate
> the same hash. A rather large amount of CPU time (measured in years rather
> than trillions of years, which is the real breakthrough here) was required
> to do this. 

Although the full paper has not yet been published, this 
doesn't seem to be the case. There were problems verifying 
the first collision (turned out to be due to the wrong 
endianness on the MD5 IV) at which point they produced a 
revised version, with a different collision, overnight.

Frequently when a hash clash (two different inputs -> same
> output) is found, 

The entire point of a cryptologic hash function such as MD5 
is that it's supposed to be computationally infeasible, ie. 
impossible for all practical purposes, to find even one such 
collision. Obviously they exist, but you're *not* supposed 
to be able to find them. If somebody mananges to find even 
one such collision, the hash is broken. MD5 is now broken.


it is relatively trivial to find "similar" clashes very
> cheaply (the basis of hash-cash in fact);

No. Hashcash works on the basis of *partial* collisions, 
which are known to be creatable with not much work. This 
result is a *full* collision, and that's supposed to be 
computationally infeasible.


> relying on MD5 alone for signing has been viewed as unsafe for
> years; use at least SHA1 or SHA1 and MD5 together.

True. However, it's still not uncommon: until yesterday, the 
best current practice was that MD5 was unsuitable for new 
designs but still OK for backwards compatibility. The 
concern was not so much weakness in the design (although 
that was a factor) as that it wasn't long enough; the 
expected workload to brute-force it was only O(2^64) which 
wasn't enough any more. This is now no longer the case.
> - Raz
> 
> 1: The difference appears to have been accidental; for some reason the
> endianness in the initialisation vector (list of 32 bit numbers used to
> seed the algorithm) was inverted, meaning that the hash algorithm for
> which a clash was discovered is very similar to, but not the same as, MD5.

That bug was corrected. Overnight.

Will.