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