[p2p-hackers] SHA1 broken?

[Jack Lloyd]

On Wed, Feb 16, 2005 at 05:15:36AM -0800, Paul Campbell wrote:
> On Tue, Feb 15, 2005 at 09:41:05PM -0800, Gordon Mohr (@ Bitzi) wrote:
> > Via Slashdot, as reported by Bruce Schneier:
> > 
> >     http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
> > 
> > Schneier writes:
> > 
> > #   SHA-1 Broken
> 
> I saw this a few months ago. It's not just SHA-1. All ciphers based on the
> MD-5 S-box design are apparently vulnerable. At this point, it appears that
> there are two options for the future:

No, there were no major results against full 80 round SHA-1 until this. There
were collisions with ~50 of the 80 rounds for SHA-1, and Joux found a collision
for SHA-0 around the same time Wang et all produced the collisions for
MD4/MD5/RIPEMD/HAVAL-128 last summer.

BTW, MD5 does not use S-Boxes in any form.

> 1. Go to something with a larger internal state (256-bit state), and that is
> NOT just an extended version of the original (as the extended SHA standards
> attempt to do).

Currently Whirlpool is looking like the best bet. Tiger is still out there, and
is both reasonably fast on 32-bit machines and very fast on 64-bit, but it
never saw much analysis, as the designers expected the 64-bit revolution about
8 years too early.

Both are quite unlike the MDx designs, which is both good (possibly less likely
to fall to whatever methods Wang and crew have), and bad (less analysis has
been done). A major issue is that currently the details of the attacks haven't
been published. All we really have right now are a set of collisions for
various hashes, which proves that there are weaknesses, but until we know the
details there is no way to say that they will or won't apply to
Whirlpool/Tiger/SHA-2/etc.

Fortunately the 2^69 worklimit on SHA-1 is currently theoretical for everyone
but the TLAs, so the paper will have to explain the attack is sufficient detail
to verify the results, from which people more compentent than me can see if the
attacks do (or might) apply to the latest generation of hash functions.

The real key is not just to upgrade, but to provide a smooth upgrade path in
the future. Before SHA-1, the average security lifetime of a hash was about 5
years. I suspect we're seeing a return to that level of cycling; for the most
part analysis of hash functions is not nearly as developed as that for block
ciphers.

> 
> 2. Go to a completely different type of cipher. The choices right now are
> either digital signatures via elliptic curves, or else using one of the

ECDSA and ECNR still use conventional hash functions; you don't reduce the
impact of an attack on SHA-1 by using either of those as compared to DSA or
RSA.

> stream cipher designs.

I am not aware of any methods of hashing with just a stream cipher; are you
refering to Panama? Panama's stream cipher mode is still secure AFAIK, but the
Panama transform has been shown insecure for hashing (IIRC with 2^80
operations, versus the expected 2^128)

Regards,
  Jack