Coding Horror: Rainbow Hash Cracking

As stated in the last few paragraphs, the simplest way to guard against this sort of attack is to salt the data before hashing it. What he doesn't discuss is how to choose a salt value. In a good hash function, every bit should affect the output, so really only a couple of bytes are needed for a good salt. Additionally, the salt value can be random and may include unprintable ASCII characters. Furthermore, a new salt can be created for every password. Now, if two users have the same password, the ciphertext will be different for each.

I've used this technique to store sensitive personal data which must be recoverable (i.e. credit card numbers.) When a new number is obtained, a few bytes of salt are randomly generated. The data, plus the salt, are passed to a symetric cipher, and the ciphertext and salt are stored in a database.

[edit: there's some discussion of this in the article comments.]

Also: stunningly bad exposition on "salt" values. A salt is a public nonce. Each password hash should have a different salt. An attacker shouldn't be able to construct a "your-salt" rainbow table to crack all the passwords on your machine; she should have to constrct N rainbow tables, for each of the passwords.

I don't think rainbow tables would work for public key crypto - cracking md5 with a lookup table is nothing like cracking RSA - they are completely different algorithms....

How quick would this do SHA-1?

Correction: passwords are routinely stored in plain text (or reversably encrypted); there are a variety of challenge-response protocols that you can't run if all you have is the hash. It's a tradeoff; what do you care more about, passwords at rest or passwords in motion?

A year or so ago I remember a couple private rainbow cracking sites that had tables of up to several terabytes in size. It was easy to just submit your hash and they'd queue it up to be cracked. I think one of them is now rainbowcrack.com, but it seems like a few have gone to paid services.

Does anyone know of Rainbow table-like pre-computation that could be used to crack any private/public key systems?