Wednesday, February 03, 2010

The Password Meta Policy

Light CaressPatterns. They're everywhere. The way you get dressed in the morning. The way you brush your teeth. The way you fold your underwear (or in men's case, the way you just toss them in a drawer, unfolded). The way you tie your shoes or neck tie. The way you start your car. The way you drive to work. The way prepare and eat food. The way you make love...

Whenever we do anything more than once, we tend to create patterns that dictate how we perform even the most minuscule task. Patterns are good. In fact, patterns are great! They help us predict how much time and effort each task will take, and they reduce the amount of processing our brains need to do to get a task done. They also makes it easier for others to predict how we will behave in a given situation, which in turn makes cooperation easier.
But sometimes, patterns just suck. Bear with me while I explain...
Over the past year, I've been writing a piece of software that analyzes password usage history. The software measures things like password policy compliance and how long it takes for a change in policy to actually propagate to all passwords (if it ever does). It generates lots and lots of boring statistics on character frequencies, password formats, unique characters, login names used in passwords, usage of common words in passwords and so on.

More interestingly, however, the software meters how much difference there is between the previous and new password, whenever a user has to change it. And that, ladies and gentlemen, can be a true eye-opener. It seems to go like this:

More complex password policy = Less difference between passwords
Keep in mind that there's a difference between technical complexity and perceived complexity; a high password change frequency increases the perceived complexity, but it doesn't make the policy technically more complex.

It seems that the more complex the password policy is, the more likely it is that the user will seek to create the lowest common denominator password that will still be in compliance with the password policy. Couple this with a high change frequency, and humanity's uncanny knack for creating patterns everywhere, and predictability, that old nemesis of password security,  rears it's ugly head.

In the vast majority of cases where I've had the opportunity to analyze password histories larger than 1 (!), I have found the following to be true: If one gets hold of a user's password (and it doesn't even have to be a current one), one can with reasonable confidence predict all the future passwords, unless once or more of the following scenarios occur:
  1. The password policy changes in such a way that the password pattern is made invalid, and a password change is forced.
  2. The user buys a new car.
  3. The user's pet dies.
  4. The user gets married, or the spouse leaves.
  5. The user moves to a different city.
  6. The company name changes.
So much for changing the password every 90 days, huh? Okay, it might still mitigate Pass The Hash attacks on Windows, but only if the attacker didn't manage to crack the hash she stole before the end of that 90 day period.

Like I was saying, sometimes patterns just suck.

So, with added complexity comes added predictability, but can this be mitigated? The solution is so simple, it's actually a bit scary:

Change the password policy every time.

Yes, you read that correctly. Every time someone enters a new password, change the password policy. Or rather, generate a new password policy that applies only to that user for that password change, based on a separate policy that dictates how new password policies are to be generated. This effectively prevents a user from following any patterns.

Let's call this the Password Meta Policy.

I envision the password meta policy as having two distinct sections: A non-volatile and a volatile part. The non-volatile part describes things that apply to every generated policy. The volatile part is a list of policy items that will be customized into the unique (or at least unique'ish) policy that is applied to each password change.

The following is a sample password meta policy I have created. One of my goals when creating this meta policy was to make it generate a policy that is possible to implement (using passfil.dll, PAM, or whichever pluggable system you prefer), and where policy compliance is measurable. You may, of course, create completely different meta policy.

Without further ado, the Password Meta Policy:

Non-volatile rules
  •  The new generated policy must deviate from the previously generated policy on at least 3 points. This means you have to store each generated policy in the password history. Impractical, I admit, but not impossible.
  • Automatically reject 73% of all passwords. Let's face it; most passwords are bad anyway.
  • Each volatile policy rule only has a 73% chance of being included in the final policy. This ensures further password unpredictability.
Volatile rules
  • Minimum password length is chosen randomly, between 1 and 64 characters.
  • Maximum password length is chosen randomly, between minimum length and 64 characters.
  • The password must or must not contain lower case characters.
  • The password must or must not contain upper case characters.
  • The password must or must not contain digits.
  • The password must or must not contain special characters characters.
  • The password must contain at least a randomly chosen percentage of vowels or consonants.
  • The password must not contain a word found in a randomly selected dictionary, chosen from a predefined set of dictionaries.
  • The password must not contain user name or real name of the user. Which one may be randomly chosen.
  • The password must or must not contain a word that rhymes with a word found in a previous password. There are lots of algorithms for this.
  • The password has to be changed after a random number of days between 1 and 365. One might conceivably factor in events like Christmas, Halloween, public holidays, spring break or basically anything that might have an impact on the activity level of the black hat population.
It's quite clear that some thought needs to be put into the creation of a password meta policy. In particular, one needs to avoid rules that could potentially contradict each other, since this may lead to a situation where it is impossible to construct a password that is in compliance with the policy.

So, what does a generated password policy look like? Well, click the button below to find out. Then click it again, and again.


  1. Haha. ;) Tror jeg satser på PIN og engangspassord.

  2. Statisk 4-sifret PIN da Jan Roger? PIN koder er jo også passord. Når endret du dine sist? ;-)

  3. Has your research ever turned up the trend to choose passwords that are easy to type? Probably good to reject passwords scoring high on a basic ease-of-input algorithm (you know to thwart cracking programs that prioritize their dictionaries in a similar manner)

  4. Hmmm, good question Gordy. I suppose that "easy to type" can be interpreted in many ways, but I've been looking into keyboard patterns where the password is "impossible" to remember, but the pattern is really easy. Like typing an X using EFV-CFT on your keyboard, moving one character left for each change.

    Not too many doing that. :-)

    As for dictionary mangling etc I'm still looking for free time to read the dissertation from Matt Weir ( I think he's done an amazing job in this area to improve the success rate as well as the speed of logical (rule-based) dictionary-hybrid attacks on passwords.

    Best regards,
    Per Thorsheim

  5. "Minimum password length is chosen randomly, between 1 and 64 characters.
    Maximum password length is chosen randomly, between minimum length and 64 characters."

    So you might end up with minimum 1 and maximum 1. Ouch :-)

    I don't like passord policies with a maximum length setting.


All comments will be moderated, primarily for spam. You are welcome to disagree with my posts of course.