Tuesday, January 20, 2009

Too much optimization

I just found a major bug in my dictionary based rainbow table program. The MD4 hashing algorithm I was using for NTLM, (though thank god not MSCACHE), passwords does not work for passwords over 14 characters long. I discovered this when attempting to build a table to crack strong, (16+ character) passwords. I'm kicking myself because this limitation was documented in the actual code. The fix is easy enough, (if > 14 then use old hashing algorithm), but going back it really messed up some of my older ntlm tables, (aka the old tables were generated using incorrect hashes for 15+ characters, so if I start hashing them correctly the old tables break). Normally at this point I would just change the version number of my new tables, (I tried to build some future proofing into my setup), but this also explains why my program was crashing on some other computers I was testing it on. Aka, on my development desktop it would just give garbage for those long passwords, while on my mac it give a full on seg fault.

I guess what I'm trying to say is A) I'm frantically trying to rebuild my NTLM tables before shmoocon, and B) You really need to read ALL the comments ;)

The plus is that my MSCasche, MD5, and some of my older NTLM (keyboard combo), tables are still good, and combined with what I can create after hyjacking a couple of my coworker's computer, I should still have a fairly good selection to release at Shmoocon.

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.