26

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?

CodesInChaos
  • 106,488
  • 23
  • 218
  • 262
Mohamad
  • 34,731
  • 32
  • 140
  • 219

5 Answers5

37

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

Zippit
  • 1,673
  • 1
  • 11
  • 11
12
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?

Ian
  • 4,421
  • 1
  • 20
  • 17
  • 3
    The purpose of salting is to defeat a dictionary attack. Instead of creating a dictionary of hashed passwords and then simply looking for matches all over the place, you force the attacker to recompute all the hashes for each unique salt. This way, the password database is even allowed to fall into the wrong hands, and it's OK because the adversary has a computationally infeasible problem to solve. – Ian Aug 25 '10 at 13:21
  • Ian, does the salt have to be hashed too? – Mohamad Aug 25 '10 at 13:21
  • 2
    @Mel: Since the salt is generally a bunch of random bits, hashing it makes no sense. – jpalecek Aug 25 '10 at 13:33
  • 2
    Hashing isn't reversible and you need to know the actual salt value, so no, don't hash it. The purpose of the salt is to render rainbow table attacks harmless. It needs to be different per user to make generating a new rainbow table less valuable. It doesn't need to be secret to accomplish this -- but if it's secret or a little hidden, then it will make it a little harder to generate the table. For example, the real salt could be f(salt) where f() is in your code somewhere. – Lou Franco Aug 25 '10 at 13:36
  • @Lou Franco: actually, the purpose of the hash is avoiding the same cleartext hashing always the same (so two users with the same password would have the same hashed password and an attacker could have precomputed hashes for common passwords). Rainbow tables appeared much later. – ninjalj Oct 23 '10 at 09:01
  • 1
    @Mohamad, you include the salt in the input to the hash function, every time you call the hash function. However, you store the salt separately as well, in an un-hashed format, so that you have some chance of testing the password. Basically the "salt" exists to turn a single hash function into a multitude of hash functions. So you have to remember exactly which hash function was used with a given password (which is why you store the salt in plaintext) but you don't want to use the same hash function for multiple passwords (which is why the salt is random). – Ian May 31 '12 at 06:05
4

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).

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
4

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.

Ralph
  • 31,584
  • 38
  • 145
  • 282
1

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.

sbi
  • 219,715
  • 46
  • 258
  • 445