Monday, 4 April 2016

Rainbow Tables

I often see people talking about rainbow tables in lectures and seminars and just getting it wrong. If you have a dictionary of words and their precomputed hashes, then this is a hash lookup table, and there are plenty of free services that will allow you to check the hash that you have obtained against their database to see if it has been cracked before.

A rainbow table, on the other hand, consists of precomputed "chains" of hashes, where a reduction function is repeatedly performed on each output hash along the chain to create a new password candidate according to the desired length and complexity. Once a chain is complete, which is typically thousands of hashes long, only the start and end hash are stored in the rainbow table.

There are instructions online for generating your own rainbow tables or for downloading or purchasing precomputed rainbow tables. This effectively allows any password within a given character set and length to be cracked in a very short space of time, as long as it has not been salted, and as long as you have the storage available for your rainbow table.

When you have a hash for which you wish to find the password, you begin by running the same reduction function on it repeatedly until you match the end hash for one of your chains. You then start the repeated reductions again from the start of that same chain until you find the hash that matches the one you wish to crack. At this point you have successfully guessed the password, if all has gone according to plan. Software such as rtgen will do all of this for you and it is much quicker than a standard brute force, and will take far less storage space than a complete hash table for a character set.

No comments:

Post a Comment