Here’s Why Common Password Policies Are Ineffective

password_strength
xkcd comic that everyone uses when blogging about passwords.

Your employer’s password policies are stupid and you know it. If for some reason you love your employer’s password policies, then hopefully you will be disappointed by the end of this post, but first let me clarify which password policies I’m talking about.

Bad Password Policya haiku by Dan
Eight characters please.
Uppercase, number, special…
At least one of each.

So all that, plus having to reset your password every 30 or 90 days, and finally password lockouts after ten or however many incorrect attempts. But first, let’s get technical (like way more technical than you expected when you clicked this, but I’ll explain all of it like you’re five). I’m going to explain passwords, the math behind them, and the reality of cracking them in a way that hopefully everyone can understand.

Because this blog post is insanely long, I’ve provided a table of contents so you can return to where you were if you’ve taken a break or skip ahead if you’re already familiar with the concepts.

  1. How Passwords Work
  2. Password Cracking
  3. Encryption
  4. Hashing
  5. How Passwords Work In Real Life
  6. Password Cracking In Real Life
  7. A Good Password Policy
  8. How You Can Improve Your Security

How Passwords Work

So let’s say you want to order a great book on starting your own company or a cute book of super-short stories on Amazon. On the login screen you type your username and password and events similar to the following take place:

  1. You, the client, send over your username and password to Amazon, the server.
  2. Amazon pulls your records, including your password, by matching them with your username.
  3. Amazon compares the password it has stored with the password you entered.
  4. If the passwords match, Amazon responds to your request to log in with a success message. If the passwords don’t match, Amazon responds with an error message.
  5. If the log in is successful, you go on buying one of the items I just linked to so I can get some $$$ please thank you.

Seems simple enough. Next section.

Password Cracking

d4b07ed6d1d74838536d66dbb2c9d676
Actual photo of hacker manually trying 30 passwords before giving up and getting Taco Bell.

Here’s where it gets interesting. Let’s say I’m looking for a quick way to make some cash or I want a new TV. I find a list of email addresses somewhere online, and decide to try and see if I can guess their passwords.

I load up a list of ten thousand of the most common passwords (available for download here) into a simple program that just tries to log in to each email on the list with all of the ten thousand passwords, a method otherwise known as password cracking.

A few emails on the list match, awesome! I take the first email, and as much as I want to send a message to that person’s boss and tell them about how much my victim loves tickling ferrets, I instead decide to go to Amazon’s website to check if they have an account by logging in with the same email address and password that I just cracked. We have a match, so I ship a bunch of ferret toys to my victim’s boss and order myself a new TV to an abandoned house in the next town over and go and pick it up when it comes.

Alternatively, if I were more aggressive and the passwords didn’t match, I could click “forgot password” and enter the email address I just broke into. A recovery link gets sent to the email address so I log in, click the recovery link, and update the password.

amazon

There are actually many different scenarios that could happen instead, depending on how aggressive I am and if I care about being discovered:

  • I could crack Amazon accounts with the email/password combo instead of the email site (like Gmail, Hotmail, etc).
  • I could crack banking site accounts and transfer money to prepaid cards.
  • I could crack insurance site accounts and grab social security numbers and other personal information which I can then sell or use to open credit lines.
  • I could crack payroll site accounts to download W2’s and steal tax returns.
  • I could crack social networking accounts and spread malware or spam and indirectly make money that way.
  • I could crack someone at a political campaign, send malware to the candidate from someone he trusts, and compromise his machine to meddle with his campaign or sell information.
  • I could crack celebrities’ iCloud accounts to try and find nude photos which I can then sell or publish.

In real life however, cracking is a little different than how I described. Account lockouts and password complexity requirements are meant to mitigate the tactics I’ve mentioned above. Additionally, sending a login request to target sites over the Internet can be slow, and that slowness would scale when sending several thousand requests, one for each password attempt. Unfortunately, none of these mitigation techniques or challenges are actually relevant or effective anymore, and I’ll get to that a little later.

Hashing

Okay, here we’re going to get really technical and call in our friends Alice and Bob to help us. Before I explain hashing, I’m going to give a brief summary of encryption so that you learn the difference between the two and so that you can understand the world of information security a little better.

Okay, encryption then!

Alice and Bob are in class together and Alice wants to send a message to Bob, but Alice is sitting far from Bob. Alice writes her message on a piece of paper, and asks the person next to her to pass it along to the next person and so forth until the message reaches Bob.

