philosophical: restricting the password space increases security

Question

This is more of a philosophical question.

Suppose that you are trying to choose a good password for a particular online service, say your bank's e-banking service. Now the bank has some restrictions on the passwords that it allows: you can only use (lowercase) letters and (decimal) digits, and the password can be up to 6 characters long. So what is a "good" way to select such a password?

One could do the following (call this scheme 1): select randomly 6 characters from the set [a-z0-9] with uniform probability. This scheme has the disadvantage that it may produce "weak" passwords such as those containing only letters or only digits (there is a 14.2% [1] chance of this happening).

So here's another idea (call this scheme 2): select randomly (and uniformly) one letter, one digit, and 4 characters from the set [a-z0-9]. Then use a random permutation of these 6 characters as the password. This guarantees that the password will have characters from both classes (letters and digits).

So the question is, which of the two scheme produces "better" passwords?

On the one hand, the second scheme produces passwords that will likely be more resilient to simple brute force attacks. On the other hand, the first scheme allows strictly more combinations than the second one: 2^31.0 [2] vs 2^30.8 [3]; in fact the set of passwords of scheme 1 is a superset of those of scheme 2.

Note: I'm looking at this from the perspective of the party that generates the password and not the party that sets the password policy.

[1] (26^6+10^6)/36^6 = 0.142

[2] log2(26^6) = 31.0

[3] log2(36^6-26^6-10^6) = 30.8 i.e. all combinations of 6 characters excluding the ones with only letters (26^6) and the ones with only digits (another 10^6)

Answer 1

tldr; Restricting the password space does not help against brute force attacks, but may against intelligent attacks, but there is an even better way.

First off, you're asking the right question, but using the wrong terminology here:

...the second scheme produces passwords that will likely be more resilient to simple brute force attacks.

(I think you mean intelligent attacks.)

A brute force attack is one that attempts every possible combination without added intelligence. Brute force in your example would be something like:

a, b, c, ... y, z, 0, 1 ... 9,  
aa, ab, ac, ... ay, az, a0, a1 ... a9, ba, bb, bc ... 99,  
aaa ... 999, 
aaaa ... 9999,
aaaaa ... 99999,
aaaaaa ... 999999

Anything other than that would be considered an intelligence strategy. For example, before you try brute force, you may be able to save some time with this strategy:

1. Attempt only numbers.
2. Try words found in a dictionary.
3. Try the top X most popular passwords.
4. Try combinations of the username or user's initials, current year or last year, etc.
5. Try brute force.

Your goal, as the creator of your password, is to make sure that the first 4 options always fail to discover your password. In other words, you need to make sure that the only way to discover your password is by brute force, and also make sure that if brute force is used, that it will take a long time before finding your password. However you do that is up to you, given the constraints of what types of passwords are allowed.

As for your particular question, I would approach it more like a random password generator- it generates one for you, you look at it, and if you believe that it could be guessed with a method other than brute force, you simply generate another random one until you're happy with it. (This would be Scheme 1 with a twist.) If you really wanted to quantify this, you could have your intelligence strategies built and ready to go (all strategies except for brute force). Then you can test them against your randomly generated password and if it is found, you generate another one until all intelligent strategies fail to discover your password. You then would be left with a password which is only discoverable by brute force. Using this method you can achieve better entropy than by restricting the password space in the way you described.

Note: with the password rules you supplied, my twist to Scheme 1 may end up looking somewhat like Scheme 2, however, as the number of allowed characters and password length increases, the Scheme 1 twist should provide more entropy.

Answer 2

I think you have summarized the complexity of the problem nicely, and illustrated why both have pros and cons. The correct answer is of course Scheme 3: Use a longer password, or Scheme 4: Switch to a bank that allows more than 6 character passwords.

You have actually raised an age-old question, which you can find sprinkled around the questions on this site if you browse through the tag passwords: with some (small) probability, a completely random password generator could come up with "password". By putting restrictions on randomness, you are increasing the strength of your worst-case password, at the expense of your entropy. If you can make a good argument for a restriction that does not reduce the entropy significantly, then I think it can be acceptable. Though the general answer is always: if you're worried about the entropy of your password space, use more characters.

Answer 3

answer to title question:

No, under no scenario but one does restricting the password space increase security. The one scenario where it does is when your restriction is the exclusion of known weak passwords, e.g. a blacklist. This is the (2018) recommended way of doing it, by the way. Forget all the complexity nonsense, that was IT securities equivalent to alchemy.

answer to the full-text question:

Your scheme two is actually weaker due to a common human fallacy. You may think that a random generator that can theoretically spit out "aaaaaa" is weaker than one that cannot. However, you are mistaken. Your generator that cannot generate this "weak" output actually has a reduced search space and any attacker who knows the algorithm behind the scheme has a big advantage over the entirely random scheme.

Note that "aaaaaa" might be the first try one a stupid brute-force attack, but the probability is really tiny and easily offset by the fact that the search space is so much larger. In fact, in a scheme that makes it impossible for the generator to create this output, an attacker aware of the scheme would not test for it, either.

"aaaaaa" is actually not a bad password and in any realistic attack scenario is likely to be tested by the attacker long, long after "passwd", "123456" and even all their possible permutations. An actual real-world attacker is much more likely to run or at least start off with a dictionary attack before he uses actual brute-force enumeration.