MD5 broken?

[Owen Lewis]

> -----Original Message-----
> From: ukcrypto-admin@chiark.greenend.org.uk
> [mailto:ukcrypto-admin@chiark.greenend.org.uk]On Behalf Of Brian Gladman
> Sent: 19 August 2004 20:30
> To: ukcrypto@chiark.greenend.org.uk
> Subject: Re: MD5 broken?
>
>
> Brian Beesley wrote:
> > On Thursday 19 August 2004 09:47, Owen Lewis wrote:
> >
> >>ISTR that the work of a US team attacking MD5 was discussed here some
> >>months ago.
> >
> >
> > Relatively minor problems with MD5 have been known for a few years.
> > If I read the report correctly, this is new, deeper and much
> more serious
> > than any previous report.
>
> Yes, it is important - in my opinion primarily because it is (or appears
> to be) a new form of attack which has been demonstrated to work on a
> number of different hash functions - specifically MD4, MD5, HAVEL-128
> and RIPEMD.
>
> As far as I can see, the attack does not work against a given hash value
> but two message texts with the same hash value can be found in about an
> hour on an IBM P960. It is not clear whether the attack requires a large
> memory multiprocessor like the P960 or whether it will scale down to a PC.

In the case of a party wishing to substitute a false document in place of a
true one and with the identical secure hash, as Brian B has pointed out, the
problem seems to be rather larger than identifying a collision. Rather one
must manipulate the fake document until, using the same hash mechanism as
was used on the true document, the identical hash is derived. It seems to me
this is altogether an altogether more difficult task and one in which the
discovery of a method of reducing the average time to discovery of one hash
collision to (say) an hour.

Brian B suggests that the approach to this might be by exploiting the large
amount of white present is the average document. It seems to me that, to use
this approach, the hash must be of the document as a graphical image as
opposed to as a text string. To buy on an apple, I'd propose that one should
consider the more restrictive case of deriving a false document that is a
correctly formatted and worded text string but with the text varied from the
true to convey a different and pre-determined meaning. Unless one can do
this, you are likely to have, as Roland P pointed out a very unsuccessful
attempt to substitute a BACS transaction for a snippet of bastardised Hamlet
that produced the identical hash. This simply would be of no use.

In either way, unless one can show that this end can be achieved and to show
that it can be done in a useful time frame, one has no real indication of
the extent by which the assurance offered by secure hashes has been
degraded.

It seems to me that what the paper shows conclusively is that the assurance
offered by a 128 bit hash is less than perfect. However, the assurance in
any transaction between human parties must be less than perfect anyway.
Therefore, for the result to be much more than an academic curiosity, one
would need to show for a transaction of a specified type that the risk
inherent in that translation is increased by some significant amount.

AFAICS, we are not yet even considering work that might yield such a
significant result. This work in simply not (yet) of similar significance to
the demonstration that a cipher key of a given length can be recovered from
a practical number of ciphertexts.

>
> A key issue is whether the attack is limited to 128-bit hash functions
> or whether it has potential against 160-bit hash function such as SHA-1.
> A succesful attack on SHA-1 would be of far greater significance than an
> attack on MD5 since (in my view) most people who are serious about
> security have dropped 128-bit hashes some time ago.  But almost all of
> them moved to SHA-1.
>
> A different attack on SHA-0 has been reported so it seems to be a bad
> year for hash functions.

Where imperfection is discovered, then surely there can be no sound reason
not to migrate to the use of some system that has not yet been shown to be
as imperfect, especially where the cost of such migration is negligible.
This migration surely need not be a stampede but a part of the generational
change in systems. Moreover, there seems no reason to re-process the
substantial number of documents of enduring value that are presently assured
with 128 bit hashes.

Owen