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.
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|
|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|
|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.
Let's have a look at how the 95 possible symbols of your password are assembled:
- there are 26 lower letters,
- there are 26 upper letters,
- there are 10 numbers,
- there are 33 special characters.
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|
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)! ) )
|n||is the length of the password,|
|m_l||is the enforced minimum of lower case letters,|
|m_u||is the enforced minimum of upper case letters,|
|m_s||is the enforced minimum of special characters,|
|m_n||is the enforced minimum of numerals.|
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.
it was a hard decision which one to put under this
article. I went for this work of Kenneth Bird:
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.
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 :)