Password hashing and salting

Question

I'm trying to wrap my head around the logic of encrypting passwords with MD5/SHA combined with salting.

I understand the concept of a user proving a text password, and appending a random string (salt) to the text password, and hashing the final string via whatever encryption method you want.

This is where I lose the concept

Say in my database of users, I have usernames, and encrypted passwords generated with the random salt value

When the user goes to log into a system, and they enter their password, how do I obtain the correct salt to check the password validity?

If the salt is randomly generated to begin with, I can't recalculate it

Do I have to store the salt with the username/password record? If I query the database for the salt value by username, it would seem that defeats the purpose of having the salting.

How do I obtain the correct salt when it comes time to validate the supplied password?

Answer 1

From Wikipedia, Salt (cryptography)

A new salt is randomly generated for each password. In a typical setting, the salt and the password are concatenated and processed with a cryptographic hash function, and the resulting output (but not the original password) is stored with the salt in a database

You store it with the hash, to prevent dictionary attacks.

Answer 2

The salt is stored in the database, so you can use the same salt to verify the password. Todays libraries often will include the salt in the resulting hash-value like this (result of the PHP function password_hash()):

$2y$10$nOUIs5kJ7naTuTFkBy1veuK0kSxUFXfuaOKdOKf9xYT0KKIGSJwFa
 |  |  |                     |
 |  |  |                     hash-value = K0kSxUFXfuaOKdOKf9xYT0KKIGSJwFa
 |  |  |
 |  |  salt = nOUIs5kJ7naTuTFkBy1veu (22 characters)
 |  |
 |  cost-factor = 10 = 2^10 iterations
 |
 hash-algorithm = 2y = BCrypt

This 60 character string can be stored into a single field in the database. The verifying function can extract the salt from this string. The salt is not a secret, it fulfills its purpose even when it is known.

Please note that algorithms like MD5 and SHA-* are not appropriate to hash passwords, because they are too fast. Instead use an algorithm with a cost factor like BCrypt or PBKDF2. For more information you can have a look at my tutorial about safely storing passwords.

Answer 3

Yes, you store the salt. Salting is used to prevent pregenerated rainbow tables, it is not required to be secret, just unpredictable.