bugtraq - Re: MD5 To Be Considered Harmful Someday

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20041208211927.GB5646@randombit.net>
Date: Wed, 8 Dec 2004 14:19:27 -0700
From: Jack Lloyd <lloyd@...dombit.net>
To: bugtraq@...urityfocus.com
Cc: Joel Maslak <jmaslak@...elope.net>
Subject: Re: MD5 To Be Considered Harmful Someday

On Tue, Dec 07, 2004 at 06:46:20PM -0700, Joel Maslak wrote:

> The short-term fix seems to be something I've been recommending for a
> while:
> 
> Compute hashes with both SHA-1 and MD5.
> 
> The chance of one algorithm becoming compromised in the mid-term is
> relatively high IMHO (I was responsible for a PKI system which had to keep
> integrity for 20 year periods of time - not an easy task considering what
> we don't know about the future).  The chance of two becoming compromised
> is relatively less.  The chance of a problem with MD5 and SHA-1 allowing
> two different files to have collisions in both algorithms in *BOTH* is
> very very small.

You might want to read this:
  http://www.mail-archive.com/cryptography@metzdowd.com/msg02611.html

Essentially you can use Joux's attack to generate 2^64 collisions for SHA-1
with about 64*2^80 effort; out of those 2^64 collisions you have an even chance
that at least one of them will also collide in MD5. That's still 2^86 hash
computations, nothing to sneeze at, but nowhere near the expected 2^144
operations. That workfactor might be doable in a 20 year timeframe.

It actually looks like it's better to generate 2^80 MD5 collisions instead of
2^64 SHA-1 collisions, since the initial collisions would be trivial to
generate, and even if MD5 wasn't broken 80*2^64 + 2^80 << 64*2^80 + 2^64. So in
fact you can generate a MD5||SHA collision with only a tiny bit more work than
generating a SHA collision.

So this really doesn't buy you anything.

Jack