I see a lot of articles on hashing passwords, however many of them skip over an important part of setting up this kind of system: iterations. But first, a quick primer on hashing in general.

Hashing is a cryptographic function that takes variable-length input, and creates a constant-length output. The output is commonly called a hash, or a digest. The most common algorithms are MD5 and SHA1. MD5 creates a 128-bit hash, and SHA1 creates a 160-bit hash. There are also SHA256, SHA384, and SHA512, although 384 is pointless, since it's just the SHA512 with some data discarded. It's computationally unfeasible to find two plaintexts that have the same hash output. Hash functions are used in some common scenarios:

1: Creating a digest of a message to ensure the message was not modified (intentionally or unintentionally). Sometimes this is referred to as a checksum. eDonkey is an example that uses MD4 hashes to identify files (and as files are downloaded, they can be checked to be good by computing the hash).

2: Digital signatures, where the hash is encrypted with a the private key of an asymmetric algorithm (like RSA). This can then be decrypted by anyone with the public key, and checked against the computed digest to ensure that something with the private key did “sign” the message, and that the message contents have not changed.

3: Securely storing passwords. Since a hash is a one-way function, it's impossible to *decrypt* the hash and retain the password. Well designed systems will not store plaintext passwords (otherwise someone who reads the database could get your password and do nasty things as “you”). If you ever use a site that sends your current password back to you if you forgot it, then they most likely have a badly designed system (and you should question the rest of their security).

We're going to focus on the password issue. Attackers can figure out a password by computing the hash themselves for a suspected password, then comparing to the actual value. So, while the hash value might be 160-bits, it certainly doesn't take 2^160 steps to find the right password, since many users use weak passwords.

When hashing a password, it's common to add some random bytes to the password that are unique for the user. This is called a salt, and it ensures that for each user has a different hash, even if the password is the same -- since hash(”password”) will always return the same, but hash(”password” + “randomData”) is going to be different. This means that an attacker must compute a separate hash for each possible password, *per user*. This helps stop an attacker from trying to attack all the users at once, since each additional user requires a complete attack (since there's a salt).

However, lets say that the attacker is going after a specific user. If the user picked an easy password, say 6 alphanumeric chars, the password's strength is ~36 bits (35.7 to be more precise, 5.95 bits per char). This is assuming completely random characters are used, which is hardly ever the case. That's not that much work for a attacker, and we're considering 64-bit security (128-bit keys) to be the “required security” level.

However, suppose instead of calculating one hash per password+salt, we take the hash, and re-hash it n number of times, where n is something between 2^14 and 2^18? Well, now the number of steps required per password goes up that much. The 36-bit password now has an effective strength against brute forcing of 2^50 to 2^54. Essentially, by adding 2^18 steps to the hashing, we've added the equivalent of 3 *random* characters to their password.

So, do you need to iterate? Find out your minimum security level (48-bit? 56-bit?). Figure out how many iterations you can perform on your hardware before performance is unacceptable (probably between 2^14 and 2^18). Subtract that from your required level, and you have the minimum password entropy level.

For instance, let's say that I want to have 64-bit security from my passwords. My hardware can do 2^16 iterations without hurting logon times, thus I need 64-16= 48 bits of entropy in each password. This can be accomplished by requiring passphrases consisting of four common words (say a dictionary of 4000). (12 bits per word = 48 bits in the password + 16 for iterations, and I'm set).

Hashing is even more important when you don't have control of how good the passwords are. For instance, you're saving customer's credit card data, and the key is based off their password (so that they MUST login for your system to access that data). In these cases, requiring a complex password might not work for various reasons such as customer pushback, or risk of customer choosing something like your site name or their name as a password. It's important to determine the level of password complexity that will “push users over the edge” - the point when they stop using something remotely random, and start using things like their last name, their SSN, etc. When that point is reached, the entropy of their password is uselessly low.

Now, assuming a semi-casual attacker with a strength of 40 bits. He's got the power to do 2^40 steps of computational work. If your users use 24-bit passwords, their hashes can be broken by this attacker easily. But, with 2^18 iterations, those weak 24-bit passwords now require 2^42 steps, and the hash is saved.

So, there is really no good reason not to do multiple iterations. Even 1024 will provide some strength (equivalent to 2-3 extra characters in the password). In fact, the .NET framework already has a class that does all of this (hashing with whatever algorith, salting, and iterations) for us: System.Security.Cryptography.PasswordDeriveBytes. Use it!