Sunday, October 11, 2015

Why is length > complexity? Because math...

I routinely work with people who argue that their 8 character passwords are secure because they force complexity requirements.  This simply isn't true.   Picking a passphrase (or simply a much longer password is mathematically more secure.  Some smart person will point out that if I know all passwords consist of combinations of only dictionary words, then I effectively have created shorter passwords.  While this is true, not everyone creates a password this way and intentionally misspelling a word (this happpens much more than you might reelize) makes things that much more secure.

Let me start by saying that I’m sure I’m not the first to write about password length vs. password complexity.  Heck, XKCD even did a comic on it.   So why am I writing this post arguing for length over complexity?  I was out to lunch with a client the other day and the subject came up.  He said “you should write a paper on that.” I told him there were probably other blog posts out there explaining it, but after a quick Google search he argued none that explained it as simply.  So that’s my mea culpa.  If you don’t like this post, go complain to my client.  I’d tell you who they are, but oh yeah (too bad for you), we’re NDA’d.

Password policies are all about making passwords hard to guess and the hashes hard to crack.  When cracking hashes, there are two approaches (I’m keeping this simple).  The first approach is to guess a password you think might be in use (e.g. a dictionary word or ‘123456’).  The second approach is to simply brute force, trying every possible combination of characters.  It’s the latter (more interesting) case this post will examine.

When brute forcing passwords, we have to assume that on average the attacker will guess correctly in half the total number of possibilities.  So which matters more, length or complexity?  Well, let’s take a look at a standard 8 character password.  We’ll assume our average user won’t use numbers, capital letters, or special characters.  This leaves us 26^8 possible passwords.  Of course we’re ignoring that users will pick recognizable letter patterns (e.g. words). 

What if we teach our users about the magic of the shift key and they start using capital letters?  That changes the base to 52 but the exponent remains the password length.  Now we have 52^8.  This is certainly an improvement.
26^8 = 208827064576
52^8 = 53459728531456

If we educate users about the fact that they can type numbers in their passwords too then the base increases to 62.  Okay, that’s a bad joke since two of the top 10 most popular passwords are 123456 and 12345678.  But how big of a difference is that really?
26^8 = 208827064576
52^8 = 53459728531456
62^8 = 218340105584896

Not too shabby.  Add some special characters in and you are now up to a base of 94.  How big is that?
26^8 = 208827064576
52^8 = 53459728531456
62^8 = 218340105584896
94^8 = 6095689385410816

So clearly adding complexity to a password works.  In fact, forcing users to put a special character in their passwords first is best, followed by uppercase.  Adding a number only increases the base by 10.

But what about length?  Let’s assume for a moment that we don’t care about complexity but force the length to change instead.  In this case then we’ll assume that our users will use only lower case characters, giving us a base of 26.  We’ll also force the users to have a minimum length of 12 characters.
26^12 = 95428956661682176
26^8 =   208827064576
94^8 =   6095689385410816

Note that a 12 character password with no complexity requirement is better than an 8 character password requiring all four character food groups.  Math just works this way.  When you increase the exponent, you radically change the game for the attacker.

What if we follow best practices and move to a 15 character password?  Why 15 characters you ask?  Because that’s the magic number greater than 14 where LANMAN hashes are no longer stored.  Of course you could turn this off on the domain controller, but forcing a 15 character password is great for security and kills two birds with one stone.  For this, we’ll assume that the user is uber lazy and only uses digits for their password (the worst possible case), giving us a base of 10.
10^15 = 1000000000000000
94^8 =    6095689385410816

Well, we finally found something worse than the 8 character password with maximum complexity.  But let’s be real here: no user (with the possible exception of Rain Man) is going to try to remember a 15 character string of digits.  Your users are much more likely to combine some letters together into multiple words like “airlinefoodughh”.  What’s the complexity there?
94^8 =    6095689385410816
26^15 = 1677259342285725925376

