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

Question

Possible Duplicate:
Doesn’t imposing a minimum password length make the password weaker by reducing the number of possible combinations?

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?

Answer 1

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 C^L, 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 2ⁿ, 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×10¹⁰⁰ 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?

The answer is not based in mathematics, and this is precisely why I've taken you on a circuitous and verbose route to this point. It's not about the numbers, it's about the people. We've seen, time and time again, the bad password practices employed by the masses. The password dumps leaked after breaches of major sites like LinkedIn, Sony and Gamigo have demonstrated how horribly common poor passwords (like "letmein" and "dragon") are. The holy grail of password policy is one that makes users pick passwords that are resistant to manual guessing and bruteforce attempts, yet remain memorable enough that the user doesn't have to re-use passwords. The holy grail does not exist. You cannot possibly make every single user adhere to perfect password policies.

Providing a password policy that brings some absolute minimum requirements (one letter, one number, minimum 7 characters) is enough to bring 100% of the offenders over to a non-dictionary password, 80% of them over to a non-common password, and kill off 90% of common passwords. That means you've successfully reduced your attack surface for low-hanging-fruit attacks by at least 80%, which is a big win. Furthermore, you've not dented your conversion rates on signup, since basic password policies are standard practice to most users.

So, whilst you may be theoretically reducing your character space, it's a poor measure of password security and a complete tangent to the real goal of increasing security. Password policies are about people, not numbers, and as such must be studied as a psychological mechanism, not a mathematical one.

Answer 2

As a practical matter, it increases the strength of the average password even though it decreases the strength in theory. Human beings tend to use easier-to-remember, easier-to-type passwords by preference, so unconstrained passwords tend to come from a smaller actual password-space, tending to be shorter, with less likelihood of case changes, digits, and special characters. So though constraining it reduces the true (theoretical) space, it excludes many higher-likelihood passwords and thus tend to (slightly) increase security. It means I can't use my favorite, "abc123".