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.
- User 'monroe' runs the passwd program and chooses the password 'HorseStapler+5'
- 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.
- 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'.
- 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.
- The system runs the hash algorithm on the new string SHA512('HorseStapler+5BohpaS.aul0Qua/t') and gets the hashtext output 'IVUen1dSKZ634jM.KLQ1Am/WPh..DSO2MYI53qffac2IFzESKwIufyVjzQGlxNenOXGehMTCdSoL9DLPe6Zfm1'
- 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:
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.
- Next time user monroe logs in to the system, he submits the password 'HorseStapler+5'.
- 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 '$'.
- 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. They used to store the encrypted password (and a 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.