Given that you check that a password is not a common password and not present in a db with compromised passwords, will password complexity requirements (e.g. at least 1 lowercase and 1 uppercase character and 1 special character) reduce security by reducing the search space without any benefits?

Note: Assume that passwords are hashed using bcrypt with a cost around 14-16.


Wanted to post my own reasoning in the question as I have given this some thought and the reason I am posting this as a question is to check my reasoning. For all I know this answer might get downvoted :) .

I mean, the general argument - as I understand it - is that password complexity requirements require the user to choose a password from a greater 'space', thus decreasing the chances of picking an unsafe password as a lot of unsafe passwords are only lowercase alpha (though clearly not all, such as Password1!).

When something like haveibeenpawned is checked that is an improved check removing the large majority of the "unsafe password"-space. Instead of considering all lowercase alpha passwords unsafe, it instead uses actual data to determine which passwords are or are not unsafe (the set of compromised passwords is assumed to be extremely similar to unsafe passwords). Combining both complexity rules with a compromised password database check thus primarily eliminates the 'secure' part of the lowercase alpha space, blocking safe passwords which are caught by password complexity rules such as passphrases (e.g. catwindowlightpencil).

enter image description here

The above figure doesn't encompass all passwords, it instead compares the passwords password complexity rules are blocking with the passwords you wish to block. The unsafe password set is the one you wish to block, the compromised password set is a subset you can block, the lowercase alpha set is the one you block with password complexity rules.

Note: Obviously new 'dumb' passwords can be 'created'. For example, a new pop idol might become popular during the past week or Microsoft might buy Github, but not yet show up in a compromised password database. Similarly someone might use a product name as a password of a product that has not been compromised yet.

  • Should not the union be labelled 'dumb' passwords, and the right hand set be labelled something like 'large namespace passwords'? – Monica Apologists Get Out Jun 6 '18 at 15:50
  • 1
    @Adonalsium No, absolutely not, because Password1! is an extremely dumb password (thousands and thousands of compromised cases), but is not part of the typically blocked passwords. The point of the graphic is to point out that blocking lowercase alpha passwords doesn't achieve the goal you wish to achieve. It blocks passwords you don't want to block (mycrazypassphrasetoiletbomb) and it doesn't block passwords you want to block (Password1!). – David Mulder Jun 6 '18 at 17:05
  • @Adonalsium updated for added clarity. – David Mulder Jun 6 '18 at 17:17
  • But half the graph is about namespace and the other half is about quality of passwords – Monica Apologists Get Out Jun 6 '18 at 18:13
  • 1
    @Adonalsium They are both sets of passwords. One set is defined by 'quality', the other by characters used. The point is to show that 'characters used' is a bad proxy for 'quality'. – David Mulder Jun 6 '18 at 19:32

Will it reduce the search space?

Yes, but only an extremely small fraction of it will be eliminated: let's assume we consider k characters, of which 26 characters are lower case. Let us consider a password of n characters. The fraction of the search space that is being overlooked by rejecting lower case passwords would then be (26/k)^n.

For n=8 (which in most cases is the minimal length) and k=128 (which is the number of ASCII characters*), this results in a 2.9*10^-6 fraction of the search space.

Will it reduce security?

No, it will not, because the search space is virtually unaltered. The complexity of your password is still O(k^n).

*admitted, not all of them are suited for typing in a password, but most of them are

  • Well, it eliminates passphrases, which humans are biased to and are incredibly safe when used properly, without any of the major disadvantages of password managers (single point of failure primarily). – David Mulder Jun 7 '18 at 12:51
  • And that's the other thing, passphrases are long. – David Mulder Jun 7 '18 at 12:57
  • What you say is right, but your question was if it reduces security by reducing the search space; to that question, the answer is 'No, it is not noticeably easier to bruteforce a password that has complexity requirements'. But I agree the 'complexity requirements' could/should also take length into account (in some 'OR'-construction). Or checking to known weak passwords is interesting as well! – aaphond Jun 7 '18 at 13:06
  • I agree, if the password requirements are disabled given sufficient length that kind of solves the main issue I see with them. Anyway, my main question is mostly about the interaction between a known weak password check and such password requirements. Like yes, statistically only a small fraction gets removed, but do you get any actual benefit by removing that small fraction given a known weak password check? – David Mulder Jun 7 '18 at 13:30
  • Well, yes; the benefit is there for people who: 1. Only use lower case, 2. Use a short password, AND 3. Use an 'unknown' password. Such as 'nkxlebtl'. – aaphond Jun 8 '18 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.