Note from Alice: party at my place tonite u down?

Alice doesn’t realize that Eve is eavesdropping on their conversation; the notes pass through Eve’s desk and she opens them before handing them to the next person. Alice and Bob soon realize this and devise a plan to obfuscate the notes so Eve can’t read them.

The plan they come up with is this:

  1. Convert each letter to a number using the alphabet as follows: A=1, B=2, C=3, etc.
  2. Add 5 to each number.
  3. Convert back to letters.

The steps above are borrowed from an actual encryption algorithm known as the Caesar cipher, used by Julius Caesar to obfuscate his messages communicating strategic military advancements.

Alice sends another message to Bob the next day in class.

Encrypted note from Alice: Gwnsl f pjl

Eve opens the note up and is now confused, but Bob can read it just fine by decrypting it using the reverse of the algorithm they’ve devised (convert letters to numbers, subtract 5, convert back to letters), so the plan works. However, Eve copies the note on another piece of paper before passing it on, and attempts to decode it at home later that night.

81888416
Eve seriously it’s not rocket science.

Eve figures the algorithm out and the next day in class she’s able to decrypt the messages that Alice and Bob are sending.

Decrypted note from Alice: Bring a keg

Alice and Bob catch on to this and that weekend they decide to change the offset from 5 to another number. That offset number now becomes the encryption key. Put the note and key into the algorithm and you get an encrypted result, or ciphertext. Choose a different key and you get a different ciphertext.

Now, notice how if you take the ciphertext and apply the reverse of the algorithm to decrypt it, you get the plaintext? This demonstrates that encryption is a two-way function, meaning you can use the key and algorithm to encrypt plaintext and get a unique ciphertext, and decrypt the resulting ciphertext to get the original plaintext with the same key.

Below is an example of what a real-life ciphertext would look like if using a common and secure encryption algorithm (AES-256).

ferrets
You can play with this tool and encrypt stuff yourself here. Circled in red from top to bottom: plaintext, key, ciphertext.

Congratulations, you’ve just learned the basics of encryption!

Hashing

Let’s build on the previous example.

Eve is getting pretty good at figuring out the encryption keys Alice and Bob are using. Eve can figure out the key Monday night and decrypt messages for the rest of the week, since Alice and Bob’s key exchange happens in secret on the weekends.

Alice and Bob devise a new plan where Alice writes the key on a note and slips it into Bob’s locker before class so no one else can see, so when Bob comes in he can decrypt Alice’s encrypted messages. Now the key changes every day, and Eve is spending every night figuring out the daily keys but still misses all the parties.

Eve’s friend, Mallory, sits in the back of the class and while the notes Alice sends to Bob don’t go through her, she’s been quietly observing what’s going on. Mallory understands Alice and Bob’s new key exchange at Bob’s locker, and one morning Mallory comes in after Alice, breaks into Bob’s locker, and copies Alice’s key.

In class, Mallory uses Alice’s key to send a note to Bob, who then decrypts it, thinking the notes are coming from Alice. Now, Mallory is telling Bob to invite other people to his parties and Alice soon realizes this is a problem. She needs a way for Bob to be sure the notes are coming from her and not Mallory.

106
Mallory and Bob (left, middle) are now planning parties and Alice (right) is not amused.

Alice, being way too smart for fourth grade, decides to create an algorithm or function to generate a key using a passphrase. The hash function is as follows:

  1. Pick any English phrase at least 10 letters long.
  2. Convert each letter to a number using the alphabet as follows: A=1, B=2, C=3, etc.
  3. Add up all of the numbers.
  4. Divide by the number of letters in the original phrase. Basically, we’re finding the average of all of the numbers.
  5. Round up, and the resulting number is the new key.

I’ve provided this handy chart to help us:

number-of-letters-in-alphabet-2itlyfl

A sample conversion:

  1. Phrase: FERRETLOVE
  2. FERRETLOVE = 6 + 5 + 18 + 18 + 5 + 20 + 12 + 15 + 22 + 5
  3. The sum of those numbers is 126.
  4. FERRETLOVE has 10 letters, 126 / 10 = 12.6
  5. Rounding up, our result is 13.

Using the example above, our hash function with the input FERRETLOVE gives us a hash of 13. We can use this hash function on any phrase, and it’ll give us an input within parameters we want defined, which in this case means a number less than 26 so that we can use it as a key (since there are 26 letters in the alphabet).

