Insecure to require numbers in passwords?

Question

Earlier, I went to a site that required a number and special character, and it got me thinking – wouldn't that make the password easier to brute force? If you assume most passwords have around 12 characters, wouldn't requiring a number remove about 90% of the possible passwords, making brute force much faster?

Answer 1

It removes a lot of passwords only if you consider that all combinations of 12 letters were possible passwords. In practice, users don't consider random passwords; they want to use passwords with a meaning and there are not many of those.

In other words, what matters is not the number of passwords which fit into the password entry field, but the number of distinct passwords that the user chooses among (the "generation process"). Requiring an extra digit enlarges that space for most users. Users for which the forced digit reduces the space of possible passwords are users who choose really random passwords, and even at 11 letters and 1 digit, these will be strong.

Answer 2

From a purely theoretical standpoint, yes. The set of all strings of a given length will be larger than the set of all strings with any further restriction on them.

But the bank is gambling that the space of passwords that the user would practically choose from is actually much smaller than the set of all possible passwords, and that by mandating a number and special character they are increasing the set of passwords the user will choose from since the user may not have included those restrictions on their own. (All other things equal.)

And while a reasonable percentage of the available passwords will indeed be eliminated by the requirements this doesn't really matter, practically or theoretically, because password strength is measured logarithmically and 90% doesn't change a lot on the logarithmic scale. Assuming that the set of passwords with restrictions is only 90%* of what it could otherwise have been, this is only a difference of about 3.3 bits of information. At a length of 10 total characters and about 72 possibilities per character (52 alphabetic, 10 numbers, and 10 special characters), the set of all possible character strings has about 63 bits of space. So with the restrictions we have 59.7 bits of password space instead of 63 bits. Not a big deal.

