TLDR: We already require two-factor authentication for some users. I'm hashing, salting, and doing things to encourage long passphrases. I'm not interested in the merits of password complexity rules in general. Some of this is required by law, and some of it is required by the customer. My question is fairly narrow: Should I detect leetspeak passwords such as Tr0ub4dor&3 as being a dictionary word, and therefore fail passwords that primarily consist of a single dictionary word (even if leeted).  Multiple word passphrases are always accepted regardless if leeted or not, this is only a question about those who choose to use more traditional short passwords.

I am the lead developer for an upcoming government website which will expose sensitive personal information (criminal history, SSNs, etc. primarily). The website will be consumed by the general public, for doing background checks on employees, etc.

On the backend, I'm storing the passwords hashed with PBKDF2 salted on a per-user basis with very high iterations, so brute force hashing attacks against stronger passwords are not realistic (currently), and the website locks the user out for 10 min after five bad tries, so you can't brute force really that way either.

I'm getting some pushback from my customers/partners about the severity of the password rules I have implemented.

Obviously I want people to use 16-20+ char passphrases, but this is a slow-moving bureaucracy. So in addition to allowing/encouraging those good passwords, I have to allow some shorter "hard" passwords. I'm just trying to limit our exposure.

In particular, the "no dictionary word" requirement is causing people frustration, as I disallow the classic leetspeak passwords such as XKCD's famous Tr0ub4dor&3. (For those curious, I run the proposed password through a leetspeak permutation translator (including dropping the char) and then compare each permutation against a dictionary)

Am I being too severe? I am a big proponent of "Avids rule of usability" -  Security at the expense of usability comes at the expense of security. But in this case, I think it's more an issue of habit/education. I allow diceware/readable passphrase passwords with no restrictions, only the "normal" passwords get stronger requirements. XKCD #936: Short complex password, or long dictionary passphrase?

Should I try to solve this with just better UI help? Should I stick to my guns? The multiple recent high-profile hacks, especially ones that exposed passwords makes me think I'm in the right, but I also don't want to make things stupid for no reason. Since I'm protected from brute force attacks fairly well (I think/hope), is this unnecessary complexity? Or just good defense in depth?

For those that can't grok passphrases or truly random passwords, the "two words plus num/symbols" passwords seem to be both easy enough, and at least harder to hack, if I can get people to read the instructions...

Ideas:


Better password hints/displayed more prominently (too subjective?)
Better strength meter (something based on zxcvbn? - would fail the dictionary words on the client-side rather than after a submit)
Disallow all "short" passwords, force people to use only passphrases, which makes the rules simpler?
"make me a password" button that generates a passphrase for them and makes them copy it into the password fields
Give up and let the leetspeek passwords through?


Heres what I currently have in my password instructions/rules:


16 characters or longer passphrase (unlimited max)

or
At least eight characters
Contain three of the following


UPPERCASE
lowercase
Numbers 0123456789
Symbols !@#$%^&*()_-+=,./<>?;:'"

Not based on a dictionary word
Not your username


Examples of passwords that won't be accepted


Troubador (Single dictionary word)
Troubador&3 (Single dictionary word plus numbers and symbols)
Tr0ub4dor&3 (Based on a single dictionary word)
12345678 (Does not contain 3/4 character types)
abcdefgh (Does not contain 3/4 character types)
ABCDEFGH (Does not contain 3/4 character types)
ABCdefgh (Does not contain 3/4 character types)
ABC@#$%! (Does not contain 3/4 character types)
ab12CD (Too Short)


Examples of passwords that will be accepted (do not use any of these passwords):


correct horse battery staple (Diceware password)
should floating things fashion the mandate (Readable passphrase - link to makemeapassword.org)
GoodPassword4! (multiple words, upper, lower, numbers, symbols)
Yyqlzka6IAGMyoZPAGpP (random string using uppercase, lowercase, and numbers)


The mistake here would be to believe that extra password rules increase security. They do not. They increase user annoyance; and they make users choose passwords that are harder to memorize. For some weird psychological reason, most people believe that a password with non-letter symbols is "more secure" in some ontological way than a password with only letters. However, this is fully unsubstantiated.

There is one "password rule" that is not harmful to security: a minimum password length. This is because of the combination of two things:


The most stupid brute force attacks enumerate all sequences of symbols, starting with sequences of 1, then 2, and so on. In that sense, a password that contains only 4 symbols can be said to be irremediably weak.
Users understand that notion of enumerating all small passwords. They are ready to accept that they need to type at least 6 or 7 letters.


All the other rules will be, at best, neutral, but most of them will in fact decrease security, because they will induce users to:


design and share with each other "methods" for generating passwords that your server will accept, methods which usually have a lot of punctuation characters but very little entropy;
write down their passwords, which are hard to memorize;
reuse passwords on other systems, for the same reason of difficult memorization.


"Password strength meters" are also harmful, because:


They are not, and cannot be, reliable. A password strength meter only measures how long a given password would stand against the exact brute force strategy incarnated by the meter code, but no attacker is constrained to follow the exact same strategy.
Password strength meters cannot measure the entropy that prevailed in the password selection, since they only see the result (the password itself).
They turn password selection into a game that encourages witty strategies on the part of the user, and wit is exactly what we do not want for passwords. Secure passwords strive on randomness.


What can help a lot is to provide a password generation system. Take care to make that system optional: you want users to willingly use it, not to force it upon them, lest they would rebel (and write down passwords, and share, and reuse).



So my recommendation would be:


Reject passwords shorter than 7 characters (since you have a mitigation system against online attacks -- namely the autolock for 10 minutes after 5 wrong tries -- you can tolerate relatively short passwords). BUT NO OTHER RULE. Any sequence of 7 or more characters is fine.
Provide one or, even better, several optional password generation mechanisms, e.g. diceware, the "correct horse" thing, and so on.
Encourage the use of password managers.
If possible, try to find something else than passwords for authenticating users.


My assertion is that you are pushing things in a somewhat skewed direction, not exactly the right one. In particular, password rules that insist on some specific characters are a bad thing (a common thing, but a bad thing nonetheless).
