How long should passwords be?

There's a lot of advice thrown around about what the actual password requirements should be, but most organizations do not stop to consider what the goals of those requirements are.  In this post, I throw some numbers around to determine minimum password lengths for different security requirements and hashing algorithms.  The minimum lengths can get a bit silly, but this is why we need to use strong password hashes and should use two-factor authentication when practical.

The first consideration is whether the organization wants to prevent offline cracking attempts or just online attacks. Online password guessing is easier to stop. With even a short temporary lockout (five seconds is sufficient), the passwords do not need to be that strong: five characters with a reasonable complexity requirement should be sufficient. With a 5 second lockout, you can guess 17,280 passwords per day per user. At that rate, it would take 145 years to exhaust the password space assuming five character, mixed-case, alphanumeric passwords.

Note: For simplicity, I will assume we're requiring mixed-case alphanumeric passwords throughout this post.

Offline cracking is hard to prevent, especially when you're using an unsalted, un-stretched hash such as plain MD5.  Windows uses MD4.  Most websites seem to use MD5 or SHA-1 (e.g. Linked In).  For Windows MD4 hashes, GPU-based password crackers can guess 20 billion passwords per second.  MD5 is only about 30% slower and SHA-1 a bit slower than that.  In case anyone is confused, MD5 is not the same as the MD5 Crypt used in FreeBSD.  MD5 Crypt uses salting and stretching and is much harder to break (although it's no longer recommended). 

Not only is offline cracking faster per user, but it scales across all users if you are not using password salts.  For online cracking, an attacker may be able to simultaneously attacker several accounts, but not thousands or millions of accounts.  If our desire is to minimize the number of account compromises rather than prevent access to a single account, then we need to increase the minimum password length to compensate.

To outlast an offline attack, a randomly chosen Windows password needs to be 11 characters or longer.  It would take an attacker over 80 years to guess all possible 11 character passwords. (Note: I explain the math here.)  But with 1,000 users being attacked simultaneously, the attacker will find a new password once a month on average. Moving from 11 characters to 12, pushes the time between passwords to about 5 years. Of course, this assumes that passwords are selected randomly.  If the password selection is less than random (and it will be), then the passwords probably need to be 13 to 14 characters or longer to achieve the same margin and even then the worst passwords will still be cracked quickly.  In a larger organization with more users (10,000 to 100,000), the password requirement needs to be at least one character longer because of scaling (14-15+ characters).  
If requiring users to pick passwords that are 15 characters or longer sounds ridiculous, then you need to pick a better hash.  With Windows, you're basically screwed since the OS doesn't give you another option.  If you're using a recent Unix/Linux distributions, you should be able to use bcrypt.   Scrypt is also available for many systems although it is not installed on any system by default (as far as I know).

If you're developing/maintaining/securing a web application, you can use bcrypt, scrypt, or PBKDF2.  Don't try to code them yourself, you'll probably screw it up and use non-random salts or something like that.  And definitely do not try to invent your own scheme.  Use what's available; bcrypt is probably the most widely available. 

Getting back to password length, how long do passwords need to be if we use a strong password hashing algorithm?

Bcrypt uses a 128-bit salt and a cost value that determines how slow the algorithm runs.    Additionally, GPU-based password cracking may be difficult/not currently possible against bcrypt (oclHashcat-plus does not support bcrypt).  In most cases, an attacker won't be able to make more than a few ten thousands of guesses per second.  With a higher cost value, this could be much lower.  Assuming bcrypt is tuned to allow 20,000 hashes/second, a random seven-character password may be sufficient.  If you tune it to 1,000 hashes/second or less, then a six character password would suffice.  I wouldn't pick a password that short, but it gives some idea of the difference between bcrypt and plain MD4, MD5, or SHA-1.

With MD5crypt, which is native to FreeBSD and supported on Linux, the hash uses a 40-bit salt and is about 2000 times slower than the Windows hash, but hundreds of times faster than what I assumed for bcrypt. Unlike with bcrypt, MD5crypt can be attacked using GPU password cracking. The top benchmark posted on the oclHashcat-plus site is 3.7M guesses/second.  Unfortunately, MD5crypt can not be tuned to increase the cost.  To provide at least the same margin as the bcrypt example above, MD5crypt passwords should be 9 characters or longer.

The old standby advice to use 8 character passwords actually makes sense if we're talking about preventing online guessing attacks or offline attacks against a strong hash such as bcrypt, scrypt, or PBKDF2.  8 character passwords provide a decent margin of security in those situations assuming the selection is not too predictable.  If we're talking about Windows password hashes or a web application using MD5, it makes no sense at all.  To prevent offline guessing attacks with those algorithms, you need to require 15 character passwords or longer which is a support nightmare.

Some will suggest pass phrases, but I don't think that's the answer.  Pass phrases (with a sentence or related words) aren't random enough; we just haven't put a lot of effort into developing guessing strategies for them yet.  Picking 4-5 random words is much better, but I wonder about the actual randomness we'd see in people's choices and how memorable these word combinations would be.  I think they seem easier at first, but that's because they are very different from typical 6-10 character passwords.  If people started using random-word pass phrases for all of their accounts, would they  have trouble remembering which words they used in which password?  Will they mix up the word order?  If you like picking passwords this way, go for it.  It is strong, I'm just not sure it's a general solution.  And remember, "Harry Potter wizard Hogwarts" is not four random words.

Using strong password hashing algorithms is a good start.  I'd also love to see more two-factor authentication.  And less SQL injection.

Edit: I added a couple of links into the post for people curious about how I came up with some of these figures.  For my note on password math, go here.