Salting passwords 101

Could someone please help me understand how salting works?

So far I understand the following:

1. Validate password
2. Generate a random string
3. Hash the password and the random string and concat them, then store them in the password field...

How do we store the salt, or know what it is when a user logs in? Do we store it in its own field? If we don't, how does the application figure out what the salt is? And if we do store it, doesn't it defeat the whole purpose?开发者_运维百科

Salt is combined with the password before hashing. the password and salt clear values are concatenated and the resulting string is hashed. this guarantees that even if two people were to have the same password you would have different resulting hashes. (also makes attacks known as dictionary attacks using rainbow tables much more difficult).

The salt is then stored in original/clear format along with the hash result. Then later, when you want to verify the password you would do the original process again. Combine the salt from the record with the password the user provided, hash the result, compare the hash.

You probably already know this. but it's important to remember. the salt must be generated randomly each time. It must be different for each protected hash. Often times the RNG is used to generate the salt.

So..for example:
user-password: "mypassword"
random salt: "abcdefg12345"
resulting-cleartext: "mypassword:abcdefg12345" (how you combine them is up to you. as long as you use the same combination format every time).
hash the resulting cleartext: "somestandardlengthhashbasedonalgorithm"

In your database now you would store the hash and salt used. I've seen it two ways:

method 1:
field1 - salt = "abcdefg12345"
field2 - password_hash = "somestandardlengthhashbasedonalgorithm"

method 2:
field1 - password_hash = "abcdefg12345:somestandardlengthhashbasedonalgorithm"

In either case you have to load the salt and password hash out of your database and redo the hash for comparison

salt <- random
hash <- hash(password + salt)
store hash:salt

Later

input password
look up hash:salt
hash(password+salt)
compare with stored hash

Got it?

How do we store the salt, or know what it is when a user logs in? Do we store it in its own field?

Yes.

And if we do store it, doesn't it defeat the whole purpose?

No. The purpose of a salt is not being secret, but merely to prevent an attacker from amortizing the cost of computing rainbow tables over all sites in the world (not salt) or all users in your site (single salt used for all users).

According to Practical Cryptography (Neils Ferguson and Bruce Schneier), you should use salted, stretched hashes for maximum security.

x[0] := 0
x[i] := h(x[i-1] || p || s)  for i = 1, ..., r
K := x[r]

where
   h is the hash (SHA-1, SHA-256, etc.)
   K is the generated hashed password
   p is the plaintext password
   r is the number of rounds
   s is the randomly generated salt
   || is the concatenation operator

The salt value is a random number that is stored with the encrypted password. It does not need to remain secret.

Stretching is the act of performing the hash multiple times to make it computationally more difficult for a attacker to test many permutations of passwords. r should be chosen so that the computation takes about 200-1000ms on the user's computer. r may need to be increased as computers get faster.

If you're using a well-known hashing algorithm, someone could have a list of a lot of possible passwords already hashed using that algorithm and compare the items from that list with a hashed password they want to crack (dictionary attack).
If you "salt" all passwords before hashing them, these dictionaries are useless, because they'd have to be created using your salt.