Is SHA-1 secure for password storage?

Question

Conclusion: SHA-1 is as safe as anything against preimage attacks, however it is easy to compute, which means it is easier to mount a bruteforce or dictionary attack. (The same is true for successors like SHA-256.) Depending on the circumstances, a hash function which was designed to be computationally expensive (such as bcrypt) might be a better choice.

---

Some people throw around remarks like "SHA-1 is broken" a lot, so I'm trying to understand what exactly that means. Let's assume I have a database of SHA-1 password hashes, and an attacker whith a state of the art SHA-1 breaking algorithm and a botnet with 100,000 machines gets access to it. (Having control over 100k home computers would mean they can do about 10^15 operations per second.) How much time would they need to

1. find out the password of any one user?
2. find out the password of a given user?
3. find out the password of all users?
4. find a way to log in as one of the users?
5. find a way to log in as a specific user?

How does that change if the passwords are salted? Does the method of salting (prefix, postfix, both, or something more complicated like xor-ing) matter?

Here is my current understanding, after some googling. Please correct in the answers if I misunderstood something.

• If there is no salt, a rainbow attack will immediately find all passwords (except extremely long ones).
• If there is a sufficiently long random salt, the most effective way to find out the passwords is a brute force or dictionary attack. Neither collision nor preimage attacks are any help in finding out the actual password, so cryptographic attacks against SHA-1 are no help here. It doesn't even matter much what algorithm is used - one could even use MD5 or MD4 and the passwords would be just as safe (there is a slight difference because computing a SHA-1 hash is slower).
• To evaluate how safe "just as safe" is, let's assume that a single sha1 run takes 1000 operations and passwords contain uppercase, lowercase and digits (that is, 60 characters). That means the attacker can test 10¹⁵*60*60*24 / 1000 ~= 10¹⁷ potential password a day. For a brute force attack, that would mean testing all passwords up to 9 characters in 3 hours, up to 10 characters in a week, up to 11 characters in a year. (It takes 60 times as much for every additional character.) A dictionary attack is much, much faster (even an attacker with a single computer could pull it off in hours), but only finds weak passwords.
• To log in as a user, the attacker does not need to find out the exact password; it is enough to find a string that results in the same hash. This is called a first preimage attack. As far as I could find, there are no preimage attacks against SHA-1. (A bruteforce attack would take 2¹⁶⁰ operations, which means our theoretical attacker would need 10³⁰ years to pull it off. Limits of theoretical possibility are around 2⁶⁰ operations, at which the attack would take a few years.) There are preimage attacks against reduced versions of SHA-1 with negligible effect (for the reduced SHA-1 which uses 44 steps instead of 80, attack time is down from 2¹⁶⁰ operations to 2¹⁵⁷). There are collision attacks against SHA-1 which are well within theoretical possibility (the best I found brings the time down from 2⁸⁰ to 2⁵²), but those are useless against password hashes, even without salting.

In short, storing passwords with SHA-1 seems perfectly safe. Did I miss something?

Update: Marcelo pointed out an article which mentions a second preimage attack in 2¹⁰⁶ operations. (Edit: As Thomas explains, this attack is a hypothetical construct which does not apply to real-life scenarios.) I still don't see how this spells danger for the use of SHA-1 as a key derivation function, though. Are there generally good reasons to think that a collision attack or a second preimage attack can be eventually turned into a first preimage attack?

Answer 1

The previous answers don't make any mention of GPUs, which can parallellise SHA-1 hashing to the extent that an entire database can now be brute forced in minutes or hours rather than days or weeks, even if the passwords have been salted.

Modern password hash algorithms such as bcrypt or scrypt are designed specifically to be difficult to run on GPUs due to the fact that they are block ciphers with much higher memory requirements (and memory access in a GPU can not be parallellised to the same extent). They also have a "work function" which allows them to be made slower on the fly as technology improves.

In short, you should only use the best tools for the job. And SHA-1 falls very far short of the state of the art.

For further reading:

• https://crypto.stackexchange.com/questions/400/why-cant-one-implement-bcrypt-in-cuda
• http://codahale.com/how-to-safely-store-a-password/
• http://www.codinghorror.com/blog/2012/04/speed-hashing.html
• https://security.stackexchange.com/questions/4781/do-any-security-experts-recommend-bcrypt-for-password-storage/6415#6415

Answer 2

SHA1 is a message digest, it was never meant to be password-hashing (or key-derivation) function. (Although it could be used as a building block for a KDF, such as in PBKDF2 with HMAC-SHA1.)

A password-hashing function should defend against dictionary attacks and rainbow tables. A good password hashing scheme should also prevent an attacker from gaining an advantage by using a GPU, a FPGA or an ASIC. Several algorithms have been designed to achieve these goals.

Currently, the best choice is probably Argon2. This family of password hashing functions won the Password Hashing Competition in 2015.

If Argon2 is not available, other choices include scrypt and the older bcrypt. Lastly, if none of these can be used, PBKDF2, which is an oldish NIST standard, is still a much better option than using a message digest as a password hashing function.

Wikipedia has pages for these functions:

• https://en.wikipedia.org/wiki/Argon2
• https://en.wikipedia.org/wiki/Scrypt
• https://en.wikipedia.org/wiki/Bcrypt
• https://en.wikipedia.org/wiki/PBKDF2

Answer 3

Your description sounds accurate for the current state of the art.

You shouldn't be using a single iteration of any hash function, though: At the very least, you should iterate many times (1000 iterations of the hash increases the attacker's work 1000-fold. It increases your work by the same amount, but you're doing a lot less password hashing than they are).

Ideally, however, you should use an existing password storage primitive, such as those described here.

Answer 4

Serious vulnerabilities have been discovered in SHA-1 that make the search much faster than brute force. It is still largely intractable, but that isn't expected to be the case for too much longer; paranoid programmers favour something from the SHA-2 family.

From this article regarding the original 2005 result:

"It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off."

It's not that the current cryptanalysis makes SHA-1 unsafe, but rather that the crypto community is worried that worse news might be just around the corner. This fear also applies to SHA-2, which exhibits the same flaws as SHA-1, albeit over a much larger search space, hence the ongoing quest for SHA-3.

In short, SHA-1 is safe right now, and probably will be for some time come, but the crypto community is uncomfortable with the prognosis.

Answer 5

If you store the salted password, SHA-1 is fine for practical purposes. SHA-2 is considered more secure, but SHA-1 is not a problem unless you have a reason to be truly paranoid.

Here is what NIST says:

The results presented so far on SHA-1 do not call its security into question. However, due to advances in technology, NIST plans to phase out of SHA-1 in favor of the larger and stronger hash functions (SHA-224, SHA-256, SHA-384 and SHA-512) by 2010.

Answer 6

As of Feb. 2017, SHA-1 should no longer be considered secure. Google has reported success with collision attacks against the full, non-reduced-round SHA-1 (link to report). For Google's announcement, click here.

Edit: As pointed out by others, passwords are not vulnerable to hash collision attacks. However as a general guideline I would not choose SHA-1 for security-related applications. There are better alternatives out there.