Password Complexity Requirements

The issue of password complexity came up at work today so I put together a small spreadsheet detailing how long it would take to crack unsalted passwords of a given length and how many passwords per day or year an attacker could expect to recover in an offline attack.  I assumed that there are 10k users and that an attacker can guess 20 billion passwords per second.  The speed estimate implies that the attacker is using a  GPU-based password crackers such as CryptoHaze or oclHashCat and that the underlying hash is something fast like MD4 (Windows) or MD5 (many websites).  Here's what the numbers look like:

Click so you can read it...

I highlighted the lengths/complexities that would yield less than one password per day for an attacker.  That's a pretty arbitrary requirement, but it seemed like an okay minimum.  Your requirements may vary.

The numbers indicate that passwords should be at least 10-12 characters long (depending on the character set), but they also assume truly random passwords.  Since people do not actually pick random passwords, I'd add at least two to three characters which brings us up to 13-15 characters (again, depending on the character set).  In order to avoid the increased support costs and general discontent that is likely to arise from requiring 15 character passwords, it's probably a much better idea to adopt a stronger password hash and/or two-factor authentication instead.  With scrypt, bcrypt, or PBKDF2 (and reasonable cost values), seven and eight character passwords start to look pretty good again.