Password salting, hashing, and stretching

Edit:This password utilities library has now been substantially upgraded and open-sourced with an MIT license. You can find a .NET 4.0 version of the library and an example graphical interface in a Google Code Mercurial repository.

This is the fifth installment in a series about creating a C# password utilities library.

The next step is implementation of a password hash policy. Specifically, a policy that covers salting, hashing, and stretching.

A password salt is a set of (usually random) bits that are the secondary input to a one-way hash function - the first input being the password itself. Salting protect you against pre-computed dictionary attacks, otherwise known as rainbow tables. Because a rainbow table is made by straightforward hashing of a large dictionary of words, passwords, and passphrases, it can't be used where every password has been hashed with a different salt.

Orange ExplosionThere's a common misconception that password salts need to be kept secret. This isn't true - the only protection that salting provides is against rainbow tables. Even if every salt is known, it would take far too much space to create a rainbow table covering every combination of password and salt.

Hashing a password involves a one-way function that converts an (optionally salted) password into a fixed-size set of bits. The idea is that you always store the password hashes rather than the passwords themselves. After storing a password hash, you can then verify the associated password, by hashing it and then comparing with the stored hash. The benefit of using password hashes is that because the hashing function is one-way, it's not possible for an attacker to reverse-engineer a password from its hashed value.

One issue with using a cryptographic hashing function such as SHA-1 for password storage is that it's designed to run very fast. Speed is exactly what you don't want in a password hash function, because it means that offline attacks can be executed very fast. Ideally you want to slow down the hashing process from microseconds to as long as 1 second or more. Somebody using a password won't notice a 1-second delay in the login process, but an attacker has no hope of brute-force password cracking if restricted to 1 attempt per second. To slow down the hashing process, we want to use some form of key stretching.

We could stretch the key by simply repeating the hash function multiple times in a loop. Alternatively we could use a hash function that has a slow setup time, for example Blowfish. As we'll see in the next installment, the method I'm going to use involves a key derivation function called PBKDF2, also published as RFC 2898. PBKDF2 has some useful properties: you can use a salt, you can define the hash output size, and you can configure the slowdown factor by specifying the number of iterations over the hash function.

Hash policy implementation

To create the password hash policy, you need to supply the number of required hash bytes, the number of required salt bytes, and the number of times that the hash function should be applied. The minimum hash size allowed in this implementation is 20 bytes (160 bits), because that's the output size of the hash function I'm going to use (HMAC-SHA1). The minimum salt size allowed is 8 bytes (64 bits), as that's the lowest size currently considered to give good protection against attacks using rainbow tables. The minimum number of iterations over the hash function is just 2, but the default policy uses 2^14, which is 16,384 iterations. Note that 2^X iterations increases protection (information entropy) against a brute-force attack by X bits. So the default iteration count of 2^14 is the equivalent of adding two extra characters to the original password.  

You can view and download HashPolicy.cs. The complete library, including this class, will be posted at the end of this series. In the next installment, we'll look at the hash generator class.