Coding Horror: All the news that was fresh in 1962

I just read a lovely article on Coding Horror, about “Rainbow Tables” – precomputed dictionaries of hashes of possible passwords, used for fast cracking of weak passwords.

At the end of the article is a quick primer on the simplest way to raise the bar on rainbow tables, salting.

That’s why you should never rely on hashes alone– always add some salt to your hash so the resulting hash values are unique. Salting a hash sounds complicated (and vaguely delicious), but it’s quite simple. You prefix a unique value to the password before hashing it:

hash = md5('deliciously-salty-' + password)

If you’ve salted your password hashes, an attacker can’t use a rainbow table attack against you– the hash results from “password” and “deliciously-salty-password” won’t match. Unless your hacker somehow knows that all your hashes are “delicously-salty-” ones. Even then, he or she would have to generate a custom rainbow table specifically for you.

That’s just one notch though; as Coding Horror says, the response from the bad guys is to generate their own deliciously-salty- rainbow table just for you. Probably not going to happen if the attacker is your roommate trying to open your private journal file. Probably *will* happen if the application used by millions of a bank’s customers to access their accounts..

The next notch is to use a randomised salt each time. The attackers don’t just need one rainbow table just for you, they need one for every possible salt. As the article says, even the smallest rainbow table is 338mb; multiply that by, say, 26^2(=676) (on the assumption of a two-character, lower-case-letter-only salt) and you have 228,488Mb (223.13Gb) of tables – and that only covers you for passwords of up to 14 characters, solely consisting of letters and numbers.

Coding Horror, with a bit of help from me, has now bought you up-to-date on the state-of-the-art in cryptography, circa the mid 1970s, when Thompson and Richie implemented this scheme to prevent dictionary attacks on unix /etc/passwd files.

Check Coding Horror again tomorrow for a fresh dose of vintage computer news!

Leave a Reply