So how does this all help Bob verify that the notes he gets in class are coming from Alice and not Mallory? The first note Alice sends Bob in class is the phrase she uses to generate her key (keep in mind Mallory can’t intercept notes, she can only send notes to Bob). When Bob gets Alice’s first note, he’ll use the hash function and compute the result, and then compare that with the key Alice put in his locker this morning.

Mallory doesn’t know the password, so she tries to guess TURKEYLOVE, but since the hash (16) doesn’t match Alice’s key (13), Bob knows to ignore the notes coming from Mallory’s direction.

And that, my friends, is the basic idea behind hashing. With encryption, you can use the same key to encrypt and decrypt messages, but hashing is a one-way function, meaning even if you know the hash, you can’t get the original text no matter what. Hashing has many uses, including verifying the authenticity of messages (digital signatures), comparing two files, and storing passwords.

In real life, hashes are longer than demonstrated above and the hashing algorithm is more complex. SHA-1 is a common and secure hashing algorithm; below is an example of what an actual hash would look like.

sha1
You can play with this tool and hash stuff yourself here.

How Passwords Work In Real Life

In the example above, Alice devised a scheme to create a password so that Bob could authenticate Alice. When Mallory provided the wrong password, Bob knew it wasn’t her and stopped taking her notes. This is all similar to how password authentication works in real life; I’ve provided a more realistic scenario below:

  1. You enter your username and password in the login form.
  2. Amazon’s code creates a hash of your password in your web browser, the client.
  3. Your web browser sends the request with your username and password hash to Amazon, the server.
  4. Amazon pulls the hash of your password by matching it with your username, and compares the stored hash with the one your web browser sent.
  5. If the hashes match, Amazon responds to your request to log in with a success message and authorizes you to use their services. If the hashes don’t match, Amazon responds with an error message and denies you access to their services.

So the server, and by extension the service you’re using, should never actually store your password; they store the hash of your password. The keyword there is should; unfortunately, some sites store your password in plaintext, and that’s a huge mistake, as security breaches of user databases are not uncommon.

Have I Been Pwned? is a website that let’s you check your email against known password dumps released by hackers who have compromised popular services, including LinkedIn, MySpace, Dropbox, and Ashley Madison.

linkedin.png
Have I Been Pwned?‘s description of the LinkedIn breach in 2012.

In many cases the password dumps are posted on Pastebin by the hackers themselves, sometimes in an attempt to sell the credentials on the black market:

breach.png
An example of a Twitter password dump that the poster is trying to sell for 0.5 bitcoin, with the first 100 accounts included to prove authenticity. Original paste here.

Some services store their password hashed, but they don’t add a salt, which is merely a random string that you add in front of or after the plaintext password before you hash it. If you read the LinkedIn breach’s description on Have I Been Pwned? you’ll notice that the passwords were hashed with SHA-1 and weren’t salted, which is not good security practice. I’ll explain why a salt is important, and why SHA-1 isn’t the best algorithm for passwords, in the next section.

Password Cracking in Real Life

Okay, now we’re getting to the good stuff. There are quite a few ways to crack an account and by the end of this section you’ll become familiar with a couple of them and will understand password security a great deal more.

Guessing

This attack refers to literally just guessing the password. Many times attackers that have some familiarity with the victim or their habits can come up with pretty accurate guesses for passwords, such as birthdays, pet names, or really common passwords like “password.” This can be mitigated by choosing hard-to-guess passwords, and no, that doesn’t mean “password1.”

Dictionary Attack

Dictionary attacks involve trying every word in the dictionary as the password. The “dictionary” used could either be every word in the English language, the most common 10 million passwords, or any other arbitrary list of passwords that would have a good chance of containing the password the attacker is trying to crack.

pwlist.png
Sample from a top 10 million most common passwords list. You can download this list and other dictionaries here.

Many password cracking tools allow for fuzzing, meaning if the target word is “dictionary,” the tool will try different combinations with letters and numbers, such as “d1ct10n4ry,” “dict1onary,” “d1cti0n4ry123,” etc. Many users think they’re being clever by using schemes like this, but attackers know this and the affect on performance by adding different combinations to password lists is, if not negligible, likely worth it to the attacker if the chances of guessing the correct password is higher.

Sometimes, context is necessary. For example, if Example Bank’s password requirements require a password of at least 8 characters and exclamation points are prohibited, the attacker would try a list of passwords that are 8 characters or longer and don’t contain exclamation points. The performance benefit of excluding unnecessary password guesses could scale when dealing with a password list of millions of passwords.

