How password policy requirements impact possible password choices

A recent discussion on a SecurityFocus.com mailing list raised a concern about password policies that I hadn't previously given much thought to. The post author commented that he wanted to enforce a policy that required passwords to have lowercase, uppercase, number, and symbol characters. By this he meant every password must have at least one character from each of these characters sets. One reader responded that by requiring the use of all four character sets he would reduce the total number of possible passwords, causing a negative impact on password security.

Instinctively I knew the claim about reducing password possibilities was right, but I dismissed the security impacts as insignificant. After all, with 95 standard characters within that character pool to choose from, the total number of password possibilities is massive. Unfortunately "massive" doesn't really provide much perspective on how negative the impact could be. To quantify the impact I decided to calculate the actual effects on password possibilities.

I started with a set password length of 7 characters, giving us 95^7 (or 6.98 x 10^13) total possible passwords that users can create without any specific character requirements. This gave me the unrestricted total. I then needed to figure out how many of these passwords would meet the restricted requirements of having lowercase, uppercase, number, and symbol characters within them.

Following some different approaches at number crunching I found that there may not be an easy formula for calculating the quantity of restricted password possibilities. The easiest approach seemed to be counting the number of passwords not meeting the criteria and then subtracting them from the unrestricted total. While not math intensive, this approach does take some fancy spreadsheet formulas. If you have a burning desire to see the numbers yourself, you can check out the resulting Excel spreadsheet I created.

When I compared the restricted and unrestricted password possibilities I was in for a bit of a shock. It turns out that for 7 character passwords the restricted requirements would eliminate about 63% (or 4.4 x 10^13) of the total password possibilities! So much for an insignificant impact.

I applied this technique for several different lengths of passwords to see how the length changed the results. The longer the password became, the more the percentage of eliminated passwords shrunk. The restriction eliminated 54% of 8 character passwords. With 10 and 12 character passwords only 41% and 31%, respectively, were eliminated. These losses still amount to sizeable chunks.

This led me to evaluate the impacts of the normal Microsoft Windows password complexity requirements. Enabling this security policy forces users to choose a password made up from only three of the four character types. For a 7 character password this still amounted to a 9% reduction in possible passwords.

So, numerically we've established the impacts of different password policies, but how should these numbers affect our decisions to enforce such policies?

If we consider password cracking our biggest threat then we must consider how knowledge of the password policy might save an attacker time avoiding unacceptable passwords. Fortunately, real-time brute force cracking isn't terribly compatible with this approach. In the time it takes for cracking software to evaluate whether a password guess meets the policy it could have just tried the password. So no effort is eliminated in this scenario.

However, a rainbows tables cracking approach can benefit from policy knowledge. An attacker could create a rainbow table consisting of only the passwords that meet a particular password policy. As a matter of fact, attackers do that today by generating and sharing rainbow tables consisting of the most common password character sets.

While bad guys could technically implement this attack for complex passwords, it would be one of last resorts. So few environments require passwords containing the four different character sets that attackers have little reason to generate the rainbow tables. It is still much more rewarding for them to focus on cracking passwords like "muffins" instead of "b@n4Na5".

More importantly, creating just the rainbow tables needed for our restricted password pool of 7 character passwords would require hundreds of terabytes of disk space. Yes, I did the math. Few attackers have this level of resources available to them.

We have always made sacrifices like this when instituting password policies. By establishing a minimum password length we, by definition, eliminate all possible passwords of a shorter length. Nonetheless, we know we are making a general improvement in overall password security by removing the shorter, and thus easier to crack, passwords.

When it comes to password complexity we have to consider the attack significance along with the mathematical significance. In reality, there are situations where enforcing specific password restrictions is a very bad idea. However, this is the exception rather than the rule.

I don't believe that enforcing either normal Windows password complexity policy or the even more restrictive 4 character set composition requirement should worry you when paired with a minimum password length of 7 characters. The loss of possible passwords in these cases are greatly outweighed by the benefits of eliminating a large number of poor password choices. From my perspective, those changes have a positive impact on security.