Is SHA1 Still Viable?

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:

  1. The author carried out a brute force attack in order to find matching input strings for a list of hashes.
  2. All of the hashes were generated with input strings consisting of 6 or less characters.
  3. 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).
  4. 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.

Terminology

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).

Conclusions

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.

Disclaimer

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

10 thoughts on “Is SHA1 Still Viable?

  1. Sha 1 is definitely too weak for new systems. The problem is there is so much legacy that depends on it. By the time sha3 gains widespread adoption, we’ll probably have quantum computers that make it all moot anyway.

    • SHA3 won’t give us more security. Hash algorithms are made to be fast, as their intended use is verifying data, not securely storing password data. Key derivation functions like PBKDF2 and bcrypt are the way to go.

      • Isn’t cranking up the rounds just as effective?

        $start = microtime(true);
        hash('SHA256', 'laskdjfl;j');
        echo microtime(true) - $start; //5.007E-6
        echo "\n";
        $start = microtime(true);
        crypt('laskdjfl;j', '$5$rounds=5000$asldkjflj$');
        echo microtime(true) - $start; //.0045
        

        Is PBKDF2 that much slower than SHA256 (for example) given the same number of iterations?

    • As well, it took 42.6131589413 seconds for it to find a 3 character sha1 without given any information besides the algorithm, encryption, and length of the original (3)

    • Is there any reason why you couldn’t do the same thing for another hashing algorithm? You can defend against brute force attacks by requiring users to provide passwords with 8 or more characters consisting of uppercase and lower case letters and digits. In addition to this you should be applying a long salt to the hash like so:

      $hash = sha1( sha1($password) . '$3b' );
      

      As I pointed out in the post, brute force attacks are an attack on the password, not the hash. Slower hashes can make brute force less viable, but if you are storing your passwords with a salt, carrying out a brute force attack on a password of any length should be infeasible even with fast hashes (provided the attacker does not know how the salt is applied).

      A successful brute force attack does not indicate the hashing algorithm is broken.

      • Where does this story with the hash come from? It’s just not true that salted passwords improve the security against a single brute force attack, as the salts need to be saved WITH the password hashes. Salted hashes are good to secure yourself against rainbow-table based attacks, not brute force attacks. It will only make brute forcing a lot of hashes more difficult.

        Cheers,

        Thomas

        • I never intended to imply that it was foolproof, only that it is an extra layer of security. It’s true that if the attacker had already accessed your user database then they would have all of the salts. But they would also need the code to determine how the salt is applied. In addition to this if you use a global salt for all of the users that is hard coded then without the source code a brute force attack would be infeasible. If the attacker has the salt(s), and knows how it is applied then it is just an annoyance.

  2. Hello, the second paragraph of the original article says: “Update: Because of the huge impact I have clarified some things here” which links to this article where I have clarified several things: https://stacksmashing.net/2010/11/20/cracking-passwords-in-the-cloud-getting-the-facts-straight/

    Quote:

    - 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:

    No, there’s no lack of consistency. I didn’t crack SHA1. I tried to crack SHA1 hashes: “How fast can this instance type be used to crack SHA1 hashes?”. And that’s exactly what I did. I didn’t crack down SHA1. I just brute forced hashes. And that’s exactly what I’m saying in my ‘Getting the facts straight’ follow up.

    • Thomas,

      Thank you for clarifying that, the link on the original article to the clarification post seems to actually point to itself. I have to admit on rereading what I wrote I’m worried I came off as too critical when in fact I think you wrote an excellent article. What I meant when I said lack of consistency was that the word crack was used rather liberally and I think it’s something that may have caused people to misunderstand the scope of what you were doing. This includes the infosecurity article that uses it far more liberally and I think completely misses the overall point. In other words they used your article to claim that SHA1 itself had been cracked when, as you just pointed out, was not at all what you set out to do.

      By the way, great response time. I hit the published button 30 minutes ago.

      -Matt