Password Cracking – Part 8 – Rainbow Tables

What are Rainbow Tables?
Rainbow tables are lookup tables that contain almost every possible combination of passwords in a given character set. It is simply a completed brute force attack that you can reuse as many times as you wish without having to regenerate all those possible password combinations. This can reduce password cracking time by up to 99%! Of course, to generate a rainbow table it can take longer that it would take to crack one password, but afterwards you will be able to crack others in a few minutes compared to hours. Now that you have a basic idea of what rainbow tables are, let’s look at exactly how they work.
If you recall, I said that rainbow tables store most of the possible hashes in a given character set. This is true, but not in the way you might think. Depending on the character set and length of the password, a rainbow table can get extremely large. Below is an example of tables from the RainbowCrack Project:











If the rainbow stored every hash for every plaintext word in a given character set, it would use more memory then you have or can imagine. Instead, rainbow tables use a time-memory trade off technique, known as chains.
To understand these chains, you must first understand the “reduction function”. As you’ve learned, hash functions map plaintext words to hashes, well, the reduction function maps hashes to plaintexts. You might be thinking, didn’t you say that you couldn’t reverse a hash function and get the plaintext from it? True, the reduction function doesn’t inverse the hash function acquiring the original text. No, instead it gets another plaintext from the hash. For example, if we have a set of plaintexts that are made up of 7 numbers [0-9], using the md5() function a possible hash could be MD5(1234567) -> fcea920f7412b5da7be0cf42b8c93759. In this case the reduction function could be as simple as taking the first seven numbers from the hash to generate a new plaintext. So once the reduction function was applied to the hash, it would result in the new plaintext, “9274125”. And that’s what the reduction function does, generates a new plaintext from a given hash.
These chains that make up rainbow tables are made up many combinations of the one way hash function combined with the reduction function, making a chain. For example, if we were to continue the chain from the first example, it would look like this:
Md5(1234567) -> fcea920f7412b5da7be0cf42b8c93759 ->
Reduction(fcea920f7412b5da7be0cf42b8c93759) -> 9274124 ->
—————————————————————————————–
Md5(9274124) -> ed7db1cf7fc4fbd0169f00c37a0165ab ->
Reduction(ed7db1cf7fc4fbd0169f00c37a0165ab) -> 7174016 ->
—————————————————————————————–
The above chain would keep repeating until you or the rainbow table maker decides to stop it, usually after millions of hashes are created. Now here’s how rainbow tables save memory. Instead of storing every one of these hashes, the rainbow table only stores the first plaintext and the last hash in that chain. Then millions of more chains are created, each representing millions of password hashes. If a table was made up of the above chain, then it would be made up of its first plain and final hash looking something like this: 1234567 -> ed7db1cf7fc4fbd0169f00c37a0165ab.
Once enough tables have been generated (millions), you will want to actually use the final rainbow table to crack a password hash by checking to see if it is inside any of the generated chains. Here is the algorithm:

• Check to see if the hash matches any of the final hashes. If so, break out of the loop
  because you have found the chain that contains its plaintext.
• If the hash doesn’t match any of the final hashes in the tables, use the reduction function on
  it to reduce it into another plaintext, and then hash the new plaintext.
• Go back to step 1.

Now that you know which chain contains the plaintext, you can start with the original plaintext of that chain and start hashing and reducing it until you come to the password hash you are trying to crack and its secret plain text. There you have it! The quickest and simplest explanation of rainbow tables that you will ever find!
When should I use a rainbow table?
If there are rainbow tables available for the type of password hash(es) you have, then use it! Chances are it’ll work. If you have to download the tables, then while that’s going on, trying a dictionary attack won’t hurt.
If the passwords are salted, then you probably will not want to use rainbow tables because you will need to create a new rainbow table for every password. Why? Well, if you recall, when you salt a password, you add a random or unique string to it and then run it through the hashing function. So if the password was “password” and the script attached the user’s username to it, the final password would be MD5(“username”+”password”). Since everyone has a different username, the word “password” will never look the same once hashed.

Password Cracking – Part 7 – Hybrid

What is a hybrid attack?
A hybrid attack is a mixture of both a dictionary and brute force attack. That means that like a dictionary attack, you would provide a wordlist of passwords and a brute-force attack would be applied to each possible password in that list.
A hybrid attack is like the beginning of an MMORPG where you choose your character design. Your figure stays the same but you have the choice to change your clothes, hair and color until you have the look you want, a badass Schwarzeneggar or a medieval hooker.
On my first day as a freshman in high school, I was given a username and password for the school’s computer network. Everyone’s password was set to the first initial of their first name, their last name and birth date. So if my name was Bob Sagat and I was born on May 22, 2010, my password would be “bsagat052210”. This wasn’t a great way to distribute passwords, but we did have to change it after we first logged in. Can you see why a hybrid would be an effective attack in this case? What I could have easily down was get a list of every freshman student in the school and apply a brute force attack to the end of each name. The rule would look something like this:
(first initial of first name)(last name)([0-9] [0-9] [0-9] [0-9] [0-9] [0-9]) In this case, a hybrid attack would have enabled me to crack every single student’s password within a few minutes.
When should I use a hybrid attack?
Use a hybrid attack whenever you have an idea of how a password is formatted. For example, if you dump a database of password hashes from a website, and after trying a dictionary attack against it you are left with many uncracked passwords, then take a look at the password requirements for that website. Many websites require a password to be made a certain way. For example it may require a password to have at least two numbers and a special character. Knowing how people like to make things as easy as possible for themselves, you can safely guess that many people used exactly two numbers and one special character. Armed with this knowledge you can go back to your dictionary file and apply a brute force attack to it (making it a hybrid attack), trying the following combinations:
([0-9] | SC) ([0-9] | SC) ([0-9] | SC) (password) or
(password) ([0-9] | SC) ([0-9] | SC) ([0-9] | SC) Where SC = Special Character (ex. !,@,#,$) and (| = or).