Is SHA-1 secure for password storage?

Question

The short answer to your question is: SHA-1 is as secure as you can get. MD5 would be fine too, even MD4; but it could make some investors nervous. For public relations, it is best to use a "better" hash function, e.g. SHA-256, even if you truncate its output to 160 or 128 bits (to save on storage cost). Some of the SHA-3 round-2 candidates appear to be faster than SHA-1 while being arguably "more secure"; yet they are still a bit new, so sticking to SHA-256 or SHA-512 would be a safer route right now. It would make you look professional and cautious, which is good.

Note that "as secure as you can get" is not the same as "perfectly safe". See below for rather lengthy explanations.

About known attacks:

The known attacks on MD4, MD5 and SHA-1 are about collisions, which do not impact preimage resistance. It has been shown that MD4 has a few weaknesses which can be (only theoretically) exploited when trying to break HMAC/MD4, but this does not apply to your problem. The 2¹⁰⁶ second preimage attack in the paper by Kesley and Schneier is a generic trade-off which applies only to very long inputs (2⁶⁰ bytes; that's a million terabytes -- notice how 106+60 exceeds 160; that's where you see that the trade-off has nothing magic in it).

The rest of this message assumes that the hash function you use (e.g. SHA-1) is a "black box" with no special property that the attacker may use. That's what you have right now even with the "broken" hash functions MD5 and SHA-1.

About rainbow tables:

The "rainbow attack" is actually cost-sharing of a dictionary or brute force attack. It is a derivative from the time-memory trade-off first described by Hellman in 1980. Assuming that you have N possible passwords (that's the size of your dictionary, or 2ⁿ if you consider brute-forcing a hash function with an output of n bits), there is a time-sharing attack in which you precompute the N hashed passwords and store them in a big table. If you sort the hash outputs, you can get your password in a single lookup. A rainbow table is a smart way to store that table with a much reduced space. You store only N/t hashed passwords, and you crack passwords with O(t²) lookups. Rainbow tables allow you to virtually handle precomputed tables much larger than what you can realistically store.

However, rainbow or not, the attacker still has to run the full attack at least once. This can be viewed as several successive optimization layers:

1. The brute-force / dictionary attack has cost N for cracking each password.
2. With a pre-computed table, the attacker pays that cost N once and can thereafter attack many passwords with very small extra cost per password.
3. If the pre-computed table is a rainbow table, then N can be somewhat bigger, because storage cost is reduced. The bottleneck on N becomes the CPU power that the attacker can muster, not the size of his harddisks.

If N is large enough that the CPU-cost of hashing N passwords is ludicrous, then such an attack is not feasible, regardless of whether rainbow tables are used or not. This means that a (preimage-resistant) hash function with an output of 80 bits or more is enough to make brute-force attack infeasible.

About salts:

Salts are a way to defeat pre-computations. In the description above, the salt brings back the attacker to step 1: salting prevents the attacker from sharing the O(N) cost between several attacked passwords. Pre-computed tables, a fortiori rainbow tables, are no longer feasible.

You want salting because when the hashed data consists in passwords, i.e. something which fits within the brain of a random human being, then N can be quite low: humans are really bad at choosing and remembering passwords. This is what "dictionary attacks" are about: that's using a reduced space of potential passwords (the "dictionary") under the assumption that many user passwords will be in that specially selected space.

Hence salting will at least prevent the attacker from using pre-computed tables, in particular pre-computed rainbow tables. This assumes that the attacker will be able to break one password or two; we do not want him to break 1000 other passwords with little extra overhead.

Also, salting is good for public relations.

About SHA-1 cost:

The elementary cost of SHA-1 is about hashing a 64-byte block. That's how SHA-1 works: data is padded, then split into 64-byte blocks. The cost of processing a single block is about 500 clock cycles on an Intel Core2 system, and that's for a single core. MD5 and MD4 are faster, count about 400 and 250 cycles, respectively. Do not forget that most modern CPU have several cores, so multiply accordingly.

Some salting schemes prescribe huge salts; e.g. what enters the hash function is actually 40000 successive copies of a single 128-bit salt, followed by the password itself. This makes password hashing more expensive (by a factor of 10000 with my example), both for the legitimate user and for the attacker. Whether this is a good idea depends on the setup. For login on a desktop system, this is good: the user will not even notice that it took 10ms to hash his password, instead of 1µs; but the cost for the attacker has risen by a very noticeable factor 10000. On shared servers with thousands of clients per second, the aggregate cost may become prohibitive. Conceptually, raising the bar by the same factor for the legitimate user and the attacker is not ultimately good security; but it can be a worthwhile idea in some specific situations.

About online attacks:

All of the above is about defeating offline attacks. An offline attack is an attack where the attacker has all the data he needs in order to "test" passwords; e.g. the attacker could get a copy of the database holding the hashed passwords. In an offline attack, the attacker is limited only by his computational resources. Conversely, an online attack is an attack where each guess by the attacker must go through an honest verifier (e.g. the attacker simply tries to log in on the attacked system). Online attacks are thwarted by enforcing limits on how many passwords can be tried per second. Extreme examples are smartcards which shut down after three wrong PINs.

Usually, for password security, it pays off much more to arrange the system for not letting an attacker build an offline attack. That's what Unix systems do: the hashed passwords, which used to be in the world-readable /etc/password file, are now in the /etc/shadow file which is protected against read access, except by a few privileged applications. The assumption here is that if the attacker can read /etc/shadow, then he probably has enough control over the system that he does not really need passwords anymore...

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

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.

SHA1 is a message digest, it was never meant to be password-hashing (or key-derivation) function. (Although it could be used 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. Several algorithms have been designed to achieve this goal.

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, the only other standardized password-hashing or key-derivation function is PBKDF2, which is an oldish NIST standard. Other choices, if using a standard is not required, include bcrypt and the scrypt.

Wikipedia has pages for these functions:

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

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.

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.