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.

We know about password attacks in Kansas

I was making a dent in a sink full of dishes tonight and half listening to the TV when a show caught my interest. Dateline NBC was airing a segment on the disappearance of John Elwin during a business trip. Apparently his girlfriend, Kirsten Flood, wasn't initially having luck interesting authorities in a search for clues about the whereabouts of Mr. Elwin. Frustrated, she engaged a friend, Denise Tripoli, with "experience in Internet security" to help.

The following excerpt comes from the show's transcript:

   If only she could hack into Elwin's e-mail account, they might discover where he was.

   The two women wracked their brains trying to guess at a pass code that would give them access.

   FLOOD: [We tried] his birthday, his social security number. And I just kept going down the list until I hit it.

   FLOOD: And lo and behold, we got into it.

   BOB MORRISON: What did you find there?

   TRIPOLI: We broke into his account at eleven o'clock at night, and I was up till three in the morning, looking through every e-mail. And I was very disturbed by what I saw.

I certainly won't pretend that I would avoid this temptation if one of my friends or family members went missing and I had exhausted other options. Nonetheless, I was a little disturbed by the casual explanation of how these women broke the law to gain access to Mr. Elwin's email account. In my opinion, reporting this part of the story in this manner trivializes the ethical and legal implications of getting into another person's email account.

You would expect that a news organization so eager to expose the secret underworld of hackers would act more responsibly.

Automating analysis of authentication system weaknesses

Most knowledge-based authenticators run the risk of poor uniqueness when they rely on users to generate or select the secret information. The human mind tends to seek order in the knowledge we acquire and store. This means that you, I, and a few billion others generate similar secrets for authentication.

Seeing as how I make a living off applying my knowledge I don't complain about this natural phenomenon. However, I do occasionally wish that more authentication system designers took it into consideration. While we can't expect them to overcome this reality, they do need to anticipate it and avoid design or implementation decisions that magnify problems.

For example, PassPoints is a knowledge-based graphical password system developed a couple of years ago. This system presents users with a picture and authenticates them by analyzing where they click within the image. Users choose and click on their own series of points during the authentication enrollment process. During subsequent authentications, only the legitimate user should know where to click within an image.

Of course, the security of the system relies on the premise that there aren't a limited number of predictable click points within the image. Good old human brains will sometimes look at the same picture and click on the same points. Our eyes may all be drawn to the fire hydrant, building corner, or stunning brunette. With graphical passwords this appears to be dependent on what is depicted in a particular image. The more predictable the click points are within a picture, the less useful that picture is for uniquely authenticating users.

So I was pleased to see a recent paper where the authors not only recognize this challenge, but also attempt to automatically evaluate an image for predictable points. Modeling User Choice in the PassPoints Graphical Password Scheme is an update from several of the original PassPoints researchers explaining how new software could sometimes accurately predict (70% - 80% in their test case) clickable points within an image. In turn, this software could be used to eliminate images that have too few likely-to-be-clicked points.

I hope that this trend of investigating and developing quality controls for authentication systems continues.

Banks fail to meet FFIEC multi-factor authentication requirements

According to a recent study, only 4% of financial institutions are actually meeting the FFIEC requirements for multi-factor authentication. Many of the others are relying on challenge questions or other risk-based authentication approaches that ultimately only provide single-factor security.

I’ve shared more on my analysis of this problem and its implications in this Security PS blog entry.