How to choose a salt for a hash function meant to protect passwords?

Question

I'm a (near complete) beginner, and this is my first foray into encryption - in fact this is probably the first time I use the word.

Here is my question: For a non banking / military, or even commercial, web app, what is the right way to choose a salt for a hash function used for passwords?

I can easily generate a pseudo random salt for each new user, and append that salt to their pw before applying the hash function. But I still need to store the salt so presumably anyone who gets access to the hashed passwords also gets the salts.

Is the benefit of the salt simply to make the pw "more random", and therefore defeat the standard dictionary-based rainbow tables?

Would any of the following be good & practical ideas:

1. Store the salt in a separate db - maybe a separate system, definitely a different host, name, pw, etc.
2. Generate the salt based on a hash of a user name (or first+last name, or sign up date), presumably using a different hash function? Then the salt itself would not be stored in the db - only the data used to compute it would...
3. Store in the db a value which concatenates the hashed pw and the salt, in a non obvious manner (e.g., the salt is 10 random keys, and they are injected inside the hashed pw between letter numbers 1&2, 4&5, 8&9, etc).

As a side question, how easy is it to change a salted hash algorithm when upgrading the software of the website? It feels nightmarish right now.

Answer 1

1. Makes checking the passwords more difficult - not recommended.
2. Better just to generate a random number (64-bit is likely enough).
3. See (in part) SO 1191112. The salt doesn't have to be secret; it just has to be different.

To answer your side question: also stash an algorithm ID (possibly a simple number, possibly a name string) along with the data. As you upgrade, you hash new passwords using the new, preferred algorithm, but you retain the old algorithm until everyone has changed their password and there are no stored passwords using the old algorithm. Again, this does not have to be secret - it just allows you to adapt to changes in the world. Clearly, if the old algorithm is suddenly exposed as worthless, you think about whether it is OK to use the incremental approach. But unless something dramatic like that happens, phasing in the new mechanism works pretty well. Try not to change your algorithm so often that you have three or more on the go at once - though there's no technical reason that the scheme cannot manage it. Also try to design your database so that the hash sizes can grow without causing ructions (so allow room for expansion from 64 to 128 bytes, or from 128 to 256, or ...).

Answer 2

Yes, the salt is just there to prevent rainbow attacks on the hashed passwords. Generally I use a single salt value for all passwords. It's stored in my source code or configuration, so it's not in the database. But it's probably better to use a different salt for each user. That way, two users with the same password will not get the same hash.

You can simply store the salt in the database along with the password. The object of the salt is that you cannot precompute a rainbow table. It would take too much time. More time than simply brute-forcing the password directly. Even if the salt is known, the complete rainbow tables for that salt would have to be generated which is extremely expensive to do. So, it does not matter much if the salt is known.

It does not matter much how you pick your salt as long as you make sure that it's long enough. According to Wikipedia a 12-bit hash (used by old unix passwords) is extremely expensive to defeat but possible. 128-bit (as used by e.g. MD5) is too expensive to defeaut in the foreseeable future.

See also: http://en.wikipedia.org/wiki/Rainbow_table#Defense_against_rainbow_tables