Rainbow Tables: The Password Conundrum Part 4
In part 1 of the Password Conundrum, we talked about how we all hate passwords and how we can never remember a strong, unique password for every website, system, and application that we use.
In part 2, we talked about how a password manager can solve this problem and make your digital life much easier and more secure.
In part 3, we explained multi-factor authentication and how to use it.
In Part 4, the final post in this series on passwords, we delve into rainbow tables. I think the best way to get people to create and use good passwords is to teach them how passwords are cracked. There are generally two main methods of password cracking: brute force, and dictionary attacks using a rainbow table. Brute force is simply guessing repeatedly until you guess the correct password. The risk of brute force guessing is greatly reduced if the server locks an account after a certain number of attempts, however there is a shockingly low number of sites that do this. The second and more interesting password cracking method is called a dictionary attack, which uses a tool called a rainbow table to figure out your password. It gets a little complicated to explain but I’ll attempt to take you through it now.
In part 1 of this blog series, I likened a rainbow table to a set of books filled with all of the words in the English language. Each word was written in uppercase, lowercase, mixed case and even using numbers and special characters to replace or append the words. That’s a good start, but let’s go back in time and learn a little history about how the rainbow table came into existence.
Long ago, when UNIX-like systems were used as shared servers and most people logged into them with “dumb terminals”, users could see who else had accounts on the system. This was convenient, especially in work or academic environments and acted as a directory of sorts. For example, if Alice wanted to send an email message to Bob, she would just log on to the system and look at a file called /etc/passwd. This file showed each person’s username, name, and other information. This file also contained each users password in the form of something called a hash. Trend Micro explains that, “Hash values can be thought of as fingerprints for files.” The hash is a mathematical representation of the password that cannot be reversed or un-hashed. This is a difficult concept for many people because we can add and subtract, we multiply and divided, we encrypt and decrypt, but we can’t hash and un-hash.
We won’t get into the technical details of how hashing works but one more thing to know about hashing is that it creates a fixed length result, no matter what you enter. In the image below, notice that each string of characters (input), whether it’s a single word or a sentence, gives an output (digest) with a fixed length. Also, you’ll notice that a slight change in the input, results in a drastic change in the output. This is good for passwords because if a small change in the password resulted in a small change in the hash value, an attacker would know to just try small changes.
Image courtesy of howtogeek.com
So back in those days, storing password hashes where everyone could see them was pretty standard. It was considered safe because knowing the hash wouldn’t get you the password and hashes are unique for every password. Below, you’ll see an example of what an /etc/passwd file might have looked like.
In the above example, you can see that each line has seven distinct parts.
Userid: The username of the account
Hashed password: As you can see, this is a fixed length
Uid: This is a numeric userid that is associated with the username in the first field. That way if you change your username from cybernewbie to cyberninja, the system knows that it’s the new name for the same account
Gid: This is a group id. This is used to differentiate and give different permissions to different groups of accounts. For example, root is 0, general users might be 10, the sales team might be 20 and the help desk might be 30. This makes it easy to grant, revoke or change permissions for an account based on a user’s role.
Gcos field: Enter whatever you want but this is usually where the first and last name go
Home directory of the user: This is where the user’s data is stored
The shell preferred by the user: This basically the user’s preferred set of commands or instructions
This method was reasonably secure and worked well back when systems had few users and before Internet connectivity was so prevalent. However, it didn’t take long for someone to figure out the weakness and to figure out how someone could possibly learn another person’s password. Can you figure it out by looking at the example picture?
Did you get it? If so, congratulations! If not, here’s the weakness. Let’s assume Al K. Seltzer is a rather curious chap and one day while perusing though the /etc/password file, he noticed that his hash was exactly the same as Jim Shorts’ hash. Realizing that this is just a representation of his password, and that hashes are unique for every password, he concluded that his password HAS to be the same as Jim’s password. Having more curiosity that scruples, Al decides to test his theory and tries to log in with Jim’s username and Al’s own password. Sure enough, it worked!
After a little bit of research, Al discovers that the hash that is being used is something called an MD5 hash and this is something he can run against any string of characters, right on his computer for free with a simple command.
$ md5 [string]
Now, Al takes this a step further and creates a list of words that he thinks would be common passwords and their representative hash values to see if he can discover anyone else’s password. His list is getting long so Al puts the passwords and hash values into a spreadsheet for easy searching.
This turns out to be a valuable endeavor so Al decides to automate this process using a script. Al gets a file that has every word in the English dictionary and writes a script that takes each word, hashes it and puts the word and the hash, in his spreadsheet. Viola! The rainbow table is born!
Below is a simple rainbow table that shows the MD5 hash for a few of the most common passwords.
Levels of Rainbow Tables
To further explain rainbow tables, let’s recap on one of the most important, yet crazy cybersecurity rules.
Use all character sets (uppercase, lowercase, numbers and special characters)
Why are they asking me to do this?
The answer is that the more character sets, the larger the rainbow table and the more storage, computing power and time it takes to crack.
Imagine that you are allowed to create a 1-character password on a site and it can only be lowercase letters. With this restriction, an attacker only needs to try 26 options. Now if that same password could be lowercase or uppercase, the number of tries doubles to 52 options. If you add numbers, there are 62 options. With special characters, there is about another 80, which takes us to 142 characters. As you can see, adding more character sets means that an attacker with only one set of characters in their rainbow table would be unsuccessful in guessing your password with that rainbow table.
Now let’s make this password better than just one character. I
f this was all numbers, as in a 4-digit pin, there are 10,000 options.
If you create a password with 6 digits, there are one million options.
If you use six lower-case letters, it jumps to more than 300 million options.
And if you use a combination of upper- and lower-case letters, you get 2 billion different combinations.
Add in special characters and the number of possibilities is in the hundreds of billions.
Remember that all of these options are stored in a database and a computer would need to compare the hashes of these options to your password hash. The smaller rainbow tables would run easily on a laptop, but a larger rainbow table—one with all four character sets and covers 8 characters—would likely require computing power and storage that is not available to most. As you can see, using all four character sets makes your password much more difficult to crack and the longer you make it, the more difficult it is to crack.
MODERN DAY
So how are rainbow tables used to “crack” passwords? When there is a data breach and a long list of usernames and password hashes are posted online, threat actors will first run through that list with various rainbow tables to see if they can match any passwords. Today this is more difficult because of three big changes from the “old days.”
We no longer store password hashes where any user can see them. The /etc/passwd file still exists, but it does not store the password anymore. Today, unix-like systems store password hashes in a file that is only visible to the administrator or root accounts. This is typically called /etc/shadow
Most modern systems have the option of adding something called a salt to the hash. Yes, it’s called a salted hash and the salt is just some random characters that are sprinkled on (added to) a plaintext password before hashing. As you can imagine, this makes it vastly more difficult to crack using a rainbow table, unless you can get the list of salts. Sadly, not everyone follows cybersecurity best practices so we see unsalted hashes more often than we would like.
We no longer use MD5 as a hashing algorithm for passwords as it has been found to mathematically have collisions, where having two inputs result in the same output. Modern hash values are much longer than the MD5 output.
If you want to hash some of your own passwords or passphrases, there are many websites that will show you the MD5 hash value of whatever you type in the box, as shown below.
Also, most operating systems have command line hash tools built in. If you’re interested in more information about hashing, check out this page. Also, if you want to hash some words or sentences on your own, here is one of many websites that give you that ability.
In conclusion, we have learned the following things.
We all hate passwords
Cybersecurity people are crazy and ask us to follow password rules that we just aren’t going to follow, unless forced to, and even then, we’ll find creative ways around it.
Using a password manager allows us to follow the crazy rules and not know any of our passwords! WOOHOO!!!
Multi-factor authentication gives us an extra layer of security so that even if someone figures out our 27-character password created and stored by the password manager, they still can’t log in!
Knowledge is power! Now that you know how passwords are cracked, you might not think those cybersecurity people are that crazy. Password cracking is not super easy, but it’s easy enough that you don’t want to make yourself an easy target. Use a password manager, implement MFA everyplace you can and know how to not be an easy target!
