Understanding Hash Functions and Keeping Passwords Safe | Nettuts+

Understanding Hash Functions and Keeping Passwords Safe | Nettuts+

Problem #2: Rainbow Tables

$password = "easypassword";  
  
// this may be found in a rainbow table  
// because the password contains 2 common words  
echo sha1($password); // 6c94d3b42518febd4ad747801d50a8972022f956  
  
// use bunch of random characters, and it can be longer than this  
$salt = "f#@V)Hu^%Hgfds";  
  
// this will NOT be found in any pre-built rainbow table  
echo sha1($salt . $password); // cd56a16759623378628c0d9336af69b74d9d71a5  

What we basically do is concatenate the “salt” string with the passwords before hashing them. The resulting string obviously will not be on any pre-built rainbow table. But, we’re still not safe just yet! Problem #3: Rainbow Tables (again) Even if a salt was used, this may have been stolen along with the database. All they have to do is generate a new Rainbow Table from scratch, but this time they concatenate the salt to every word that they are putting in the table. For example, in a generic Rainbow Table, “easypassword” may exist. But in this new Rainbow Table, they have “f#@V)Hu^%Hgfdseasypassword” as well. When they run all of the 10 million stolen salted hashes against this table, they will again be able to find some matches. How can this be prevented? We can use a “unique salt” instead, which changes for each user. A candidate for this kind of salt is the user’s id value from the database:

$hash = sha1($user_id . $password);  

This is assuming that a user’s id number never changes, which is typically the case. We may also generate a random string for each user and use that as the unique salt. But we would need to ensure that we store that in the user record somewhere. This method protects us against Rainbow Tables, because now every single password has been salted with a different value. The attacker would have to generate 10 million separate Rainbow Tables, which would be completely impractical.