Can someone explain how to do password hashing + salting

Question

I've read on SO (and from other websites found on Google after I tried to look into it a little bit more) that the correct secure way to store passwords in a database is to store the hashed + salted value of a password. On top of that, the salt should be different for each user so hackers can't do harm even if they have the encrypted values.

I'm not quite sure what salting means. From my understanding, you hash the password, then you use another value that you hash (the salt) and combine those two together so the algorithm to retrieve the original password is different for every user.

So basically, what I'd have to do is hash a password, then use a different hash on a different value for each user (ie: the user name or email address) and then I can do a simple math operation on those two values to get the encoded password.

Is that correct or did I just not understand anything about password hashing + salting?

A simple explanation or example would prove to be helpful as the sites I've found don't quite explain clearly what salting a password is.

Edit: After reading comments and answers left so far, I understand that I didn't really understand what a salt was because I'm missing some key concepts and I was making false assumption.

What I'd like to know is: how do you consistently get the same salt if it is randomly-generated? If the salt is stored in the database like some people have mentioned, then I can see how you keep getting the same salt, but that brings another question: How does it make the passwords more secure if anyone with access to the database have access to the salt? Couldn't they just append the (known) salt to all the passwords they try and the result would be the same (bar some minor time loss) than not having one at all?

Answer 1

Let me try and clarify a little bit with a somewhat oversimplified example. (md5() is used for example purposes only - you should not use it in practice.)

A salt is just a random string of characters that is appended to the password before it is hashed. Let's say you have the password letmein, and you hash it like this...

 echo md5('letmein')

...you'll get the output 0d107d09f5bbe40cade3de5c71e9e9b7. If you google this, you'll get a number of pages telling you that this is the MD5 hash for letmein. A salt is intended to help prevent this sort of thing.

Let's suppose you have a function, randomStringGenerator() that generates a random $x-character string. To use it to salt a password, you'd do something like this:

 $password = 'letmein';
 $salt = randomStringGenerator(64); //let's pretend this is 747B517C80567D86906CD28443B992209B8EC601A74A2D18E5E80070703C5F49

 $hash = md5($password . $salt);

You'd be then performing md5(letmein747B517C80567D86906CD28443B992209B8EC601A74A2D18E5E80070703C5F49), which returns af7cbbc1eacf780e70344af1a4b16698, which can't be "looked up" as easily as letmein without a salt.

You'd then store BOTH the hash and the salt, and when the user types in their password to log in, you'd repeat the process above and see if the password the user entered with the stored salt appended hashes to the same thing as the stored hash.

However! Since general hashing algorithms like MD5 and SHA2 are so fast, you shouldn't use them for storing passwords. Check out phpass for a PHP implementation of bcrypt.

Hope that helps!

Answer 2

One uses a salt to avoid the attacker creating a rainbow table, e.g. a table containing all (usual) passwords and the corresponding hashes, sorted (or somehow easily accessible) by hash. If the attacker has such a table or can create it, and then gets your password database with unsalted hashes, he can easily look up the passwords, even for all of your users at once.

If the hashes are salted (and the attacker gets the salt with the hashes), he will still be able to do the same attack (with only slightly more work to input the salt) - but now this work of building a rainbow table is useless for the next hash with another salt, which means this will need to be done for each user again. This alone is the goal of the salt. A dictionary attack on your single account still needs the same time as before, just the rainbow table is useless. (To do something against the dictionary attack, see below.)

---

How exactly the salt is used depends on the algorithm in use. Some hash algorithms (for example bcrypt, which is specially made for password hashing) have a special salt input parameter (or generate the salt themselves and include it in the output):

H = bcrypt(password, hardness) or H = bcrypt(salt, password, hardness)

(The first variant generates the salt itself, while the second takes it from the outside. Both include the hash and the hardness parameter in the output.)

Others need to be used in some special mode to use the salt. A simple variant which works for most hash algorithms would be using HMAC, with the salt as "message" input, the password as key:

HMAC(password, salt) = Hash(password ⊕ opad || Hash(ipad ⊕ password || salt) )

where opad and ipad are some constant padding values.

Then you store the salt together with the hash. (For a slightly higher barrier, you could store the hash in another location than the salt. But you will still need both for login.) For login, you then will give the password and the stored salt to your hash function, and compare the result with the stored hash. (Most bcrypt libraries have a "password verification" function build in, which do this.)

---

For password storage it is important to use a slow hash algorithm, not a fast one, to avoid (or really: slow down) brute force or dictionary attacks on the passwords, as most people will have quite short passwords. bcrypt is an algorithm which was made just for this goal (its slowness is adaptable by a parameter).

If you use a fast hash function, be sure to repeat it often enough to be slow again. (But better, really: use bcrypt.)

Answer 3

Although @Chris and @Pualo have very good answers. I wanted to add one more thing about salting passwords that hasn't been expressed.

Salting a password is not a real protection mechanism. It doesn't matter if you are using bcrypt or any other mechanism. It is simply a delaying tactic, nothing more.

By using a different salt value per password you are forcing the hacker to create a rainbow table per password in order to crack them. This increases the amount of time it takes, but by no means does it make it impossible. Bear in mind that with cloud based computing you can spin up a large number of machines to create the rainbow tables and you can see that the delay is pretty small.

Further, most of the zombie machines out there are available for rent...

That said, the reason why you go through the trouble is to buy time. Time to notice that you've been breached, repair it and inform your users of the breach. That's it.

If an attacker obtained enough access to your database to pull the list of passwords, then it is pretty much guaranteed that they've obtained everything else. So, by this point you've already lost everything. The only question is how long does it take you to plug the hole, reset everyone's password and tell them that they should reset the passwords on any other account they may have where they used the same one. If you're Sony, then this time is apparently measured in months, if not years... ;) Try to be a little faster than that.

So, although it is the responsible thing to do it is only one part of your defensive tool belt. If you've been breached then you can bet those usernames and passwords will show up on a site somewhere at some point in the near future. Hopefully before then you've already cleaned up your house.

Answer 4

Using salt prevent precomputed rainbow-tables usage, as an example if a user use "Password" as a password, MD5("Password"), SHA1("Password"), or WhatEver("Password") may be well-known results stored in some rainbow tables. If you use a different salt value per person - called a nonce - you'll get MD5(HMAC("Password","RandomSaltValue")), SHA1("Password","AnotherRandomSaltValue"), ... that mean two different hashed password values for the same initial password. Now the question about storing these salts value...i think they can be stored into the database, the idea of salts are to prevent rainbow-style attack, not the database compromised issue.

Answer 5

Although bcrypt slows the process significantly down, it still would probably be feasible to attack your scheme if lots of computations can be made in parallel. I know it's unlikely and this would have to be a quite resourceful attacker indeed, but let's imagine the site you protect would contain photos and documents from Area 51 :) In that case, given enough parallelization, you could still be in trouble even if using bcrypt.

That's why I like the approach of scrypt - not only does it involve computational cost, but also it imposes memory constraints, specifically to introduce cost in terms of space and to make these kinds of parallel attacks infeasible. I can only recommend reading the paper that is linked on that site, it illustrates the concept really well.

Although, it seems that bcrypt and even more scrypt seem to get less attention in terms of cryptanalysis than PBKDF2outlined in RSA's PKCS#5. See this discussion for details.

Answer 6

What about Secure hash and salt for PHP passwords? It even has examples in PHP.

Answer 7

I'd say first of all that security is very hard to do right, and that you really should rely on existing libraries to do as much as possible for you. For basic operations like password storage and validation that's definitely true.

EDIT: Removed erroneous info. I'll stick with the only good advice I had, which was not to roll your own.