Embedded Files
Does password complexity actually increase security?
9 September 2023
Much of this blog post was informed by a class on cybersecurity technology that I took as a policy student at the University of Texas.
It feels like websites today want you to write a novel as your password. In this post, I'll explain the reasoning behind this policy and why it makes your online accounts more secure.
I'll do this by walking through what it looks like to crack a password. Imagine that you bank at Gringotts. The bank recently told you that it had a data breach and lost your account username and password. But don't worry! They encrypt all their data at rest, so your account is protected. They suggest changing your password, but you forget to. Three months later, you've been defrauded. Someone got into your account and used your payment info to buy $1,000 in Walmart gift cards. What happened?
We'll walk through it by pretending that I'm the hacker who defrauded you. An important jumping-off point is understanding that I'm most likely not the same person who breached Gringotts. Rather, that person stole the raw, encrypted data and then sold it to me (a different hacker). From there, I set out to decrypt your information and compromise your account.
A little bit about hashing.
Before I show how that works, it's important to understand a bit about cryptography. Cryptography is complex, so I will paint with a broad brush. But it's important because crypto techniques provide the fundamental tools that we use to protect our information and secure our communications. According to NIST, "[c]ryptography uses mathematical techniques to transform data and prevent it from being read or tampered with by unauthorized parties."
With passwords, this work is done by a hash algorithm. An algorithm is a logical process invariably followed to reach some target outcome.
Computer algorithms use a really cool type of math called Boolean algebra. Basically, computers turn everything into ones and zeroes, so the algorithms take the binary version of the text, conduct mathematical operations on it, and create a ciphertext version. In this context, we call this ciphertext version the “hash”.
How does this work in practice with passwords? When you created your account at Gringotts.com and entered your new password, Gringotts put that password through a hash algorithm and stored the output (the hash). This has the advantage of not only keeping your password secret in case the bank loses it, but it also converts all customers' passwords to a fixed size (better for storage). When you log in the next day and enter your password, the bank hashes the password again, and compares the new hash against the stored hash. If they match, then the bank grants you access.
How does password-cracking work?
The process is guess-and-check. Imagine that I want to steal your account at Gringotts. I would buy your hashed password from a hacker that had breached the bank's systems and stole their bulk, encrypted data. I would then take what I think your password is, run it through the hash algorithm, and compare the output to your hashed password that I bought from the hacker. If it matches, then I now know your password.
This is basically what is happening, just on a bigger scale. A password-cracker buys a massive list of hashed passwords, generates his own list of guesses, and has his computer hash all those guesses and tell him when he has a match. It is important to note that this is all happening on one computer. It's not as if the password cracker is at the log-in portal, trying all these combinations.
But how does the password-cracker come up with his guesses? There is discretion in this, but there are fundamentally two techniques: brute force and dictionary attacks.
With a brute force attack, I direct my computer to try every possible combination of characters until it finds a match. This method is almost guaranteed to work. The problem is that this can take a long time depending on how powerful your computer is.
Alternatively, a dictionary attack uses a predefined list of words that the hacker thinks are the most likely to match. With this method, I tell the computer to try those words first. Often hackers will use a list of previously-leaked, plaintext passwords.
Below, I'll demonstrate both of these techniques on four different hash algorithms. As you'll see, the methods have varying results, and the algorithms vary in their ability to protect data.
So, can I crack your password?
With this experiment, I'll start by hashing 10,000 real-world passwords using four different hash algorithms. I'll then take those hashes and run them through a password-cracking program that uses both brute-force and dictionary techniques. For each technique and hash function, I'll give my computer a maximum of one hour to find as many passwords as possible. At the end, I'll compare the effectiveness of the techniques and algorithms.
Password cracking, particularly using a brute force method, is highly dependent on computing power. For this, I’ll first use my personal computer, a PC with a 4-core Intel processor and 16GB of RAM. I’ll then rerun the program on a Google Colab virtual machine. If you’re unfamiliar with Colab, it’s a free service that allows you to run your code on a Google computer. They typically allow you to access nicer processors, something particularly helpful for machine learning. I’m rerunning the program on Colab to confirm that my computer’s speed is not a limiting factor.
Designing the Experiment: Hash the Passwords
I first hash 10,000 passwords using four different hash functions. I pulled the 10,000 passwords at random from the RockYou list. This list contains over 32 million passwords stolen from a social media company in 2009. It's the largest real-world password set available.
The four hash algorithms that I’ll use are MD5, SHA-1, SHA-256, and PBKDF2. The first two algorithms are some of the earlier hash functions developed. They are no longer used for passwords because modern computers have too easy a time breaking them. SHA-256 and PBKDF2 are both still used for passwords, although neither represents the true state-of-the-art. Hash functions are always improving.
Here are fifty of the 10,000 passwords that the program randomly selected from the RockYou list:
5847236, jocewom@n, 34rage, sample98, flutie637, PANGOLA1, snopysnopylore1981, jitter17, picnosaandpanda, glorialea, csbdsb511985, 11214344, j102879, 9-26-93, tat187, feb2908, lolliepop32, mcfly80808, flowertik8, yoserebarbie*100, khalyohali, sr2013, April191995, carnationn1_, sanane852456, 2028060088, zacharykeller, kinseypoo, katelynnpeterson, *parvati, hot116, 5267575, f27d689e, holasarita, 621048, heavenfamily, HArryRonJeremy, 4641dhsr, 09212138621, mosby's, 17935, b-ball3, 029954234, robin203, amoajulio23, nain771113, 5121699, Sunsh!n3, hoy96fax, 1659900180774
Define and Run the Password Cracking Program
The next step is to create a program to crack the passwords. As any good programmer would (and I'm not a good programmer), I adapted this from some of the scripts that are out there already. To be clear, I didn’t write this program. A search on GitHub for "password-cracking-tool" yields over two dozen results.
For those interested, I've embedded the program below. Overall, it's quite simple, allowing for only a few parameters to vary the techniques.
Results
Four minutes to crack 1,373 SHA/MD5 passwords.
Overall, there was a clear winner in PBKDF2. This program couldn’t guess any of the passwords hashed with PBKDF2 in the two hours that I gave it.
For the other three algorithms, brute-force attacks guessed 103 passwords hashed with MD5 and SHA-256, and 83 passwords hashed with SHA-1. Dictionary-based attacks guessed 1,373 passwords for each of those three hash functions.
There were some other valuable takeaways.
Random passwords are more secure. For three of the hash functions (MD5, SHA-1, and SHA-256), a dictionary attack uncovered 1,373 of the 10,000 passwords in about four minutes. As I mentioned, the dictionary method uses a list of passwords that I provided, comparing each entry on that list to the hashed passwords to find matches. My list had one million real-world passwords that people had used.
This suggests that if you want your password to be secure, you should make it unique. You don’t want to use a password that someone else has used before. If someone has used it before, it is probably in a hacker’s password dictionary somewhere. That means it will be one of the first ones that he tries in a dictionary attack.
This also suggests that you don’t want your password to be memorable. If it is memorable to you, it probably was memorable to someone else at some other time. That person probably got hacked, so the password is in a dictionary. Use a random password instead.
Longer passwords are more secure. This is particularly true when looking at brute-force attacks. My computer tried every possible combination of four characters or fewer in 90 seconds. But one hour was not enough time for the computer to try all combinations of five characters. Because we’re dealing with permutations, adding one digit will exponentially increase the number of possible passwords. This suggests that a longer password is usually more secure.
Special characters help. In the same vein, adding in special characters helps strengthen your password. This expands the “key space”: the range of values that the hacker must try. There are more combinations of letters in a 27-letter alphabet than a 26-letter one. When we get to passwords of ten to twelve characters, this creates substantially more potential passwords. Those additional possibilities will slow down a computer that uses a brute-force attack.
What does this show? There is a good reason behind why websites today want us to create long, elaborate passwords. They are more secure. But it can be hard to create unique passwords every time, then remember them the next time you have to log in.
The best option is to use a reputable password manager. Those services typically suggest a strong password for you, then store it so that you don’t have to remember it later. Recognizing that this is like putting all your money in one safe, the combination of convenience and security is likely worth it. You can (and should) use two-factor authentication to secure that account.
Google Sites
Report abuse