(* The OP's 90% estimate is a very large over-estimate for how much the password space is reduced. See these comments or other answers for better approximations of how the password space is actually reduced.)

Answer 3

My answers are "maybe", and "no". If you consider a brute force attempt which covers the complete possible set of passwords:

• if the attacker knows the restriction, then many passwords can be discarded, in one sense this doesn't really make the set smaller, he still has to iterate from " " to "~~~~~~~~~~~9" (for example), it just makes it sparse
• the restriction eliminates the "low hanging fruit", i.e. straight dictionary passwords

So strictly, yes, if you look at ideal bits of entropy per character, but really only maybe. You can find a more empirical analysis of this in NIST SP-800-63-1 (Appendix A).

Correctly calculating permutations with restrictions is tricky. If we assume 96 valid characters:

 96^12      ~= 2^79   ~= 6.13E+23
 96^11 * 10 ~= 2^75.8 ~= 6.38E+22
 (96^11 * 10 )/96^12  ~= 0.104

That ratio indicates a loss of ~89.5% (with a more realist set of 64 characters it's about 85%) -- but that's not the right calculation, that's the number of permutations for a digit in a specific position.

(Aside: I'm disregarding passwords shorter than 12 characters for simplicity as it barely affects the numbers:

96^1 + 96^2 + 96^3 + 96^4 + 96^5 + 96^6 + 96^7 + 96^8 + 96^9 + 96^10 + 96^11
 ~= 6.45E21

which is ~1% of the total: for passwords from 1-12 characters, 12 characters ones account for ~99%. As the character set size gets smaller the ratio increases, it's ~1.5% for 64 set size, it doesn't change much as password length varies in the range [7-16] in either case.)

There are two obvious ways to calculate the correct number of permutations with a digit-required restriction:

1. calculate the permutations for a digit in each place, and sum them
2. calculate the size of the total set, subtract the disallowed ones

Option 1 quickly gets out of hand when you try to form permutations with no overlaps. Option 2 is near trivial (at least for simple cases like "must have at least one digit"):

96^12 - 86^12 ~= 2^78  ~= 4.49E+23
(96^12 - 86^12 ) / 96^12 ~= 0.73

This shows for 12-character passwords chosen from a set of 96 characters you loose ~27% of the total number of permutations with the "at least one digit" restriction. Repeating with a 64 character set for passwords:

( 64^12 - 54^12 ) / 64^12 ~= 87%

So you only loose about 13% in that case.

Requiring digit & punctuation is a little trickier, my calculation (96 chars, length 12, >=1 digit, >=1 punctuation) is 4.46E+23 or ~73% of 96^12, ever so slightly less than the digit case.

Brute force is not "much faster", only ~25% faster, which is quite acceptable given the benefits.

Answer 4

These sorts of rules are sensible mainly as they prevent many weak passwords in practice, and require that you considered using special/numbers symbols when generating your password. Any password like a dictionary word is automatically excluded requiring at least the addition of a number and symbol somewhere in the password. Yes you can still construct weak passwords following the rules, but you have dramatically increased the space to do so.

Let's do some math assuming you were randomly creating an 12 character password that was randomly generated. Let's say you are randomly picking symbols out of a set of symbols of size N; e.g., N=26 if you only allow lowercase letters (also 26 if you only allow uppercase letters); N=52 if you allow both lower and uppercase letters; N=95 if you allow all printable ASCII characters etc. That is there are 26 lowercase letters, 26 uppercase letters, 10 numbers, and 33 other printable ascii symbols.

You can easily find that the number of available passwords is N^12 for an 12-character password (there are N choices for the first letter; N for the second/third/fourth, etc.) so the number is N*N*N*N*N*N*N*N*N*N*N*N = N^12. The entropy of a password relates to the base-2 logarithm of the number of possible passwords (that is lg(N^12)).

Type of password   |  N |   number of 12-char passwords   | Entropy
--------------------------------------------------------------------
number only        | 10 |               1 000 000 000 000 | 39.9
lowercase only     | 26 |          95 428 956 661 682 176 | 56.4 
symbol only        | 33 |       1 667 889 514 952 984 961 | 60.5    
lower+number       | 36 |       4 738 381 338 321 616 896 | 62.0
number+symbol      | 43 |      39 959 630 797 262 576 401 | 65.1
lower+upper        | 52 |     390 877 006 486 250 192 896 | 68.4 
lower+symbol       | 59 |   1 779 197 418 239 532 716 881 | 70.6 
lower+upper+num    | 62 |   3 226 266 762 397 899 821 056 | 71.4 
lower+symbol+num   | 69 |  11 646 329 922 777 311 412 561 | 73.3 
lower+upper+sym    | 85 | 142 241 757 136 172 119 140 625 | 76.9 
lower+upper+num+sym| 95 | 540 360 087 662 636 962 890 625 | 78.8 

Now if you required that you must have at least one lowercase, uppercase, number, and symbol in your 12 character password, that effectively excludes the previous possibilities. Imagine the simplified scenario, where you originally allowed only lowercase passwords, and then decided to require at least one number and one lowercase letter in the passwords (and still forbid symbols/uppercase letters), the number of 12-char passwords would not be 36^12 passwords, but would now be 36^12 - 26^12 - 10^10 passwords - though this only shrinks the effective password space by 2.01 percent. However, the entropy of the password barely changes from 62.04 to 62.01. When brute forcing passwords entropy matters -- a small constant factor like 2% faster time to brute force doesn't matter.

In our case requiring at least one lower+upper+num+sym in our passwords results in:

95^12 - 85^12 - 2*69^12 - 62^12 - 2*59^12 - 52^12 - 43^12 - 2*36^12 - 33^12- 2*26^12 - 10^12
 = 367598836933644823317658 possible passwords

The multiplication by two for some values accounts for how my table only considered lowercase-only cases; also have to consider in uppercase-only. This reduces the entropy from 78.8 bits into only 78.3 bits. Yes it did eliminate 31.9% of possible passwords (and ~26% of it came from requiring a number), but it made a minimal dent into the intrinsic entropy. Now compare that to a scheme where your original password was randomly generated from lowercase letters and symbols. That has an entropy of 62 bits instead of 78.3 bits, meaning its about 65000 times easier to brute force.

Granted its almost always better to just increase password length than increase the size of your symbol set. E.g., a random 17 digit lowercase password has ~80 bits of entropy (e.g., ajctzdtrtenwutuxc) slightly beating a 12-digit password with 95 symbols 4eT5*\'W]";vu which may be harder to remember/type and have some symbols blacklisted.