Cryptography Engineering: Salting & Stretching

“Salting and Stretching” is just one section of Chapter 21 of Cryptography Engineering, but it’s applicable to web applications, so I thought I’d summarize it here.

Salting and stretching are two techniques for storing secrets. They should always be used, for example when storing passwords in a database.

Salting

A salt is just a random number (256 bits, if possible) that is encrypted with the password. The salt itself is not secret and can be stored alongside the encrypted data.

Salting prevents attackers from pre-computing likely passwords, because the salt adds enough “randomness” to result in a different hash value. Using a different salt for each user also prevents attackers from identifying if two users have the same password.

Stretching

Stretching is the technique of encrypting over many iterations. Here’s how it might look in PHP:

$r = SOME_BIG_NUMBER;
$x[0] = 0;
for ($i = 1; $i <= $r; $i++)
{
  $x[$i] = HashFunction($x[$i-1] . $password . $salt);
}
$K = $x[$r];

The final result $K is then used as the key for encrypting the data. (Obviously there’s no need to store all the values of $x separately; this is just illustrative of the process.)

Stretching adds valuable computation time to the encryption/decryption of data. When a normal user enters his password, the additional time it takes (should be) imperceptible. However, if an attacker is trying to brute-force the key, she has to perform those computations for every password she tries — there is no way to get around it. So if $r = 2²⁰, it basically adds another 20 bits to the key size.

The other nice thing about stretching is that it can scale. Computers get faster over time, so $r can increase over time too. The authors recommend using an $r value that results in an overall addition of 200-1000 milliseconds. And it’s backwards compatible — simply store $r with the data and the system will always know how many iterations to perform. (Of course, you’ll want to update older passwords using the new $r values.)

Putting It Together

In fact, salting and stretching is what bcrypt does, and why it’s constantly recommended by people for storing passwords.

Bcrypt is not included in PHP itself, but there is a library implementation with the somewhat-unfortunate name of phpass that seems easy to use. You can find more info in this StackOverflow answer.