Posted by: rolande | April 21, 2012

Good Practices for Selecting Strong Passwords

password.png

Using passwords for authentication is inherently a fairly weak mechanism for security. Remembering complicated userID and password combinations for an average of 30 or 40 different applications and websites is darn near impossible for any normal person. So, we tend to use one combination that we can drill into our head and we don’t like to change it if we don’t have to. The problem is that passwords can be lifted by key-loggers, shoulder surfers or, if not sufficiently strong enough, they can be brute force cracked from the secret hash that is stored on a system for when a credential is validated for an access request. There are other super stealth methods but the point of this post isn’t to cover all of the remote possibilities of attack. The point is that, unless the application we want to use has some form of 2 factor authentication, we are pretty much stuck with the old school simple password option and we need to know how to achieve the strongest credentials in that scenario.

Steve Gibson puts it quite succinctly in his Password Haystacks article:

Every password you use can be thought of as a needle hiding in a haystack. After all searches of common passwords and dictionaries have failed, an attacker must resort to a “brute force” search – ultimately trying every possible combination of letters, numbers and then symbols until the combination you chose, is discovered.

If every possible password is tried, sooner or later yours will be found.

The question is: Will that be too soon . . . or enough later?

System Security

We like to hope the application/systems administrator has done their homework and properly secured all of their systems and infrastructure and is regularly patching and testing for vulnerabilities to ensure everything is locked down tightly and no unauthorized person can make off with the keys to the kingdom. But you never really can know or be certain of that. This potentially can provide an opportunity for your credential to be attacked and learned. The worst case scenario is that you use this same userID and password for all of your critical accounts. Once it is compromised in one location, you can bet the attacker is trying it with your userID combination on every known public Internet site you can imagine to see what other accounts they can compromise and pilfer or use to their advantage. So, we can’t control the security of the system where our usernames and passwords are being stored, albeit, hopefully, in some form of encrypted state. We also can’t perfectly control against keyloggers or shoulder surfers or man in the middle type attacks. However, the odds of these are quite low in comparison to the risk of someone lifting a password hash table somewhere and running a brute force attack to uncover userID and password combinations. So, what we can do is ensure that the passwords we use for these systems are sufficiently strong enough that any typical brute force attack to uncover your password will take an inordinate amount of time and processor power to achieve. The question is “How can you know what is a sufficiently strong enough password to counter the typical brute force attack?” That is the answer I hope to provide here.

Password Strength & Complexity

Entropy. You may hearken back to your days spent staring through your eyelids at the ceiling in Chemistry class when you may have vaguely heard your professor drone on about entropy as it related to the laws of thermodynamics. Well that is not the entropy I am referring to. Entropy as it relates to information theory is the measure of the uncertainty of a random variable. It is a measure of disorder or unpredictability. In this case, the random variable being the password or even each character position within the password itself. The goal of a strong password is to provide as much entropy as possible such that a brute force attack to guess the value of the password would take such a large enough number of guesses that it would require an enormous amount of processing power to accomplish the task in any reasonable amount of time.

So, how do we establish as much entropy as possible within a password and how impossible will it be for a normal human to memorize and recall the password for frequent use? Well, it is not very difficult to do at all and it can be quite easy to create a password that is memorable and fairly simple to use frequently. The key is the human brain’s ability to use mnemonics and shortcuts. It is like our own indexing mechanism for bits of information. But, I’ll get into that later. At this point, let’s just focus on the mathematics and probability of guessing a password.

There are 2 factors that weigh into the strength of a password. First and foremost is the length of the password. How many characters make up the password itself. The more characters there are in a password, the stronger it is, by a factor of at least 26 to 84 times per additional character, depending on the range of characters chosen from. Length is actually the single most significant factor in password strength. The second factor is the range of possible characters that could be found in any given character position within the password. Generally, most people stick to passwords that use just letters and numbers. If you only make use of lower case letters and numbers that leaves you with only 36 possible characters to choose from. In a typical 8 character password with only 36 characters to choose from, if I had access to the encrypted hash value, I could easily crack it in under an hour on my MacBook Pro. If you minimally add upper case letters into the mix, that processing time increases to over 2.5 days. That is a multiple of 65.85 times the duration it took to crack the password without any upper case letters. So, in combination with a longer password, the goal is to include as many character possibilities as possible to increase the entropy or difficulty of predicting the value of the password.

