Lately whenever I see discussion regarding SHA1 in the context of password hashing or user management it usually involves someone claiming that SHA1 has been ‘cracked’ or is otherwise not viable as a hashing algorithm. I think there is some degree of truth to these claims. In spite of this however, I think that many of these conclusions are based on a misinterpretation of the evidence.
Before I explain myself I want to say this: If you are reading this article because you intend to implement something that require a secure hashing algorithm stop thinking about SHA1. There are a lot of more collision resistant algorithms for you to chose from. You might be thinking that this fact defeats the purpose of discussing the viability of SHA1, but considering all of the existing system that rely on SHA1 I think the discussion is valid. Here we go:
Has SHA1 Been ‘Cracked’?
Here is an article that proclaims SHA-1 crypto protocol cracked using Amazon cloud computing resources. The article details how an IT security researcher used Amazon Web Services to crack a “six-character implementation of the 160-bit SHA-1 crypto algorithm” in 49 minutes at the cost of $2.10 (please take note of the bold text). I think this is a perfect example of how easy it is for someone to draw the wrong conclusions. Here are some quotes from the article:
- The fact that the crack took all of 49 minutes shows that SHA1 for password hashing is deprecated
- Credant’s CTO argues that using Amazon Web Services to crack a 160-bit SHA-1-hashed password extends the hacker ballgame into a whole new cloud computing dimension
- This is, he said, one of the first times that an SHA-1 encrypted password has been cracked using rentable cloud-based computation.
The word ‘crack’ in some form appears 18 times in the article, ‘SHA-1′ appears 8 times, but only once (in the subtitle) does it mention that the ‘crack’ only applies to 6 character or less passwords.
Lets take a look at the original article that the infosecurity-magazine article is based on. In the article the author asks “How fast can this instance type be used to crack SHA1 hashes?” and then shortly thereafter provides the answer: 49 minutes. However, if you read the comments you’ll see that the author wrote the following reply to a commenter:
- Read the article, understand it, and then rethink what you’ve written. I didn’t claim that I cracked SHA1 or anything.
I’m not trying to say that the author contradicted himself, only that there is a definite lack of consistency in terminology. This lack of consistency becomes a blatant disregard for the facts in the highly editorialized infosecurity article. Here are the facts:
- The author carried out a brute force attack in order to find matching input strings for a list of hashes.
- All of the hashes were generated with input strings consisting of 6 or less characters.
- The hashing algorithm used happened to be SHA1, but could have just as easily been any other algorithm (I’ll go further into this in a bit).
- Using the same method as the author on 7+ character strings would take much longer.
The only impact SHA1 has on the time necessary to ‘crack’ these passwords is the amount of time it takes to generate a SHA1 hash relative to other algorithms. Unless an algorithm takes much longer to generate compared to SHA1 it is vulnerable to the same attack. A brute force attack exploits a vulnerability in the password, not the hashing algorithm.
The author concludes the following:
- This just shows one more time that SHA1 for password hashing is deprecated – You really don’t want to use it anymore
Nothing in either article supports this claim, but there is still some truth to it.
Disclaimer: I’m aware that the author is not responsible for what conclusions people draw from what he has written. I think the original article is very interesting and brings to light the issues that inevitably result from the existence of services like EC2. I recommend you read his follow up post where he clarifies several things that people have misunderstood.
Finding the Truth
As I mentioned before, brute force attacks are not an attack on the hash, but on the password. The only impact a hash has on the time necessary to find a matching password using a brute force attack is the amount of time it takes to generate that hash. While it is true that slower hashes are more resistant to brute force, the difference in calculation time is small compared to the increase in time resulting from adding another character to the string.
So if it isn’t the case that brute force attacks make SHA1 obsolete what does?
The answer is collisions attacks. The objective of a collision attack is to find two inputs that yield the same output for a given hash algorithm. I highly recommend you read the Wikipedia article on SHA1 before reading any further.
The question of whether or not SHA1 is viable is really a question of how long it takes to generate collision pairs. Lets begin answering this question by establishing some baselines. The estimated number of hash operations required to perform a brute force search is 280 (roughly 1.2 * 1024). Lets assume that we have a cluster of machine that can generate 230 (roughly 1 trillion) hashes per second. This means it would take 250 seconds, or roughly 35 million years to perform the attack. Clearly this is not feasible.
Now lets consider some attacks that take less than 280 hash operations. One such attack published in 2005 requires 269 operations. Take note that this article proclaims that “SHA-1 has been broken”. At a trillion hashes per second it would take 239 seconds or roughly 17,500 years to find a collision.
This paper describes an algorithm that may lead to an attack that requires 251. This translates to about 24 days to find a collision at a trillion hashes per second. Just for fun lets put that in terms of dollars using Amazon EC2. 24 days @ $2.10 per hour = $1209.60.
So for the low low price of twelve hundred dollars you can derive a password from a SHA1 hash, correct? Actually no. As I mentioned before the goal of a collision attack is to find two inputs that yield the same hash. This is not the same as finding an input that corresponds to a specific hash value (understanding the Birthday Paradox may help you understand why). In order to do this you would need to perform a Preimage Attack.
Here are some quotes from Wikipedia that I think characterize the status of SHA1:
- All currently known practical or almost-practical attacks on MD5 and SHA-1 are collision attacks. In general, a collision attack is easier to mount than a preimage attack.
- Some of the applications that use cryptographic hashes, such as password storage, are only minimally affected by a collision attack
- In order to find an actual collision in the full 80 rounds of the hash function, however, massive amounts of computer time are required. To that end, a collision search for SHA-1 using the distributed computing platform BOINC began August 8, 2007, organized by the Graz University of Technology. The effort was abandoned May 12, 2009 due to lack of progress.
If cracked means that it is possible to carry out a brute force attack on a password hashed with SHA1, provided that the password is no longer than 6 characters then SHA1 has been cracked (but then so has every other hashing algorithm). If cracked means that given any arbitrary hash it is possible to determine an input that yields that specific hash then SHA1 has not been cracked.
If broken means that given a cluster of machines and seventeen thousand years you can find two inputs that yield the same hash then SHA1 is broken. If broken means that given a cluster of machines and a few weeks to a month you can do the same then SHA1 has not been broken (but may soon be).
The system is working. Researchers have found vulnerabilities in SHA1 and as a result it is being phased out. However, those vulnerabilities have not yielded viable attacks. If you are in a situation where you are implementing a new system and need a secure hashing algorithm then there is most likely no good reason for you to use SHA1. If you are considering updating an existing system that currently uses SHA1 then you should consider what kind of attack your system is vulnerable to. For example, SSL is vulnerable to collision attacks, but the passwords in your user database are not.
Based on the information I’ve seen collision attacks may become viable in the near future. That doesn’t appear to be the case for a preimage attack.
I am not an expert in the field of security. If anyone told you I was they’re lying. I encourage you to verify everything I said here. Part of the reason I wrote this is I feel that people have come to the wrong conclusions either based on bad information, or by misinterpreting good information. Feel free to disagree with my conclusions, correct me, or provide me with more up to date information.