Tuesday, January 13, 2009

Dictionary Based Rainbow Tables

I'll be officially releasing drcrack at shmoocon but I'd like to spend a bit of time talking about it first. If you want to obtain the code or some of our pre-generated tables feel free to pick them up here. The short explanation of it is that drcrack is a modified version of the rainbow table generation program rcrack. It allows an attacker to create rainbow tables based on dictionary words and mangling rules. What does this mean? Well against unsalted hashes it will allow an attacker to save their work and reuse it on future cases, reducing the time it takes to audit a password from days/weeks/months down to minutes. This gives the attacker the opportunity to try much more sophisticated mangling rules.

I've been working on this project off and on for about a year and a half, and it's been fun watching it evolve. Originally it was very limited in the dictionary/word mangling rule selection as I tried to minimize the time it takes to select the proper rule to use for each step. I eventually settled on a slightly slower method that gives the user more options though.  Also, I'm fairly proud of the method for letter replacement as that was a major stumbling block, (aka how do you avoid trying replacement rules such as swapping an '@' for an 'a' on words that don't have those characters?). Additionally, I originally replaced all the un-optimized hashing functions with slightly betters ones taken from John the Ripper. Later I dropped those in favor of even faster ones from the rcracki project found at www.freerainbowtables.com.  In fact, they work so well, I've been thinking about modifying John the Ripper to use them.

Why yes, I am bragging!

I have found some limitations though that I'm still working on. First of all, full case mangling is still not supported, (aka trYiNG AlL CaSes). Note, basic case mangling is supported though, (UPPERCASE, Capitalization, lowercase, lasT letteR). I have a plan to fix this but quite simply the chances of it being done by shmoocon are remote. Second, drcrack is very sensitive to the dictionary used as duplicate guesses can cause chains to merge and work to be wasted. For example, I was trying to build a table that combines different keyboard combo's such as qwerty, 12345, awds, etc. The problem was that certain shorter combos match longer combos when combined.  aka if you combined "qwerty" + "uiop[]\" it would create a collision with the single combo "qwertyuiop[]\" which is just someone going across the top of the keyboard. Also you have to be careful to remove duplicate words from your input dictionary and for word mangling rules to not generate duplicates. An example of this would be if you had the word "Password" in your input dictionary, and tried the rules "No-op, try as is", and "Capitalize the first letter". If you use both those rules they will generate a collision as it creates the guess "Password" twice. Looking back on it, I should have put in a safety factor that says if a rule, (besides No-op) does not modify a word, then throw in a junk result, (aka hash "Password-Error-No-First-Upper"). I might still do that in a later version, but the problems with rainbow tables is that by making that change my old tables would no longer work. It's not the end of the world as I could put a version check in, but I'm still debating that.

As always, if there is anything you would like changed or added, (or heaven forbid you find a bug), please let me know.

No comments: