Doesn't adding requirements to a password, such as must contain 2 digits, decrease the strength? [duplicate]

Doesn't any constraints added to a password policy increase the ease of guessing the password (since a constraints shortens the domain of possible passwords)? For example a password must be at least 10 characters - attacker knows not to bother with passwords shorter than 10 characters. Passwords must have 2 numbers - attacker knows to only check passwords with 2 numbers. It certainly is common for policies to enforce users to have a mixture of characters and a minimum, why is this? Does it have to do with the has functions; for example if a string contains a mixture of letters and digits are collisions less likely or is the hash value harder to reverse engineer?

marked as duplicate by AviD♦Dec 23 '12 at 11:38

I think you may have missed a subtle part of the policy:

• You must have a minimum length.
• You must have a minimum number of letters.
• You must have a minimum number of numbers.

From a purely statistical perspective, let's look at the possible reduction in keyspace. My apologies if it's a bit hard to follow, but you'll understand my reasons for it as you get towards the end.

First, we'll look at the possible lengths for a password. In theory, your possible lengths fit into the set ℤ+, i.e. all positive integers. This set is uncountable, i.e. infinite in length. As such, any set with bounds {n→∞} is always uncountable, as long as n<∞. So for any non-infinite length password your length requirement will not change the number of possible lengths. Let's define a function ƒL that gives us the length of any arbitrary password, for further use.

Next, let's look at the numbers of letters and numbers. Since the domain of our function ƒL is at most {1→∞}, and at least {n→∞} for n<∞, we know that it is uncountable. Computing the number of permutations for a character set C and a length L requires us to compute CL, i.e. C raised to the power of L - let's call this ƒS. We do this commonly for determining the number of possible values storable in an n-bit binary string, by computing 2n, so it should be a familiar task. Unfortunately, L in our case is not a defined number; it's a function. So we're really trying to compute C raised to the power of ƒL, which is rather meaningless since the output of ƒL could be any positive integer. However, we can observe the behaviour of this operation - since the outputs of ƒL are an uncountable set, any value of C would always cause produce an uncountable set too. As such, for any value of C, ƒS always produces an uncountable set, and therefore the keyspace remains infinite regardless of the character set, as long as the possible lengths of the password fit into the set ℤ+.

Now, all of the previous was purely theoretical, and largely nonsensical in any applicable way. In practice you couldn't allow a 2×10100 character password, so you do actually have a limit. As such, the set ƒL becomes countable, and therefore the set ƒS becomes countable too, and by definition is now dependant on the value of C. But to what extent does this matter?