The SHA-1 break and its consequences

The SHA-1 break and its consequences

Yesterday news broke that SHA-1 (Secure Hash Algorithm) has allegedly been
broken. This has been reported by, among others, Bruce Schneier
[url]http://www.schneier.com/blog/archives/2005/02/sha1_broken.html .

While the break has not yet been confirmed independently (the paper is new and has had
limited distribution, so far), such a break has been expected for a while, in
particular since MD5 and SHA-0 was broken in a similar manner last year, and
similar results were reported for reduced versions of SHA-1.

SHA-1 is used widely to handle the SSL/TLS protocols and certificates by all
browsers (e.g. Opera, Mozilla, MSIE) that supports those protocols. What does
this mean for these applications?

In the short term nothing will change for clients like Opera, since this
discovery is mostly of interest to cryptographic researchers at this time,
while in the long term SHA-1 (and MD5) will be abandonded in favor of more
modern algorithms, which will lead to the introduction of new cryptographic
metods in clients and servers. Most of this process will be invisible to end
users.

What is SHA-1?

SHA-1 is the second version of the Secure Hash Algorithm developed by the US
Goverment (NIST and NSA) for the Digital Signature Standard, DSS. The first
version, SHA-0, which is no longer in use, was recalled shortly after it was
released because NSA discovered some (undisclosed) weaknesses in the algorithm,
weaknesses which were apparently discovered by independent researchers last
year.

SHA-1 (and MD5) are what is called a cryptographic one-way function, a.k.a. a
digest or hash function (what you get out are the original content chopped into
very small pieces and rearranged so that it is no longer recognizable); you send
in content (e.g a document) as the argument to the function and gets a result
out at the other end. The output result will vary wildly if you change a single
bit in the input. It is also impractical to reverse the calulation and find the
input from the output result.

Both of those aspects (and a couple more) makes such functions ideally suited
for document integrity checks since they will detect changes in the document
when you repeat the calculations to verify a given content, and it is not
practical to create faked (realistic) content with the same output result from
the function. Combined with Public Key Cryptography methods like RSA they are
used to create digital signatures.

What happened?

As I understand it this new break has reduced the work needed to find content
that produces the same result as another piece of content when run through the
SHA-1 function, i.e. they have made it a little more practical (about two thousand times
times) to reverse calculate a result and find a piece of content that will
produce the same output as the original content did. This alternative content
can then be substituted for the original content and it would be impossible to
tell, from the digest result which was the original (whether or not the
replacement makes sense in the actual context is another question). In the
proper context this could then be used for fraud.

The work needed to perform the reverse calculation is still enormous, a single
calculation would still require years to perform even with thousands of
computers doing the work. This break will not magically make it possible to fake
authenticated data, or modify data over a secure connection.

But like a piece of metal that is has started to crack at a weakened spot due to
metal fatigue, SHA-1 will unravel relatively quickly as researchers probe at the
cracks that they can now see (or suspect), until the work needed to complete the
break is neglible.

Consequences

In Opera and other browsers SHA-1 is, among other things, used to verify digital
signatures for secure server certificates, as well as for various tasks in the
SSL/TLS protocols, and the largest impact will be for certificates, which will
now have to start using new hash methods for the digital signatures, and this will
require new root certificates from the CAs as well as some updates in the
clients.

For SSL I do not expect the problem to be too serious for a while, but SSL v3
should probably be retired as soon as the certificates start changing to new
methods, since SSL v3 uses MD5 and SHA-1 directly for a number of essential
tasks. MD5 is also showing severe stress, since it was broken in a similar
manner last year. SSL v2 is only using MD5, but is should be retired for other
reasons as well.

The situation for TLS is far less critical since it does not use MD5 or SHA-1
directly, but is using their output as the input to another oneway/hash function
called HMAC which combines the input with some independent key data so the
weaknesses in SHA-1 (and MD5) arent't that important here.

However, I expect that within a couple of years the IETF will publish new
ciphersuites for TLS 1 or TLS 1.1 that uses new hash methods, such as the modern
SHA-256, SHA-384 and SHA-512 (the numbers are bitlengths) instead of SHA-1.

When these new methods are defined we will implement them, and probably adjust
the security level of the current methods down a notch or two to indicate that
they are not believed to be as secure as the newer methods. At some later point
support for the older methods will be removed as they are phased out of active
use.

Yngve: thanks for the informative summary!

Re: The SHA-1 break and its consequences

However, I expect that within a couple of years the IETF will publish new
ciphersuites for TLS 1 or TLS 1.1 that uses new hash methods, such as the modern
SHA-256, SHA-384 and SHA-512 (the numbers are bitlengths) instead of SHA-1.

The variations of SHA with longer block lengths still use the same transformation functions as SHA-1, don't they? I'm wondering whether or not this break may prove to be catastrophic for the entire SHA familiy after the academic community (and NSA) have had their go at it. If they find a way to make the work factor of creating a collision in SHA-1 negligible, the other SHA versions may in essence be broken as well.

Maybe we're seeing the beginning of the end of the Damgård-Merkle era of cryptographic hashes?

Thanks

Very informative. Thank you.

Very nice, Mr. Pettersen! I'm reading 'Web Services Security' by Mark O'Neill, and he's raised SHA-1 many times so far. Kinda neat to see it in the news.

It appears that Opera 7.54u2 doesn't understand (new) certs which are signed using SHA-512 (with RSA encryption; I can find the OID if that would be helpful): we fed it one, and it choked on it. The error message was something highly vague about
a "transmission error" - I don't have it to hand but I could get it if that would be helpful.

a) Is this true?

b) If so, is / will it be supported in Opera 8? Are there any plans to introduce support for it in the Opera 7 line?

TIA

Will

Do you have a public test server running with a SHA512 dependent certificate?

Many of the errors during the handshake map to transmission error, the number in the title gives a more precise code (mod 256).

At the moment SHA-512 and it's siblings are not available in Opera since they are not supported in the current version (0.9.7) of OpenSSL. AFAICT they have been added in OpenSSL 0.9.8 which is still under development.

fractalgp - sorry, no - it's an internal webmail server. We need it working, so it's about to get its cert replaced with an SHA-1 one.

Yngve - thanks, I suspected this might be the case. Is there a list of (the meanings of) these error codes anywhere?

The error codes (mod 256, some of them have internal additions that are multiples of 256) are the same as those specified in the SSL/TLS specifications.

For those who are interested: Paul Hoffman and Bruce Schneier have published the first version of an Internet-Draft describing the issues around the MD5/SHA-1 breaks with respect to various internet protocols.

You can find the draft (it expires September 26, 2006) here: [url]http://www.ietf.org/internet-drafts/draft-hoffman-hash-attacks-00.txt