Typically passwords are saved in databases using one way encryption such as md5. In other words if my password is “hello”, the database stores my password as “5d41402abc4b2a76b9719d911017c592″. Each time a user attempts to log in, the md5 algorithm is applied to the provided password and if the result matches the hash stored in the database then access is granted to the user such as in the following
if (md5($_POST['pwd']) == $saved_hash)
// user is logged in
// user password was incorrect
Saving this encrypted password is more secure than saving plain text passwords because if a database is temporarily compromised, at least the attacker will not have access to user’s passwords. However, despite not being able to unencrypt the password (remember this is one-way encryption), the intruder might still be able to crack many of your user’s passwords through precomputation.
An attacker could go through the dictionary (or any set of possible passwords) precomputing the md5 hashes. So, if the attacker were to see that my hash was “5d41402abc4b2a76b9719d911017c592″, he would just look it up in his reverse database and see that this hash maps to “hello”. There are many such reverse lookup databases on the web. This one successfully cracks the mentioned password.
The use of salts greatly decreases the effectiveness of a precomputation attack. A salt is a random string appended to the password before encryption. Typically each user would receive a unique salt.
$saved_hash = md5($pwd . $salt);
Let’s examine the implications when the salt is public (stored in the compromised database) as opposed to when the salt is private:
- Public Salt – The attackers reverse lookup table (commonly known as a rainbow table) will no longer be useful. He will need to generate a rainbow table for the specific user’s salt. While this is still very possible, the attacker will need to perform this operation for each user, which will make it a very challenging process to crack a large number of passwords
- Private Salt – For the attacker to actually compromise a password, he would need to compute the md5 of each possible password appended to each possible salt. If your salts were 32 bits long the attacker would need to compute 800 trillion hashes or so for the English dictionary to be covered. This would be practically impossible.
Therefore, public salts are better than no salts, but private salts are much better than public salts. So, how does one keep their salt private? You can’t store it in your database because all this assumes your database was compromised. My suggestion is to create a salt based on the md5 of immutable data related to that user (and be very careful to not delete/modify that piece of data). For example, the user’s registration timestamp could be used. As long as your attacker was unable to also steal your application code the salt would be safe. This works out as the following:
$salt = md5($registration_timestamp);
$saved_hash = md5($password . $salt);