Because many services have a rate limit on how many login attempts users try within a period of time, dictionary attacks and the attacks below may be attempted on the hash of a password rather than trying to log in with each password on the list. This means that each word in the dictionary is hashed using the same scheme as the actual password, and the dictionary hash is then compared with the real password hash to check for a match. The password hash is usually attained through a security breach or other malicious means like eavesdropping on a wireless network or retrieving a stored password hash from the victim’s computer.

Brute Force Attack

A brute force attack means literally computing every alphanumeric character combination available. Let’s say the attacker knows the password is eight to twelve characters long and contains numbers, letters, and special characters; a brute force attack might try the following passwords:

  1. aaaaaaaa
  2. aaaaaaab
  3. aaaaaaac
  4. aaaaaaad
  5. aaaaaaae
  6. …and so on…

Like dictionary attacks, because of the number of passwords attempted, this attack is more likely performed on the hash of a password rather than with a login request to a website or service.

Rainbow Table Attack

Every unique combination of characters has a unique hash, so you can say that hash functions are one-to-one in that each input has a corresponding output. The SHA-1 hash for “ferrets” will always be “ff43837c5754a9ac639368712b67c87ead422391”, and if you use another common hashing algorithm, MD5, the MD5 hash for “ferrets” will always be “45225EA1BE970C37C4EBD4B443CD267E”.

Hackers understand this, and have created rainbow tables to help facilitate cracking. Rainbow tables are enormous lists of character strings and their corresponding hash, all pre-computed. Instead of going through each word in a dictionary, the password hash is compared to all of the hashes in a rainbow table, and if a match is found then the original password is known as well. This method is significantly faster than dictionary or brute force attacks, so some attackers might actually try this before other types of attacks.

rainbowtables
A list of rainbow tables generated by the RainbowCrack team. RainbowCrack is a password cracking tool that uses rainbow tables to match computed hashes to plaintext passwords. The tables shown are for sale; they can be purchased via Paypal and are loaded onto a USB dongle and shipped via FedEx. More details here.

The image above shows a list of rainbow tables for sale. The reason a rainbow table must be downloaded or purchased is because computing rainbow tables is incredibly resource-intensive and can take days depending on how comprehensive the dictionary you want to compute is. Though, now with cloud services like Amazon EC2, it can be computed in much less time.

This is where a salt comes in. A salt is typically a random string of fixed length prepended or appended to the raw text before hashing. For example, instead of computing the hash for the raw password “ferrets,” the hash is computed for the salt + password: “7c%ferrets.” This all means that the resulting hash for a salted password can be different for any unique salt. Salts render rainbow tables useless because rainbow tables only account for standard unsalted words or character strings. To perform this attack on salted passwords, an attacker must compute an entirely new rainbow table taking into account the salt, which the attacker also needs to obtain. Additionally, the salt can be changed on every login, and computing a new rainbow table for each new salt would be computationally infeasible. Simply put, this method would not worth pursuing for the attacker, especially considering the password hash might not even be in the rainbow table!

A Good Password Policy

Now that we have this wealth of knowledge, how can we apply it to a sensible password policy that any service, website, or organization can institute? Good question, you’re reading the right blog post!

Hashing Passwords

One might assume that SHA-1 is good to use for hashed passwords, and in response I might quote President Donald Trump:

“WRONG!”

Actually, SHA-1 is a pretty quick algorithm, which is precisely why it’s not great for hashing passwords. We want an algorithm that’s resource-intensive and slow. This is because when an attacker is executing a dictionary or brute force attack on a hash, the attacker must hash each password attempt in the same way that the victim’s password is hashed and stored in the database. If the passwords are stored as SHA-1 hashes, then the attacker must convert all of his guesses into SHA-1 hashes and compare with the SHA-1 hash stored in the database. Each guess will take longer if the attacker needs to convert each guess into a hash using a slower algorithm. With 10 million password guesses, a mere 0.01 second delay with each guess would extend the total cracking time by 27.7 hours.

Additionally, for added security, the hashing algorithm used for the password could be iterated any number of times, meaning the password could be re-hashed 10,000 times with the same algorithm for an even longer hash duration.

Two recommended password hashing algorithms are bcrypt and PBKDF2, which stands for “Public Key Derivation Function 2.” As you might have guessed, PBKDF2 supersedes PBKDF1.

Storing Passwords

