I don't really understand how salting works. I read the Wikipedia article, but I still don't understand how can a system authenticate a salted hash?
Let's say a user chooses a password. It's randomly salted and hashed. Now, when that user wants to login again, his password is hashed again and compared with the salted and hashed password saved from the last time. The hashes won't match, will they?
I mean, I guess they DO match in some way. But how?
When you hash the password the first time (when the user registers), you use a salt and store both the salt and the resulting hash in the database.
The second time (when they try to log in again), you use your username to pull the salt and the hash out of the database. You use the salt to hash their password input, and compare the two hashes.
You may be wondering "but if someone gets access to my database, they have all the salts - isn't this a huge problem?". The fact that they have the salts isn't a problem, since the purpose of the salt isn't to add something "secret", it's to ensure that if two users have the same password they have different hashes since the hashes were created with different salts.
If you didn't use salts, or if you used exactly the same salt for every user (unfortunately not an uncommon mistake), there will be a lot of duplicate hashes (since some people will use the same password, and those identical passwords will all have identical hashes). If someone gets access to your database, they can look for the hashes that appear most often, concentrate on cracking those hashes, and for each one they manage to crack they have access to multiple accounts. By salting each hash differently, chances are very high that there won't be any duplicate hashes - the different salts mean that even duplicated passwords will have different hashes. For each hash they crack, they get access to exactly one account - no more. That's the purpose of the salt.
The salt is stored with the hash, for example in a separate database field or it is tagged onto the end of the hash or the username is used as the salt.
The purpose is so that even if two users have the same password, their salts will be different and therefor their hashes will not be the same.
This is useful if someone manages to steal the database, they will have to crack each hash + salt combination separately. So in the case of our two users who share the same password, the attacker will not know they are the same until he cracks them both.
It is also the case that without salts an attacker can per-generate the hashes of common passwords and check them against the stolen database. Salting makes these per-generated rainbow tables useless.
Great answers so far, but something that I think should also be mentioned because its not very clear from the article you referenced. The hashing function is run against the salt concatenated along with the password and then the salt is concatenated again with the resulting hash from the function and that string is what is stored in the password database like /etc/shadow.
This example shows what happens when a user chooses their password on a Unix system, how it gets stored in /etc/shadow and then how the password is checked when the user logs in. I'm going to use real examples instead of variable names or strings like foobar. I'm also going to ignore things like pam to make this a bit simpler.
The full entry in /etc/shadow looks like this:
munroe:$6$BohpaS.aul0Qua/t$IVUen1dSKZ634jM.KLQ1Am/WPh..DSO2MYI53qffac2IFzESKwIufyVjzQGlxNenOXGehMTCdSoL9DLPe6Zfm1:15196:0:99999:7:::
The $6$ part indicates that it was SHA-512 hashed. The part in-between the 2nd and 3rd '$' character store the salt that was used. This field in the shadow file is called the encrypted field. Some people don't like that name because its hashed, not encrypted. Encrypted implies that it can be decrypted, which it cannot. However, I'll refer to it as the encrypted password field.
Hopefully this demonstrates why the hashing algorithm only needs to be a one way algorithm and how exactly the salt is used.
The reason for the shadow file is because the /etc/password file needs to be world readable on a unix system. A long time ago, they used to store the encrypted password (and a very long time ago the cleartext password even) in the 2nd field of the /etc/password file. They moved it to the shadow file and only gave root access to that file and the authentication mechanism needs root privileges to authenticate you.
Well, that ended up being a lot longer than I thought.
The user always submits the actual password to the server and the server stores the salt and hash values. The point of a salt is simply to make sure that if the DB is compromised, an attacker can't try brute forcing all the passwords at once. It also prevents identifying reused passwords.
It doesn't matter if the salt becomes public knowledge because it doesn't reduce the work of the attacker any to know the salt since they still only have to try every password until they get a match. The hashing is done on the server so that the client can not simply return the hash as it is seen in the DB without having to actually know the password.
