Newsflash: SHA-1 is broken

[johans]

What is SHA-1 then?

SHA stands for Secure Hash Algorithm. SHA-1 is probably the most widely used such a hash function around at this moment, although there are quite some others. Hash functions calculate a fixed-length value for a certain block of data, such that a any small (accidental) change in the data, also changes the hash value. This result is also called the Message Digest (or checksum value).

Properties of a good, secure hash function included that it should be computationally infeasible to find a message that has a given hash; or to create to messages that have the same hash (known as 'pre-image resistance' and 'strong collision resistance').

Is SHA-1 really broken?

It all depends on your definition of 'broken'. Generally, SHA-1 is still quite usable as a secure hash function, so no it is not broken. However it is a weaker than people had assumed; especially in collision resistance. So now might be a good time to start looking carefully at other hash functions.

So what happened then?

At the recent Eurocrypt 2009 convention, Australian researchers announced that they have found new ways to exploit weaknesses in the collision-resistance of SHA-1. This affects the computational effort that it takes to find (create) two different sets of data that have the same SHA-1 hash value. The MD5 secure hash algorithm suffers from the same kind of weaknesses; even much worse than SHA-1 does.

The theoretical strength of SHA-1 against such attacks was originally given as 80 - meaning that it would take 2^80 computation steps to create an attack (create colliding plain texts that lead to the same hash). This is a brute-force attack (using the Earlier weaknesses have been discovered in SHA-1 and in 2006 experts lowered the practical complexity to 2^63. Researches now announced they have found new attacks that reduce this further to a strength of 2^52.

This means that attacks may now be practical to compute on existing computer clusters - owned by large, well-funded organisations (WFO).

Should I continue to use SHA-1?

SHA-1 is still considered safe to use for most applications. In particular nobody can create a file that has the same hash value as something that you have created. But the issues with MD5 have show that even collision problems can be a serious real-world issue.

Most experts will refer to the guidelines from NIST as the authority in this area. NIST is the institution that tells the US government agencies what kind of crypto algorithms they should be using to protect their Secret and Top Secret information. NIST is also the institution that declared SHA-1 and later SHA-2 a general standard (and also AES). And they are currently working with cryptographers world-wide to come up with an even better successor for hashing: the standard that will become SHA-3.

For years now, NIST has been saying that US agencies must not use SHA-1 after 2010 (that is next year). So that was long before the recent attacks were announced. Most experts and other people who worry about security are following the NIST guidelines.

What are the alternatives?

The replacement standard that NIST has chosen and has been promoting for years now, is SHA-2. Actually this is a set of algorithms, also known as SHA-224, SHA-256, SHA-384 and SHA-512, named after the respective length of the resulting hash value (in bits). In fact there are really only two different algorithms: SHA-256 and SHA-512, while the other two simply truncate the result of SHA-256 or SHA-512 to obtain a shorter hash value.

There is also a European alternative: RIPEMD-160 (or simply RIPE-MD). Just like SHA-1 this produces a 160-bits has value. Use of this hash algorithm is (allegedly) prescribed for some European agencies. There are no known weaknesses for this algorithm, but it has probably seen less research (and less use) than the SHA-1 algorithm.

There are several other alternatives such as Whirlpool; but these are used even less.

Many people are anxious about NIST's SHA-3 contest that should lead to a new hash algorithm standard, that will be usable for decades to come. The candidates for this new standard have been developed and published already, but people have only just started analysing them and poking at holes. It is unlikely that developers will bet on any horse before this race has run a while longer. Eventually this will lead to a new SHA-3 hashing standard - but that announcement isn't expected before 2012.

How do I use these?

This completely depends on the application that you are using. Many modern tools, such as openssl, gnutls and gnupg will have a choice of hash algorithms available. However be aware that the default is often SHA-1 (or maybe even MD5), as this is also the default in many security standard documents.

Where's the catch?

Changing the hash algorithm may cause problems when interacting with other software (especially older software). When you are working with secure data on the internet (e-mail, https, ...), the range of applications that may use your data is generally not something you control and others may start complaining that your crypto 'does not work'.

You also need to keep in mind that SHA-1 is often not used by itself, but in combination with other cryptographic algorithms, such as public-key encryption (e.g. digital signatures). In this case the encryption algorithm and the encapsulating format or protocol will need to be compatible with the hashing algorithm of your choice.

For digital signatures (e.g. PGP) it is good to remember that the original DSA standard only allows for SHA-1 hashes. This was later changed to allow other hashes as well (by the DSA-2 standard). But a 1024-bit DSA key (the default for GPG), can only be used with a 160-bit hash length. This means that if you are using SHA-2 (instead of SHA-1 or RIPEMD), then your hash value will be truncated to 160 bits. Using a DSA-2048 key allows you to use SHA-256 hashes without truncation.

For internet connections using TLS), it should be noted that TLS 1.0 and 1.1 don't include support for SHA-2 ciphers. TLS 1.2 does, but this is very new and not yet supported by openssl stable releases. SHA-2 is usable in the digital signature of X.509 certificates with SSL - but many other (browser) vendors do not support this feature yet either.

What about public-key crypto?

SHA-1 is the default hashing algorithm in OpenPGP when using DSA-1204 keys (the default in GPG) or RSA-1024 (the default in many other applications). SHA-1 is also the default fall-back algorithm for any other type of key.

The developers of GPG have announced that they will be changing the default when generating new keys, from DSA-1024 to RSA-2048. The rationale for switching to a larger key is that 1024 DSA/RSA keys are also on NIST's do not use after 2010-list. And a 2048 bit key combines well with the (theoretical) security offered by SHA-256 hashes.

The switch from DSA to RSA is for more practical reasons. Firstly DSA-2 is a relatively new standard and there is still a lot of software that doesn't support it yet. Secondly, unlike DSA, RSA does not restrict the hash length that is used: for example a RSA-1024 key can be used with a full SHA-512 checksum to create a digital signature. Even though it would be more 'logical' to use comparable cryptographic functions (that is to combine RSA-1024 with SHA-1).

A Debian developer recently urged colleagues to replace all their PGP DSA-1024 keys as well and switch to RSA-2048 with SHA-256 signature hashes.

Academics (and also NIST) are also encouraging the use of elliptic curve cryptography (ECC) for public key crypto. ECC is often faster and can use much smaller key sizes when compared DSA/RSA keys. But ECC has not made its way into many internet standards yet.

Commercial companies that are into digital certificates (selling random bits for profit) are still using SHA-1 or even MD5 for their signatures. This provides better interoperability, which is to many people more important than bullet-proof security.

If you are using a PGP smartcard, then you are stuck with RSA-1024 keys for now. Although the 2.0 version is expected later this year. That one will support RSA-2048 keys.

Many secure application developers seem to be waiting (for each other or for SHA-3) - and nobody is considering dropping support for SHA-1 any time soon - even if they are reconsidering their defaults.

What can I do?

Well, that's up to you really. There is no cause for panic, so there is plenty of time to evaluate your options. And unless you are a developer of security applications or handling top secret data, there's nothing to disturb your slumber.

For developers it is probably a good idea to take a close look at the deployment of SHA-256. Even though there are some small cracks appearing, this is probably the most interesting hash function until SHA-3 will come along in 2012.

For public key cryptography, the conservative choice would be to switch to DSA-2048 or RSA-2048 keys. NIST gives these algorithms another 20 years (through 2030) and they combine well with the mentioned SHA-256 hash.