Visiting a BBQ, I recently enjoyed some interesting talk with some guy working for some government agency who was openly discussing their password policy (to be honest: he ranted about it). Of course this person wasn't one of their SEC folks, since even the best password policy shalt be treated as internal -- as it helps eliminating useless attempts in brute force password guessing. Notably.

Password policies

Password policies enforce things employees hate. A good password policy enforces a password to contain alphabetic symbols in upper and lower case, numbers and special characters. Plus the password needs to have a minimum length. Granted, some administrators have a heart for their password-hating users and passwords must fulfill a length requirement plus three of the four sketched criteria. Still, most users hate password-changing-day pretty much as they spend the morning with creating and changing the password and struggle the rest of the day with intutively entering the old password.

I understand them. This being said: That's not the point.
The point is not to talk, tweet, sing, draw, paint, write, or dance about it to strangers. Because strangers always may be attackers. Think social engineering. And literally everything an attacker can get to know about your password will reduce his effort.

Password length

OK, you don't belive me. I totally can understand that. Let's change that and do some math.

A US keyboard typically features 95 symbols (numbers, letters in upper and lower case and special characters [including the space!]) which may be used in passwords. Thus, there are 95n possible variants for a passwort with the length n. Granted? Granted.
Now, if I want to attack your account with a brute force attack, that is by testing every possible password, I will have to test all one-character passwords (95), then all two-character-passwords (952) and so on -- in short, 95+951+...+952.
In case I do know your password has a minimum length of, say m characters, I do not have to test all passwords with a length less than m -- because you will not be allowed to use them anyway. By definition they cannot be the answer to the question "what's your password?".
Sounds simple, but it adds up: The longer the minimal length of you password (increasing the number of possible passworts after all), the more passwords i don't have to test (because I do know they can't be what you use).
At this point, we should have a look at some numbers to get a feeling for it. Below, you find a table with the number of passwords with the exact length n and the number of all passwords with up to n characters:

Password length Possible passwords with exactly this length Passwords up to this length
1 95 95
2 9025 9025+95=9120
3 857375 857375+9025+95=866495
4 81450625 82317120
5 7737809375 7820126495
6 7,35092 * 1011 7,42912 * 1011
7 6,98337 * 1013 7,05766 * 1013
8 6,6342 * 1015 6,70478 * 1015
9 6,30249 * 1017 6,36954 * 1017
10 5,98737 * 1019 6,05106 * 1019

As you may notice, the number grows quite fast -- not that much of a surprise. It's the reason for a minimum-length policy after all. Now let's see what happens when I do know your password policy. Let's assume you do have a password featuring 10 characters.

Known minimum length Number of passwords which now can be eliminated without even trying Percentage
1 0 0%
2 95 1,56997 * 10-16%
3 9120 1,50717 * 10-14%
4 866495 1,43197 * 10-12%
5 82317120 1,36038 * 10-10%
6 7820126495 1,29236 * 10-8%
7 7,42912 * 1011 1,22774 * 10-6%
8 7,05766 * 1013 0,000116635%
9 6,70478 * 1015 0,011080341%
10 6,36954 * 1017 1,052632416%

So I was able to eliminate ... nothing. Almost nothing. Big deal? Oh wait, look at the numbers. They're big. Really big. Eliminating 1% seems ridiculous, but not having to check 6,36954 * 1017 passwords helps a lot. If we're able to test 100k passwords each second, we were able to get rid of 6,36954 * 1012 seconds of pointless work (that is 73721549 days on one machine -- but I may have 73721549 machines ready and waiting). Of course leaving 99 times as much to do.

Composition policies

Let's have a look at how the 95 possible symbols of your password are assembled:

How shall it help me to know that you must have at least two of each in your password? Because I know what at least some of the symbols in your passwort cannot be: If you have your ten-character-password and the policy "at least two of each group" applies, I do know your password will not be ten numbers. Because you have to have at least six symbols which are not numbers!

The basic underlying problem is simple: If I do not know anything, "1234567" is just as likely as "G0r!lAz" (that doesn't make "1234567" a great password, but I will have to test it anyway and spend time on doing so). But as soon as I learn your password policy, I can reduce that number of possible passwords by removing all futile combinations from my to-do list and will be able to increase the effectiveness of my attack.

Lets walk through this, step by step. The first step is to determine the maximum count of combinations of each. Please note that we haven't talked about the position of these symbols in the password, as they do not need to be put next to each other ("!Go7!4Mn" compared to "GMno74!!" -- on that, which of these two beauties would you pick?). However, here the numbers. Keep in mind, we're looking at "must have"-conditions, so they don't add up. If you must have two lower letters, you can't have just one ;)

Count of symbols Total number of numeric symbols Total number of upper/lowercase letters Total number of special characters
1 10 26 33
2 100 676 1089
3 1000 17576 35973

you will probably not be forced to have more than three of each in your password, so we can keep the table short.

