Comprehensive information about hash salts

Question

There are a lot of questions about salts and best practices, however most of them simply answer very specific questions about them. I have several questions which feed into one another.

Assuming a database is compromised a per user salt prevents the use of generic rainbow tables to crack passwords. A separate rainbow table would have to be generated for each and every user who had a unique salt in order to obtain their password. This would be a time consuming process which is what makes salts effective. This does not help a tremendous amount against dictionary or brute force attacks.

This leads to a number of questions:

1. Although a salt is not meant to be security through obscurity wouldn't it still be more secure to place salts in a separate table? That way even if the 'users' table was to become compromised the salts would not.
2. Would having a 2nd hard-coded application wide salt add a tremendous amount of security? This way even if the database is compromised, the actual application would also have to be compromised or both the salts and hashes would be completely useless.
3. What is the best length for a salt? Obviously the longer the better, however with larger numbers of users database size does become an issue, so what would be the minimum length for an effective salt be?
4. Is using a 3rd party source for a "true random salt" (random.org, random.irb.hr) really needed? I understand using a salt based off of server time is "guessable" to some extent however taking a random sub-string of a sha1'd random string seems like an effective salt method.

Thank you in advance.

Answer 1

1. No. Using salts correctly will multiply the time it takes for an attacker to crack all the passwords in your database by a factor of millions. Putting salts in another table will add 30 seconds to the time it takes for an attacker to get the salts too.

2. Yes. It is not a bad idea to use both a global key and a per-user salt.

3. A salt is, or should be, a cryptographic key. Make it long and random. Database size is not an issue. The salt, like any cryptographic key, can be 128 bits or 16 bytes (32 bytes when stored in hex format).

4. Your computer should have cryptographically strong pseudo-RNG. Check the security or crypto APIs for your language.

Answer 2

1. If a hacker has access to your database system, you're fsckd. Your system has to have access to both tables to run, so the likelihood of "hiding" one from a hacker who's already compromised the system is nearly zero. Not remotely worth the extra complexity, in my opinion.

2. Having a "nonce" added (in addition) to a salt for each password is not a great help, but doesn't really hurt anything either.

3. Even 16 bits of salt is typically enough to make password cracking infeasible, if done correctly. I would probably use 64 or 128 bits, why not?

4. You should use a "good" source of randomness, but it doesn't need to be perfect. If the random values are somehow visible to an attacker, then they may be able to find a way to predict the next random value, but they would have to do this when the password is created and it would only get them that one password.

In short, you need per-user salt and a good hashing function. MD5 is terrible, and SHA-1 is no longer "good". You should be using a system like bcrypt to force an attacker to spend a considerable fraction of a second on each hash. 0.1s per password check is probably no big deal to you, but it's devastating to any kind of brute-force cracking.

This is required reading for anyone implementing a password security scheme:

http://chargen.matasano.com/chargen/2007/9/7/enough-with-the-rainbow-tables-what-you-need-to-know-about-s.html

Answer 3

Regarding #1, you can probably assume that if the users table is compromised, they probably will also compromise the salt table, even if you protected it better somehow. It would only slow them down a bit, like a speed bump would do.

Regarding #2, a hard coded salt value is often easily reverse-engineer-able via decompilation or runtime memory inspection, even with moderate amounts of code obfuscation. This would only help increase security in the case where your application is strictly hosted and nobody is able to get hold of your compiled application.

Regarding #3: What is the optimal length for a password hash? (SO link) - 16 is good!

Regarding #4, it isn't much more work to implement "more truly" random numbers, depending on the platform you're working with. For example, if you can tradeoff some performance to generate your seed/random number, you can probably breathe easier over how truly random your salt is.

Answer 4

1) No. An attacker will probably dump everything on your system and will find the salts eventually (though this will be annoying).

2) Yes, there is a small benefit-this covers you if another system uses an identical hashing scheme as you, and some of your salts overlap.

3) The only requirement of a salt is that it's unique per user. Length is irrelevant for security-salts are not keys despite widespread confusion. 64 bit random salts will never repeat. You can also use a 32-bit counter, or just use the user IDs if those are unique.

4) The only reason salts even need randomness (if you use random salts) is to ensure uniqueness. This is statistical randomness, not cryptographic randomness (impossibility of guessing). So any random number library will do.