“It always seems impossible until it’s done.” – Nelson Mandela
Researchers at Google and the CWI Institute in Amsterdam recently announced that they had successfully found a SHA-1 collision. In other words, they found two messages that produce the same output when run through the SHA-1 hash algorithm. This is a significant break of this aging but widely used algorithm, which has practical security implications for everything from security protocols such as TLS and SSH, to the security of passwords, and even the integrity of document repositories.
Organizations that haven’t already heeded warnings of SHA-1’s weaknesses should begin moving away from SHA-1 in earnest.
What exactly did the researchers manage to do?
The researchers demonstrated a way to find two input messages that would produce the same output from SHA-1 or a collision. There are an infinite number of message pairs that produce collisions, but it’s supposed to be nearly impossible to find them.
To fully appreciate the accomplishment, consider that SHA-1 algorithm produces 160 bit outputs. Thus, there are 2^160 possible outputs. Finding a collision is expected to require approximately 2^80 messages. The researchers managed to find a collision in approximately 2^63 calculations; more than a 100,000x reduction in effort!
Thus, it’s now practical to find collisions in SHA-1. Cryptographers generally consider a hash algorithm “broken” when a technique for efficiently finding collisions is demonstrated.
Was this a Surprise?
The cryptographic community has expected SHA-1 to break for several years. The first research demonstrating flaws in SHA-1 appeared in 2005. Various researchers improved it over the past decade. The latest advancement was published in 2013.
Over the past 12 years, there has been a slow but steady move away from SHA-1. NIST deprecated SHA-1 for government use in 2011. The CABForum (the group that sets standards for public CA’s) no longer allows members to issue certificates that use SHA-1 signatures.
Unfortunately, removing a widely-used algorithm takes time. Some older systems may not support more secure hash algorithms, such as SHA-256. Converting existing enterprise CAs from SHA-1 to SHA-256 is also not always straightforward. As a result, SHA-1 is still in widespread, though diminishing, use.
Where is SHA-1 used and what is the impact of SHAttered?
SHA-1 is used in security protocols (e.g. TLS, IPSec, SSH), secure password storage, document identification, and other places.
TLS and IPSec optionally use SHA-1 primarily in two places: certificates and message digests. Similarly, SSH can use SHA-1 as a message digest. Certificate authorities are supposed to place a random value in each certificate. Because of the way this particular attack works, that random value should offer protection. However, someone could potentially enhance this attack, or a CA could neglect to include a sufficiently random value, which would allow them to attack certificates. For these reasons, browsers are continuing or accelerating their efforts to deprecate SHA-1 signed certificates.
Message digests are used to help ensure data transmitted through TLS, IPSec, or SSH is not changed en route. Fortunately, these protocols do not use raw SHA-1 for message digests. Instead, they use a construct called HMAC, which among other things uses the hash algorithm twice. To date, there has been no feasible attack against HMAC-SHA-1. However, this is not an excuse to keep using it. TLS, IPSec, and SSH all support more secure alternatives (e.g. HMAC-SHA256 or HMAC-SHA384). Use these wherever possible.
Hashes are also used to securely store passwords. One of the key properties of a hash is that it is easy to calculate the hash from data, but given a hash it is difficult to find an input that would produce that hash. (This is another aspect of collision resistance.) It is common security practice to store hashes of passwords rather than passwords themselves. This way, it’s easy to verify that users have provided a correct password, but difficult for an attacker who obtains the hashes to discover the passwords. Fortunately, this particular attack requires knowledge of the plaintext and a fairly reasonable length of data. Neither is likely to be true of passwords, but again one ought not to be complacent. Attacks always improve.
How likely is SHAttered to affect me?
SHAttered itself is unlikely to find widespread use anytime soon. The calculations required are too expensive. In the past, this would have put it beyond the capabilities of anyone except nation-states. Now, a well-funded attacker could use the same cloud infrastructures Google did to launch this attack. In any case, if this attack is used in the wild it will be against high-value targets in very special circumstances. What this attack demonstrates is that organizations need to begin moving away from SHA-1.
What does this mean for my organization?
Unless you’ve been very proactive, there is probably still some SHA-1 used within your organization. Here are some common ones to look for SHA-1:
This list isn’t comprehensive, so be diligent in searching for any hidden uses of SHA-1. Keep in mind that not everywhere that uses SHA-1 is impacted. Using SHA-1 for non-security purposes, such as bucketing values in a list (e.g. building a hash table) may be safe. You will need to carefully consider the security implications of each use.
- TLS/IPSec certificates – replace any certificate that uses SHA-1 with one that uses SHA-256 or SHA-384.
Be sure to review your root CA certificates! These are often long-lived and may have been generated before the defaults were switched to SHA-256/SHA-384.
- TLS/IPSec/SSH ciphersuites – consider disabling cipher suites that use SHA-1 (generally ones ending in SHA) and replacing them with cipher suites that use SHA-256/SHA-384.
- Stored password hashes – work with your vendors or internal teams to move to SHA256 or SHA384.