Okay, the difference here should be clear.  By forcing longer passwords we increase security. Everybody knows that.  But users can easily remember a short phrase like “airlinefoodughhmystomach” or “iwanttorideahorse”.  They are quite a bit worse at remembering things like “Jw176!@t”.  And let’s not kid ourselves. Which password is more resistant to brute force guessing?  Incidentally, it’s the one that’s easiest to remember.

I’d be remiss not to note that some detractors will say that passwords which only string dictionary words together need not be brute forced and are much easier to guess.  I’ll concede that if the attacker knows that all your passwords are just strings of dictionary words, then the point is valid. But your attacker doesn’t (or at least shouldn’t) know this.  In my many years of password cracking, I’ve never (to my knowledge) even tried the password “iwanttorideahorse” or it’s many derivatives.

To those who may note that users will be tempted to write longer passwords down, let’s not kid ourselves.  Your users are doing that anyway.  Long passwords will never prevent users from compromising themselves in the physical domain, but will definitely thwart attackers trying to remotely brute force an account.  And in the event that your hashes are stolen you can rest easy knowing that “soupsmellslikefish”, while easy to remember, is less likely to ever be recovered by a cracking program than your lame 8 character password that used a keyboard walk.

8 comments:

  1. In defense of your phrase approach, you are significantly increasing the base to the size of your dictionary. Even if you use a relatively small dictionary of 100,000 english words (out of an estimated 1 Million from google/Merriam-Webster) makes a five word phrase orders of magnitude larger than 26^15. The complexity can also be increased with capitalization, punctuation, and special characters as word boundaries (including spaces!) .

    ReplyDelete
    Replies
    1. Thanks for the comment. You are 100% correct in your assessment.

      Delete
  2. One thing also worth noting is that many places tell you to think of a memorable phrase "Quick Brown Foxes And Lazy Dogs" and then ... truncate it down to only the first letters (QBFALD) and then throw some numbers and symbols in. If you've got to remember the whole phrase to begin with, just *use the whole phrase* as your password.

    Another thing worth noting if we're talking about 8 character passwords and brute forcing. My organization bought a $10k commodity hardware password cracking rig a few years back that we use on some of our engagements. It takes 6 days to bruteforce /every/ possible 8-character password. Doesn't matter how random it is, if it's 8 characters, we own it. Obviously, more (and newer) hardware pushes this number down even farther, but we've certainly startled some people with just how rapidly their 8 character passwords get broken.

    ReplyDelete
    Replies
    1. My company (Rendition Infosec) has a couple of relatively robust GPU cracking rigs as well. We've seen similar astonishment from customers when we are able to crack the short passwords they thought were safe because "they used complex algorithms."

      Delete
    2. Trying again…hope it won't double post:

      Literally any 8-characters? As in any of the 256 Ascii-chars?
      If you're able to I'd really like to see what happens if you throw fancy passwords like 2∞&bYond (truncate if nessecary) into your machine.
      If not…I'd gladly hear an educated guess from your side.

      *** New passwords to contain Uppercase, Lowercase, Number, Special char and Emoji ***

      Delete
    3. No, I'm not counting emoji and non-ASCII characters. Most organizations that use 8 character passwords do so because they have legacy systems that don't support longer passwords. In those cases, you frequently can't use special characters. I'm not sure how long it would take because I've never tried passwords like that. Realistically, I'd expect it to take a few hours to a day if we built frequency tables for those special characters.

      Delete
  3. If password policies are enforced, the number of possiple passwords will even be decreased. Assuming a pw with length of 8 chars and a policy which enforces a capital letter, a number and a special char:
    The amount of valid passwords will only be:
    94^5*26*10*32 = 61060814663680 (or ~100 times lower as without policy enforcement)

    ReplyDelete
    Replies
    1. I see your point and it's well founded. But I don't think that's a good argument against password policies. While they theoretically decrease possible combinations, without them your users will use MUCH weaker passwords.

      Delete

Note: Only a member of this blog may post a comment.