However, if we assume each class of symbols not to be interleaved ("GMno74!!"), we can easily do the maths. Your password has a lenght of ten and you have to have two of each class. With this, there are 100 variants for the two numbers, 676 variants for the two lowercase letters, 676 variants for the uppercase letters, 1090 variants for the special charakters, and 9025 variants for the two characters you're free to pick from all 95 possible symbols. That makes a total of 4,49539 * 1014 possible password combinations. We still have to consider the mixing of the groups.

This is where binomial coefficients come to the resue as they can be used to model that we have (in a n-symbol password) n possible positions for the first symbol, n-1 for the second and so on. With them, you come to 5.09309 * 1019 possible passwords with ten symbols of which two are enforced to be from each class.

Yes, that's still a big number.

If you want to calculate some more, the formular turned out to be
Combinations(n,m_l,m_u,m_s, m_n) = 26^m_l * 26^m_u * 33^m_s * 10^m_n * 95^(n-m_l-m_u-m_s-m_n) * ( n! / ( m_l! * m_u! * m_s! * m_n! * (n-m_l-m_u-m_s-m_n)! ) )
Where
n is the length of the password,
m_lis the enforced minimum of lower case letters,
m_uis the enforced minimum of upper case letters,
m_sis the enforced minimum of special characters,
m_nis the enforced minimum of numerals.

Conclusion

That were some big numbers. But what does this mean in everyday life? Is it dangerous to talk password policy? Or isn't it?
Let's have a look at the numbers for your beloved ten-symbol-password. You made party smalltalk about your password being enforced to have a minimum of ten characters in which minimum two of each group. I consider you lazy, so your password will be *exactly* ten characters. Here are the numbers:

Possible passwords if I know only that it has up to ten chars (maybe less):6,05106 * 1019
Possible passwords if I know you have to have ten chars: 5,98737 * 1019
Possible passwords and I know the two-of-each-rule: 5.09309 * 1019

Even tough there are still 5 * 1019 possible combinations out to be tested for, your careless talk eliminated roughly 1019 additional combinations which I won't have to test any longer.
This can't be stressed enough: Just by talking, an attacker's life just got one sixth easier!
You may ask whether that is a real problem or just a theoretic one -- and I have to say "that depends". It depends on who your attacker is. And that in return depends higly on who you are. If you're just a guy who works at The Home Depot and talks about the password policy for his home computer -- it's probably not a problem. But if you're working for -- say -- DoD, UN, NATO, <insert country here> government, you have to deal with a quite different class of attackers.Granted -- you won't be a top target for Chinese Intelligence if you're on rookie level. But there are two important points: A. To intelligence, there is no irrelevant information and B. the password policy is applied to the whole organization! The point is that you're not just discussing your password policy, but also the password policy describing the passwords of (in case of DoD) e.g. Secretary of Defense, Secretary of the Army, Secretary of the Navy, Secretary of the Air Force; (in case of UN) the Secretary General, the Deputy Secretary General, the General Assemb... you got the idea? Great. I won't have to look up NATO ranks or list goverment officials' positions then. Long story short, you described password policies of high-value targets. That kind of target for which one builds up super computing clusters to get their password cracked before they've got to change it.

Still with us? Then we can take it one step further. I assume you to be lazy. That's nothing personal, in fact, I assume everyone to be lazy. Part of laziness is that you won't make up a super-perfect password (especially if you are forced to change it on a regular base). Instead you will find the first combination fitting the requirements and being memorable to you. And, fun thing, so can I. Here's the inside scoop: If I listen to you talking and maybe move the topic slightly to the right direction (hey, I got this 'ad001' thing from University as my logon name, pretty cool, isn't it?) you may answer with "Yeah, we have this stupid first-letter-of-firstname-plus-family-name-thing.
Ouch, that one hurt. Why? Because I -- as an attacker -- just gained more precious information. I can not only create very probably the user names of the high-ranked folks mentioned above but for everyone in your organization. All I need is a telephone directory. If your organization is big enough, I may even go for arbitrary lists of common names. And try each of these names with the ten most promising (since easy-to-remember) passwords fitting the policy. Testing the easiest modifications of them for, say, the first twenty password-change times ("01WpDn!@" becoming "02WpEn!@"...) is promising too.
And that's pretty much why OPSEC hates your watercooler-conversations on password policies -- if it's not your company's watercooler.

There are so many adequate posters from WWII,
it was a hard decision which one to put under this
article. I went for this work of Kenneth Bird:

The happy end

You want a happy end? Ok, here it is: If your organization is a high-value target and you're dealing with highly sophisticated attackers, they'll already know your password policy better than you can remember it. Thus your talk probably won't change: Those who can afford an attack already know and those who are learning the policy from your talk usually won't have the funding for a successfull attack.

Thanks

I want to thank Ragnar Nevries who helped me when I got stuck on the question of how to model the arranging of given symbols :)

Stichworte:


Impressum