On a normal keyboard, there are typically 84 character options you can easily include in a password with a single keystroke or holding the Shift key. Password crackers know that the majority of people only use a range of 36 characters to create their passwords as they do not use symbols or upper case characters. This fact alone allows them to vastly reduce the time it takes for them to crack a password. If everyone just followed the simple recommendations you always see anytime you go to create a password (use at least 1 upper case, 1 lower case, 1 number and 1 special character like @,+,$,! etc. and you would render most trivial attacks useless requiring an attacker to use a brute force method.

Password length. Each additional password character significantly increases the number of password permutations. If you minimally used a mix of upper case, lower case, and numbers that is a factor of 62 times or almost 26 for each character. An 8 character password would be equivalent to 218,102,555,120,846 possibilities. If you threw in a special character that would be a factor of 84 times for each character. An 8 character password would then be equivalent to 2,479,550,445,438,080 possibilities or a factor of 11.4 times more permutations. If you add one more character and made it a 9 character password it would increase the permutations by a factor of 62 to 84 times, depending on the range of characters you are selecting from.

Excerpt from NIST 800-118

Increasing the character set from 26 characters to 95 characters on a four character length password increases the keyspace almost 200 times. However, if the length of the password is increased from four to 12, given a character set of only 26 characters, the keyspace increases by almost 200 billion times. Although both have significant effect on the overall strength of a password in resisting brute force attacks, outside of cryptographic attacks, length seems to be the dominating factor in determining password strength.

The problem is that even a fairly modest computer with a Graphical Processor (GPU) can attempt brute force password cracking at rates in the neighborhood of 500 Million to a Billion guesses per second or more. Without sufficient length and character options, a small computer can make swiss cheese out of your password in a very short period of time. With the advent of parallel computing, an attacker can easily gather a small cluster of computers and crack 70-80% of typical passwords stored in hash table. They can even use Botnets, thousands of unsuspecting Internet connected computers under their control, to perform these tasks. So, how can you create a reasonably difficult password that can stand up to the ever increasing capability of computer hardware and the propsect of parallel computing or a Botnet attack? You have to select a minimum password length and character set that creates a large enough pool that will require so much horsepower and take so much time that it would not be worth it for the attacker to continue dumping resources into the task.

The Math Behind Password Defense

A 12 character password with a possibility of 84 characters will yield 1.23410307017276 x 1023 or 123.41 sextillion permutations. Let’s see how long it would take an attacker to crack that password with a typical computer.

Based on the law of averages, it would take approximately half of the guesses to find the correct password. So we divide the starting number of permutations in half. If our typical modest computer can attempt 500 Million guesses per second, we can divide by 500,000,000 to find the number of seconds. Subsequently we can divide by 60 to find the number of minutes and 60 to find the number of hours and so forth.

(1.23410307017276 x 1023)/2 = 6.1705153508638 x 1022
(6.1705153508638 x 1022)/500,000,000 = 123,410,307,017,276 That is 123.4 Trillion seconds!
123,410,307,017,276/60 = 2,056,838,450,288 minutes
2,056,838,450,288/60 = 34,280,640,838 hours
34,280,640,838/24 = 1,428,360,035 days

1,428,360,035/365.25 = 3,910,636.65 years!!!

Even with a sizable Botnet of parallel computers, it is going to take an attacker years to crack that kind of password. They will typically give up long before they get your password.

Password crackers are not dumb people. They are typically pretty intelligent, as evidenced by the fact that they gained backdoor access to a system and lifted its password hash table. So, they will use the law of averages to their advantage to uncover encrypted passwords. In other words, gather the low hanging fruit first. They will use dictionary attacks going after common words and phrases first like ‘password’ and ‘12345’ etc. Once they have exhausted the obvious, they will then dig into the upper case characters and number combinations. In a typical password hash table an attacker could easily recover 10-15% of the passwords in under an hour using a list of common passwords and a dictionary of common words and phrases. Beyond that, they can probably collect another 20-30% in a matter of a day or two using rainbow tables. It also helps if they know the password minimum and maximum length and required characters. This can reduce the effective search time drastically, as well. So do you want to be in that group of 30-45% of the users who had their passwords owned within a day or two? It is kind of like being in a race with a group of people against a bear. You don’t have to be the fastest… just not the slowest.

How To Create Your Own Secure Password

So, now for the fun part. How do you create this exceptionally difficult password to crack and make it easy to remember and use? Remember that the single biggest factor in determining password strength was the number of characters and not the complexity of odd character combinations. The US Federal Government is currently recommending a minimum length of 12 characters be used for enterprise passwords to provide sufficient strength and complexity. So, we will use that as the baseline here.

Strange combinations of letters, numbers, and special characters are difficult for normal people to remember. But if we focus on length and use recognizable chunks, it is much easier for a person to remember and type. It is quite easy for the average person to use mnemonics as an association method to remember the word chunks and the order.

For example, I live in a house dominated by girls, 4 to 2.

girls dominate 42

That is not a hard mnemonic for me to remember. However, I have not made use of an upper case character or a special character to increase my character pool from 36 to 84. It is also 15 characters which is 218 times stronger. Anyway, I can easily transform these phrases to make the password sufficiently strong.

girls -> grlZ
dominate -> domin8

It also helps to not use contiguous numbers. So, in this case, I’ll reverse the two words. So, I end up with a password like this:

domin8grlZ42

Now, this might not be the easiest to type password but with the mnemonic it should not be difficult to remember.

Here’s a great geek cartoon from xkcd that helps illustrate the point further.

xkcd_password_strength

Another Alternative (Diceware)

For someone who absolutely must have the easiest password to type, about the best you are going to do is using a method called Diceware. Diceware™ is a method for picking passphrases that uses dice to select words at random from a special list called the Diceware Word List. Each word in the list is preceded by a five digit number. All the digits are between one and six, allowing you to use the outcomes of five dice rolls to select one unique word from the list. The list encompasses 65 or 7,776 unique words varying in length from 1 to 6 characters and averaging 4.2 characters. This provides 12.925 bits of entropy per word. If you select 5 words at random from the list using the Diceware method, that provides you 64.624 bits of entropy or 264.624 password combinations. You can add 10 additional bits of entropy just by inserting a single additional letter, upper case character, or special character resulting in 74.624 total bits of entropy for the password. All 3 options would give you 94.624 bits of entropy. I would highly suggest adding at least one number, one upper case character, and one special character to your final Diceware password. Attackers like to use something called rainbow tables to easily crack passwords. With a known word list, an attacker could easily assemble a rainbow table of pre-hashed 5-word combinations and find your password in a matter of minutes or even seconds. By making just a few minor adjustment as I suggested to the final password, you will render the rainbow table method useless. Generally, most password storage systems make use of something called Salt which also helps render rainbow tables ineffective. But, it is better to be safe than sorry.

References

  • Further good advice on finding a strong password can be found in the Password Haystacks article posted by Steve Gibson.
  • NIST 800-118 – Guide to Enterprise Password Management
  • Diceware – create strong yet easy to remember passwords
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: