Intrepidus Group
Insight

Rainbow Tables for Unix DES Crypt(3) Hashes

Posted: December 22, 2010 – 11:18 am | Author: | Filed under: Cryptography, Passwords, Tools

Some time ago, I started thinking about the possibility of using Rainbow Tables to crack old-school Unix crypt(3) passwords. Nobody had done this, and the reason most often cited was the presence of the two-character salt at the beginning of the hash.

This didn’t make a whole lot of sense to me. I mean, 2 characters? Isn’t that essentially like taking an 8-character password space and making it a 10-character space? People are already creating 10-character tables for other hash algorithms. Why can’t we do this for crypt(3)?

Turns out, it’s not that difficult. Over a few nights, I managed to work some rough hacks into the source for linuxrainbowcrack, and it seems like it’s working. I haven’t actually built a set of tables (other than small test tables) because I’m sure the code could be better optimized, and I simply don’t have the horsepower. But I’m hoping that others can both optimize the code, and generate and distribute tables.

This had been submitted as a talk for ShmooCon, but didn’t get accepted. So rather than waiting around for the next conference, I decided to turn it into an actual paper and publish it here. After all, the point is to enable others to use the technology, not for me to get a speaker badge to hang on my wall, right? (though I admit that would’ve been cool).

Even as I was waiting for the response from ShmooCon, I still wrestled with one big question: Will anyone even care? Then the Gawker hack was made public, along with 1.3 million user names and email addresses, most (over 750,000) with password hashes. Unix crypt(3) password hashes. If I still needed proof that this topic remained relevant, there it was.

Before I point you to the paper (which, like most things I write, is sort of long), let me give you the final conclusion up front:

  • The trick: Instead of creating 4096 different tables, one for each salt, I create a single table (set) that includes all salts. This is accomplished quite simply by extending the generator’s password length by two, and using the first two characters of each randomly-generated plaintext password as the salt for the encryption step.
  • It’s about as slow as expected: about 9x slower than MD5 hash table generation.
  • It takes a lot of space (mostly because of the slower compute time, the chains were smaller, but also because there are 4096 salts to be accounted for).
  • These speed / storage constraints, while significant, are no worse today than what existed for LANMAN or other hashes in 2003, when Rainbow Tables first started getting popular

And a couple of caveats:

  • Though the code is provided, it’s probably not something you can just apply to “the” standard rainbow crack source. I found several different projects, all in various stages of non-activity, so I’m not sure where the canonical rainbow table source really is at this point.
  • So you should treat this as a proof-of-concept. A paper outlining a method, and showing some of the key components for implementing that method.

I’m really hoping that more experienced Rainbow Table experts can take this idea, polish it, and make it work across multiple platforms, with freely-available crypt(3) tables as the ideal final goal.

The paper can be downloaded here: [download id="268" format="2" autop="false"]. Enjoy!

Both comments and trackbacks are currently closed.

3 Comments

  1. Posted May 23, 2011 at 10:40 pm | Permalink

    Why such short chain lengths? Can’t you decrease the rainbow table size with a linear increase in search time by simply moving from 10,000 entry chains to 100,000 entry chains? Since chaining is cheap even with an expensive hash, it seems like an obvious win.

  2. david_schuetz
    Posted May 24, 2011 at 2:31 pm | Permalink

    I needed something to work with, and in testing, 10,000 seemed workable while 100,000 was pretty slow. Keep in mind that the DES routine is slower than the MD5 (about 9x), so having the chain lengths about 1/10 the size keeps the times similar.

    On the other hand, if you’re able to get a faster DES routine, especially if it’s implemented in GPU or something else similar, then you’d definitely want to go with longer chain lengths.

  3. Dennis F. OBrien
    Posted February 12, 2013 at 1:57 pm | Permalink

    About 15 years ago I did a similar exercise, I used more of a probability model. I had some time on my hands and selected the upper-lower-num-+-minus character sets I noticed most common for prior guessed passwords. Then I pllied each of the 4096 salts for each trial password and I went aaaaaa,aaaaab,aaaaac… thru 99999999 to build files of every upper-lower-num-+-minus password having at least 6 characters, but less than 9 characters (likely unix/linux passwords). While the success rate via the resulting table lookup was over 85%, the amount of storage required to save every character combination using each of the 4096 salts was prohibitive. But today a 3 terrabyte disk is about $100, so the limitations I had at the time likely no longer apply. Then again, with todays distributed storage, someone could likely make the entire rainbow set and turn it into a simple table lookup as a full lookup, with no computation required.

2 Trackbacks

  1. By Nails in the Crypt « Darth Null on December 22, 2010 at 11:19 am

    [...] can read my corporate blog-post, with the paper linked at the end, right here. Categories: Uncategorized LikeBe the first to like this post. Comments (0) Trackbacks (0) [...]

  2. [...] This post was mentioned on Twitter by Rob Fuller, shftleft and others. shftleft said: RT @IntrepidusGroup: A paper written by David about creating Rainbow Tables for Unix DES Crypt(3) Hashes – http://cot.ag/howHAA [...]

image

This site is protected with Urban Giraffe's plugin 'HTML Purified' and Edward Z. Yang's Powered by HTML Purifier. 24504 items have been purified.