Password Complexity: Hows and Whys Explained

Spread the love

Over the last year, we’ve seen news stories of sites getting hacked and passwords getting stolen and we’ll doubtless see more in the future.  These range from the relatively irritating to the level of possible identity theft.  In every case, especially when the passwords have been published, we see the usual advice from the experts: use complex passwords, don’t share your passwords, don’t use the same password on multiple sites… It’s basically the same list trotted out all the time, but I see few explanations of why people should do these things.  It’s not bad advice at one level, but doing something out of blind obedience has actually made security worse on occasion, and passwords are part of that mess.

Passwords are usually hashed when they’re stored, which is to say that they’re run through a mathematical algorithm to create a value that is easily calculated but not easily reversed.  By hashing the password, it cannot be easily read and usually must be determined by brute-force attacks.  This is different from encryption because encryption is reversible with a key.  This key has to be stored somewhere, and if it’s found by an attacker, anything encrypted may be decrypted and read.  However, in some cases, the passwords have been stored as plaintext (not hashed or encrypted) or, at best, encrypted with an easily-found key.  These are mistakes in system design, and no password length or complexity advice will help you.  The only thing that will help you there is not using that password on more than one site.  But if that site happens to be an important one, such as for a bank or work, the results can still be catastrophic.

Fortunately, that particular scenario is becoming less common as programmers learn and older systems are replaced with newer, more secure applications.  So let’s look at the most common item that is recommended, which is password complexity.  We’re told many things:

  • Use letters, numbers, and symbols
  • Make sure it’s at least eight characters long
  • Don’t use any real words, names, birthdays, or other patterns that might be guessed

These all make some sense.  After all, a password like “nieF$AD=” certainly looks more secure than “password1” if quite a bit harder to remember.  But aside from the first one, they’re really starting to show their age.  Most people, if told to use a password of at least eight characters, will use a password of exactly eight characters.  In my former job as a security admin, I often wanted to pound my head into my desk in frustration.  But in my job as a penetration tester, I love these passwords.  For technical reasons I won’t get into here, an eight-character password is trivially easy to break.  This is in large part due to a hash function used in Windows (known as LM) that is incredibly weak but still in widespread use due to legacy applications and, frankly, IT’s fear of breaking things and getting yelled at.  I can crack such a hash using brute force in less than an hour in most cases, information can sometimes be reused, and this doesn’t even get into more modern methods that may allow me to break thousands of passwords in an hour.

So, why the complexity?  Why make all these passwords so difficult to remember?  It comes down to two things: the number of possible passwords and something called Moore’s Law.  We’ll talk about Moore’s law in a moment.  First, I want to go into password complexity.

Every password has what is called a character set.  This is the set of allowed characters for that password.  In some cases, all characters are allowed while in other cases, some are excluded, usually for technical reasons.  I’m not going to get into the latter case, but understand that every character excluded slightly weakens the possible passwords set.  Exclude too many, and you get a significantly weaker password.  For example, a password that allows only numbers (so only 10 possible characters) is very weak compared to one that allows letters and numbers (62 possible characters including 26 each upper and lower case letters plus 10 numbers).  This is because the range of possibilities comes by multiplying the number of possibilities out for each space.  A four-character ATM PIN can have 10 x 10 x 10 x 10 = 10,000 possible values; a four-character password that can use mixed-case letters and numbers has 62 x 62 x 62 x 62 = 14,776,336 possible values.

Let’s look at this in context of the general rules: eight characters, letters, numbers, and symbols.  (For this article, we’re going to go with 33 common symbols possible.)  Here’s how many passwords are possible at 8 characters with the numbers rounded off for convenience:

  • Numbers: 100 million
  • Single-case letters: 209 billion
  • Single-case letters plus numbers: 2.8 trillion
  • Mixed-case letters: 53 trillion
  • Mixed-case letters plus numbers: 218 trillion
  • Mixed-case letters plus numbers plus symbols: 6,600 trillion

As you add possible characters, the potential number of passwords goes up rapidly, and that’s just for eight characters.  Here’s how it looks for 12 characters:

  • Numbers: 1 trillion
  • Single-case letters: 95 million billion
  • Single-case letters plus numbers: 4.7 million trillion
  • Mixed-case letters: 391 million trillion
  • Mixed-case letters plus numbers: 3.2 billion trillion
  • Mixed-case letters plus numbers plus symbols: 540 billion trillion

Impressive at a glance.  But what does it mean in more practical terms?  That question takes us back to Moore’s law.

Moore’s law comes from an observation that Intel co-founder Gordon Moore made in 1965 where he noted that the number of transistors in microchips sold at about the same price point was doubling about every two years and would continue to do so for at least a decade.  Nearly fifty years later, this is still true, though it might be slowing a little.  Generally, the more transistors a chip has, the more it can do in a given time.  Thus, as chips have gotten faster, we’ve been able to crack passwords more quickly.  If at a given point in time, a system is able to crack one million passwords per second, for about the same price two years later, a system can crack two million passwords per second.  Ten years after that, a system can crack 64 million passwords per second.  This is a very rough approximation and doesn’t take into account many other factors.

So what’s the current capability?  A system that cost perhaps $2000 in 2011 can try 10.4 billion passwords per second against a single password for a specific hash function (NTLM).  That system would probably cost under $1000 today.  We’ll use that password to consider how long it would take to crack the password possibilities listed above.

For eight-character passwords, that system would take:

  • Numbers: 0.01 seconds
  • Single-case letters: 20 seconds
  • Single-case letters plus numbers: 4.5 minutes
  • Mixed-case letters: 1.4 hours
  • Mixed-case letters plus numbers: 6 hours
  • Mixed-case letters plus numbers plus symbols: 7.3 days

Those are some discouraging numbers.  It wouldn’t take long to crack a single password if it were known to be eight characters.  How does it look for 12 characters?

  • Numbers: 96 seconds
  • Single-case letters: 15 weeks
  • Single-case letters plus numbers: 14 years
  • Mixed-case letters: 1200 years
  • Mixed-case letters plus numbers: 9750 years
  • Mixed-case letters plus numbers plus symbols: 1.6 million years

Those are much better numbers.  But remember that they will effectively weaken over time, and these times are actually worst-case scenarios for the attacker.  Passwords are cracked on average in half the maximum time.

On top of that, even these times may already be halved due to Moore’s law, and there’s a system designed by password expert Jeremy Gosney that can try 350 billion passwords per second.  It can crack every password up to eight characters hashed using NTLM in under six hours.  A single-case password with numbers would fall in about 22 weeks instead of 14 years.

So what is one to do?  Even as a security expert, these kinds of numbers can get downright discouraging.  But there is a solution, one that can actually make things easier to remember and more secure: pass phrases.  I’ll touch on them later this week.

One Reply to “Password Complexity: Hows and Whys Explained”

Leave a Reply

Your email address will not be published. Required fields are marked *