Now that we know which hashing algorithm to use, we can talk about how to store them. It’s actually pretty simple, you store the hash of the password next to the salt in a database. It doesn’t matter if the salt is not stored securely; it is only meant to prevent a rainbow table attack, whereas the hashing algorithm is meant to prevent a brute force or dictionary attack.

Most implementations of hashing algorithms, including PHP’s, automatically generates a random salt and the output of the function includes both the salt and the hash. The implementation then provides a way to compare the password provided by the user with the hash in the database, so these days using a secure storage scheme for passwords is relatively easy to do.

Account Lockouts

It’s stupid, don’t do it. It makes no sense. An attacker can easily disable any account, including the CEO of your company, by sending ten or twenty failed password attempts; this is not good security! A slow hashing algorithm combined with a salt will prevent brute forcing, so why do we still need lockouts?

Password Expiration

My opinion is that password expiration maybe every six months is reasonable. 30 or 90 days is too often; users will start forgetting their passwords, and this slows employees down from doing their jobs and will cause users to be impatient. Availability of services and information is one of the pillars of information security, and forcing users to reset their passwords too often is putting additional strain on the availability principle. Well, in my opinion anyway.

How You Can Improve Your Security

Finally, the last section. Hopefully if you’re developing a website or service you keep the above principles in mind; that way, the passwords are stored securely, so even if a breach occurs, no one’s account is at risk and the users can be notified that they should reset their passwords.

But how can you, the client, secure your passwords? The most important factor is length; the longer the password, the longer it will take an attacker to crack it. Complexity also helps.

Let’s take a look at some numbers. The number of permutations for a given password is calculated by the following formula:

nlength

As an example, if we’re only taking into account lowercase letters for a 3-character password, the number of combinations would be:

26 * 26 * 26 = 17,576 password permutations

For each character added, the number of permutations goes up exponentially:

26 * 26 * 26 * 26 = 456,976 password permutations

That’s a big difference! Typically though, passwords don’t only consist of lowercase letters. They include numbers, uppercase and lowercase letters, and special characters.

asciifull
Here’s an ASCII table to help us calculate how many characters are in the allowed password character set.

Using the table above, we can see that character 32 (space) to character 47 (forward slash) are all special characters that can probably be used in a password, so that equates to 15 special characters.

Now let’s calculate the number of characters in an allowed character set:

  • Lowercase letters – 26
  • Uppercase letters – 26
  • Numbers (0-9) – 10
  • Special characters – 15
  • Total = 26 + 26 + 10 + 15 = 77 total characters allowed in a password

Great, now let’s say we want to calculate how many permutations in an 8 character password:

77 * 77 * 77 * 77 * 77 * 77 * 77 * 77 = 1,235,736,291,547,681 password permutations

That’s a lot of guesses for an attacker! But with today’s technology, how many passwords per second can an attacker go through in a brute force attack?

Well… it’s hard to say, but Random ize has a pretty cool tool that let’s you check how quickly your password can be brute forced, though I can’t seem to find what metric they’re using and against what algorithm (some use MD5 or SHA-1 as opposed to bcrypt or PBKDF2).

8charpassword
An eight-character password could be brute forced in a matter of days, according to Random ize.

According to the tool, a password eight characters long could be brute forced in a matter of days, but just like the number of permutations goes up exponentially for each character, the length of time to brute force a password goes up exponentially as well. Adding just one character to that eight-character password brings the time up to over 4 months, while a ten-character password would take over 23 years to crack. Eleven characters? According to the tool, over 1,500 years.

I think in terms of security, password length is more important than complexity, as long as you don’t pick an easy password, like a word in the dictionary or a name or sequence of numbers. You should pick something that’s complex and contains lowercase letters, uppercase letters, numbers, and special characters to maximize the size of your password’s character set, but I don’t think it should be a requirement for any kind of user. Even with the requirement, the user can set the password “Hello123!” which abides by the rules yet is hard to remember and easy to crack.

In my opinion, the password complexity stipulation should be the responsibility of the user. The only requirement a server or administrator sets should be the length of the password, and he or she should encourage users to pick longer passwords that aren’t easy to guess.

Additionally, you should not use the same password for all of your accounts. Password safes are a good idea to use to help you manage your passwords. You can read more about password safes and Lifehacker’s top recommendations here.

To conclude, let’s revisit that xkcd article from the very beginning; I think after all of this new information you’ve ingested, it might make some more sense.

password_strength

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