Some time ago, I started wondering why I couldn’t find any Rainbow Tables for old-school Unix crypt(3) passwords. After some research, I learned that the salt was the culprit – that virtually anyone who’d asked about such tables went away chastised, told that the salt made it impossible to generate Rainbow Tables, unless you went through the trouble to create 4096 different tables (one for each salt). And who’s going to do that?

Somehow, that just didn’t sit right with me, and it wasn’t long before I decided that the conventional wisdom was wrong, and that there would be an easier way to build crypt(3) tables. But I didn’t really do anything with it for a long time, until I finally decided to try, once and for all, to see if I was right. And it turns out – I was right. Changing the standard rainbowcrack programs to support crypt(3) password hashes was trivial. In only one evening, I had something (more or less) working, and a couple of nights later, it was able to actually read, write, and process crypt(3) hashes in their native form (as opposed to a flat hexadecimal dump of the hash).

“Wow! This is cool,” I thought. “I should totally submit this for a security con.” Which I did. But I didn’t get accepted.

So what do I do now? Do I sit on my findings and resubmit, again and again, until a conference accepts it? Or should I just admit that maybe it’s not quite as cool as I think, and maybe it won’t get accepted ever? (As cool as I think it is, it’s certainly possible that it’s not that cool, or that perhaps someone else has already done this and I’ve just not found the code yet – and I’m okay with that.)

It seems silly to just keep this in my back pocket for the sole purpose of getting up in front of a room full of people to talk about it. So rather than hiding it away, I decided to turn it into a more detailed paper, and post it.

So I’ve now posted it to my company’s website. All the crazy details are there, including 50-some-odd lines of proof-of-concept code that need to be inserted into the linux rainbow table crack source. It’s not entirely turnkey (you’ll have to work some to get it compiled yourself), but then again the tables aren’t built, either, so it’s not like you could just make the changes and start cracking passwords. It’s also verly likely far from optimal.

I’m hoping that Rainbow Table experts can see what I’ve written and roll it back into some canonical, actively maintained source tree, and that people can start building and using tables for crypt(3).

Before you go running to read the paper (if you haven’t already noticed, I’m a little long-winded, and the paper is 12+ pages long), here’s a quick preview:

*Instead of generating 4096 tables of 1-8 character passwords, just create 1 table of 3-10 character passwords, and use the 1st two characters of the plaintext passwords as the salt. (That part will make more sense if you read the paper.)

  • It’s still kind of slow: 9x slower than LM hashes, for example. But CPUs are much faster than they were in 2003, when people first started building tables for LM hashes.
  • It also takes a lot of storage. But storage, likewise, is much cheaper than it was seven years ago.
  • So, in the end, I think it may be worth the effort, finally.

Why would anyone care? Well, even though crypt(3) hash technology is something like 35 years old, it still shows up from time to time. It’s a simple, well-understood, and almost universally-supported format. So it’s tempting when building systems to just use crypt(3) and forget about it.

That’s apparently what happened with Gawker Media, who had over 1 million emails and password hashes leaked last week, most of which were crypt(3) based.

So anyway, it’s a fun little hack, and I’m hoping people can run with it.

You can read my corporate blog-post, with the paper linked at the end, right here.

UPDATE - I presented my original slides (with appropriate updates) at the Northern Virginia Hackers Association (NoVAHA) in April. You can download those slides here.

(view Archived Comments)