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:

And a couple of caveats:

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!