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 Enjoy!