Subject: Re: SHA-1 broken

From: [email-masked] ("Hal Finney")
Date: Thu, 17 Feb 2005 16:49:27 -0800 (PST)

I have a little different perspective on the new attacks, which I will
throw into the mix.  Of course everything is still very mmuch uncertain
and up in the air and we are all digesting the information.

Many people are saying, this is nothing to worry about, 2^69 is still
plenty strong, and there is no reason to stop using SHA-1.  I am not
comfortable with this.  2^69 is in a gray area.  It's not small enough
to say we absolutely have to stop using it, but it's not big enough
to say that the hash is basically as strong as before.

A reduction in strength by a factor of 2048 is the difference between
1 day and 5 years.  It's the difference between 1 month and 170 years.
Depending on how much money you have to spend, this could definitely
make the difference between a practical and an impractical attack.
And remember that the birthday attack of 2^80 also requires 2^80 memory,
which would probably dominate the costs.  We don't know the details
of the new attack but I haven't seen any indication that it requires
enormous amounts of memory.

This makes me feel pretty uncomfortable sticking with SHA-1, especially
when we do have a replacement hash that NIST (which is backed by the
NSA in these issues) was already encouraging people to transition to,
the SHA-2 family: SHA-256, SHA-384 and SHA-512.  These hashes are newer,
and they were designed with an eye to experience with SHA-1 and its
related hashes, MD5 and MD4.  They are intended to provide much greater
strength: 128 to 256 bits, compared to 80 bits for SHA-1.

This leads to another claim I'm seeing a lot of, which is that SHA-256
is just about the same as SHA-1 and will probably be just as unsafe.
I don't agree that we are in a position to make this conclusion.  MD4, MD5
and SHA-1 are a very similar family of hash functions, each one adding
a few twists and extensions to the one before.  SHA-2 is not nearly
so similar.  I don't think anyone who has studied or implemented these
functions would disagree with the claim that SHA-1 is much closer to MD5
than it is to SHA-256.  This suggests to me that you can't generalize
from the older hash functions to SHA-2.

Now, it's true that in its broad structure, SHA-2 does share commonalities
with the others.  It is basically an unbalanced feistel network structure.
But it handles the nonlinearities differently, it updates two words
each round, one in the middle and one at the end, using two sources of
nonlinearities, it mixes the bits up much more with rotates, it avoids
the use of the 16 round block structure of MD4, MD5 and SHA-1, and there
are many more differences.

We can also look at the fact that in a way, the attack just barely works
against SHA-1.  As I said, it puts us in a gray area.  SHA-1 almost
retained its full designed strength against the attack.  The additional
complexity in SHA-2 should give us even more confidence.  And SHA-2, with
a minimum strength of 128 bits, has a much greater margin against attacks.
If we took 11 bits off SHA-2 it wouldn't matter a bit.  We could lose
30 bits and it wouldn't matter.

Some people are concerned that SHA-2 hasn't received enough attention.
But don't get the impression that this is some little-known hash function
which has suddenly found itself thrust into the limelight.  These hashes
have been around for four years.  The are being put forward by the most
powerful and prominent source of cryptographic standards in the world.
People haven't ignored SHA-2.  If there is a dearth of published
attacks, it's not because nobody paid attention.  Finding a flaw in the
new standard hash algorithm of the United States government would be a
major accomplishment for a cryptographer.

Now, I'm not arguing here that we should drop all support for SHA-1 and
switch over to SHA-2.  But in my opinion, given the information presently
available, SHA-2 is a better choice for a hash function than SHA-1.
I wanted to give my reasoning because I'm seeing people promoting the
alternative views that SHA-1 is just fine and/or that SHA-2 is no better.
I don't think SHA-1 is just fine and I do think that SHA-2 is better.
Where we go with that is still open for discussion.

Hal Finney

---

From: Werner Koch <[email-masked]>
Date: Fri, 18 Feb 2005 13:02:31 +0100

> Where we go with that is still open for discussion.

I agree with your reasoning. 

We should however not kick out SHA-1 from all places where it is now
used and replace it by SHA-256 before we understand the new attack.
If we recall the DES development, the NSA knew techniques which got
invented in open research only years later.  Hopefully that is the
case with SHA-2 too.

Shalom-Salam,

   Werner

---

From: Ingo Luetkebohle <[email-masked]>
Date: Fri, 18 Feb 2005 13:26:55 +0100

> used and replace it by SHA-256 before we understand the new attack.

Hmm, maybe this is stupid and it is definetely more effort
computationally, but what about using several hashing methods
simultaneously, mandating that all hashes have to check out?

regards

-- 
Ingo

---

From: Ian G <[email-masked]>
Date: Fri, 18 Feb 2005 13:35:05 +0000

>simultaneously, mandating that all hashes have to check out?

Scientifically, it's very hard to show that that
is an improvement in and of itself.  If the two
(or more) hashes are similar, there is no real
expectation that their security is improved.
For example, MD5 and SHA-1 are both attacked
by the same techniques, so combining them
isn't going to give any definitive advantage.

And, if one of the hashes is much stronger,
then just use that.  I.e., if we were to use both
SHA-2 and SHA-1 then in almost all circumstances,
the security of SHA-2 would dominate that of
SHA-1, so there is little point in using the latter.

Also, there is one bad side:  complexity.  The
addition of complexity is always a 'bad' as it
introduces the possibility of wierd effects.
Think of it this way, if the algorithm delivers
TRUE if (n-1) of n hashes deliver TRUE, then
we have the possibility of implementation
bugs that muck up the checking in some way
and returning TRUE on 0.

iang

PS: there is a new cryptosystem called ciphire
(sp?) that does precisely that:  it uses two
algorithms everywhere, in different ways.
Looks great on paper now, but what happens
in 3 years time when they have to replace
half the algorithms?

-- 
News and views on what matters in finance+crypto:
        http://financialcryptography.com/