How does a system authenticate a user using a hash function, after it has been salted?

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.

A Real Example

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.

1. User 'munroe' runs the passwd program and chooses the password 'HorseStapler+5'
2. The passwd program receives the password, checks it (for validity rules), then it determines what algorithm it needs to use for hashing, (DES, MD5, SHA-256, SHA-512) Let's say the system chooses SHA-512 for its hashing algorithm.
3. The SHA-512 algorithm uses a 16 character random string for its salt made up of alphanumeric characters + '.' and '/' . The system generates a random salt string 'BohpaS.aul0Qua/t'.
4. The system now concatenates the salt onto the password like this 'HorseStapler+5BohpaS.aul0Qua/t'. This is the "new" plaintext that will actually be hashed and stored. It makes it more unique so that anyone else using the password 'HorseStapler+5', because of its popularity, will not result in the same hashtext in the password database. It also protects against rainbow table attacks.
5. The system runs the hash algorithm on the new string SHA512('HorseStapler+5BohpaS.aul0Qua/t') and gets the hashtext output 'IVUen1dSKZ634jM.KLQ1Am/WPh..DSO2MYI53qffac2IFzESKwIufyVjzQGlxNenOXGehMTCdSoL9DLPe6Zfm1'
6. So that the system can authenticate the user in the future, it stores the salt as well an indicator for the type of hashing used in the /etc/shadow file as the following string in the second field (encrypted field) for that user's entry like this '$6$BohpaS.aul0Qua/t$IVUen1dSKZ634jM.KLQ1Am/WPh..DSO2MYI53qffac2IFzESKwIufyVjzQGlxNenOXGehMTCdSoL9DLPe6Zfm1'

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.

Re-authentication

1. Next time user munroe logs in to the system, he submits the password 'HorseStapler+5'.
2. The system looks up the user in /etc/shadow and finds the full string above. The system takes the salt part of it (the part in-between the 2nd and 3rd '$') and then concatenates it with the password like above. Then it hashes that using the SHA-512 algorithm as indicated by the algorithm designator '6' in-between the 1st and 2nd '$'.
3. The system then compares the resulting hashtext against the string after the 3rd '$' in the encrypted password field of the shadow file.

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.