Skittle advocates would blast me for applying their beloved slogan to something as sinister as password cracking. “Down with Martyr2!” or “Lets rip off his head and feed it to the lions! But we don’t have lions, ok, feed it to the bin of mutated rats growing a human ear!” The truth of the matter is that understanding the processes of password cracking can help protect and safeguard our electronic possessions. One such method for password cracking is through the use of Rainbow Tables. Rainbow tables allow computers to create a dictionary of random words which are hashed and reduced (through the use of a Surjective function) to form chains. We will cover the idea behind rainbow tables on this entry of the Programming Underground!
Before I start, I wanted to say I am not going to be providing source code for how to make a rainbow table, or its related reduce functions, and how to crack a password. But if you are wise beyond your years, you will gain knowledge and understanding of how it is done. Normally we don’t encourage this type of radical “hacker” stuff but the limitations behind a rainbow table makes it relatively safe to explore from a theory standpoint. I will explain why shortly.
As eluded to above, the idea of a rainbow table is to create a series of chains. By first guessing a random password (like a word from a dictionary) and hash/reduce it into other words. Old methods would have then stored each word and its hash equivalent making for huge dictionaries which take a long time to use and lookup words. Maybe a job for Google? Who knows.
The change with rainbow tables is that we store the beginning guess word, then hash and reduce it several times into a resulting end word which we store with the guess word. So each chain is represented by two words after several hash and reduce calculations have been completed. The beauty of this is that we don’t need as much storage for all the words we want to use. The chain could be 20 words long but still be represented by two words in a file. It could be 100 words long and still be represented by two words in the file. Below is an example…
Martyr2 (hashed) -> dkhe21 (reduced1) -> Skyhawk133 (hashed) -> uehs45 (reduced2) -> Amadeus (hashed) -> jshe34 (reduced3) -> Experts
We would then store in the file the words: Martyr2 Experts
So we have 3 potential passwords stored as 2 words in our file. As you can see we could go on and on with a single change and store it as two words in the file. Pretty straight forward huh? Now to the cracking!
Lets assume we gained access to a password file where all the passwords were encrypted with a hash algorithm. In the list of hashes we want to crack the one for one of the accounts, to remove gold from a rival clan’s WoW account. After all, he probably deserved it for attacking your friend in game. No one messes with your clan am I right? So you find his account password and it is the hash “uehs45”. Lets rainbow table hack it!
First off we are going to reduce it using the LAST reduce algorithm in our table (which we used in the construction of our chains).
GoodtrySucker <- (reduced3) uehs45 We would look up that password in our chains second word. Nope, not there. Lets hash it and reduce it again using the second to last reduce function. Experts <-jshe34 (reduced3) <- Amadeus (hashed) <- (reduced2) uehs45 We compare the word and this time, AH HA! we have it in our file. Now he is ours! So we take the beginning guess word associated with the word "Experts" and reform the chain, each step using the hashes formed in the chain against his hash. We take the first guess word "Martyr2" and start constructing the chain again in the same sequence we used to put it in the file. When we find the hash that matches, the word used to generate that hash will be the password. Martyr2 (hashed) -> dkhe21 (reduced1) -> Skyhawk133 (hashed) -> uehs45 (AH HA! We found the match, the password is Skyhawk133!)
Now for the few limitations to this procedure. First of all, it takes a bit of time to construct a really nice rainbow table. Even at the speed of modern computers, forming some really big tables could take a bit of time. Secondly, the reduce function you use is specific to the size of the hash. So you are going to have different reduce functions for hashes that are 6 characters (in our example) and something like MD5 hashes (which are 32 characters). Third, the reduce functions will have to take into account languages if the hashes could be using a different character table. Fourth, this method only works with plain text passwords which do not use any salts. Salts are random bits inserted into a hash along with the password to form a more complicated hash. A salt could be random numbers or characters of any length and of various complexity. The resulting hash is then harder to find and would bog down even the most elaborate rainbow tables. Making it nearly impossible to use a rainbow table at all and why you don’t see them used beyond anything that has a standard plain text password (like earlier version’s of windows used).
Even if you were able to find a match with a salt included, you would have to be able to then remove the salt from the hash before you could correctly find the encrypted password. This is why I figured it was ok to discuss the theory since a good salt pretty much defeats this process by bogging it down to infinity.
Either way the process is interesting and could still be sued to break those little messages people send to their friends that might be encoded in a weak custom made hash. Just don’t expect to be going in and attacking the CIA with it because they are going to swat you down like a fly.
In short, if you are every bored and want to feel like a rebel maybe you could implement such a table and test it against your own hashes for security. This, and a brute force attack, would be two good ways to test a hash’s strength.
Now where did I put that bag of skittles? Oh well, as long as I don’t find them warm under a couch cushion I am fine.
Thanks for reading! 🙂
DISCLAIMER: The Coders Lexicon takes no responsibility in what readers use with the information provided. It is meant only as an educational tool in programming security theory and any use of this information against foreign or domestic targets will be the sole responsibility of the reader them self. Please exercise caution.
