Internet Security III: Salting Your Hashes

I dream therefore I Am.

• Internet Security Part I: Cryptography and the Darknet
• Internet Security Part II: Slowing Things Down
• Internet Security Part III: Salting Your Hashes

Salting your hashes helps protect against rainbow attacks. No I'm not making this up, this is fairly basic web security.

If you waded through my previous rambles on this topic you'll recall that hashing is a way of protecting user passwords. A hash is an algorithm that generates a very large number from data (often text). The hash represents the data, kind of like a fingerprint. Hashing can be used as a way to verify that data hasn't been tampered with - if the hash is transmitted with the data then you can hash the data yourself and check it matches what is expected. Hashing is also a way to check passwords without having to store the password. When a user supplies a password the password can be turned into a hash and compared with the stored hash. If the two hashes match then the user has supplied the right password and this can be done without having to store the password. This improves security because if you don't store the password you can't leak the password.

Unfortunately however, as I explained, this is vulnerable to a type of attack called a "brute force" attack. If an attacker knows the hashing algorithm in use they can simply try every possible password until they find the one that matches the hash. One way to reduce the risk of this is to use a very slow hashing algorithm, so that trying every possible password becomes very difficult.

Alas, the bad folk are as intelligent as the good folk. Our saving grace is that being good requires less deception which in the long run makes it more effective, the problem then is trust and there are various ways to establish trust or to co-operate with people without having to trust. All topics for future ruminations.

Although slow hashing protects against brute force in theory, there's another class of attack it doesn't prevent and these are called "rainbow table" attacks. (Don't ask me why, but I bet google knows - probably because a rainbow has all the colours.) As well as computers getting vastly faster (I refuse to use the word exponentially because it actually has a meaning and this aint it) storage has become vastly cheaper too. There are only a finite number of common slow hashing algorithms and if you want to be secure you ought to be using a well understood one. Sadly that means an algorithm known to your attacker too. For those not in the know, which now doesn't include all UK schoolkids below a certain age, an algorithm is a series of steps to achieve a result. Like a cooking recipe. I love that children are now taught this.

An attacker who knows what hashing algorithm you're using can pre-compute all the hashes of every possible password. This is called a rainbow table. It takes a lot of time and a lot of storage space, but once it's done it's done and then your one way hash is broken! The point of a one way hash is that it's easy to turn a password into a hash but hard to turn a hash back into a password. If you've calculated all the possible hashes of all the possible passwords then it's easy to go from a hash back to a password - you just look it up in your rainbow table!

This incidentally is why password security nowadays is mostly dependent only on the length of the password you pick. Working out all the possible hashes for a five character password is mahoosively easier than every possible hash for a ten character password. The comic-and-generally-all-round-genius XKCD recommends that instead of picking a password you should use a pass-phrase, and maybe throw in a number and symbol to throw off dictionary attacks (passwords comprised of words in the dictionary are common, so attackers try these first). Added to this "my-horse-only-p33s-in-the-bedroom" is much easier to remember than "f&fadjsd!!00ffr". The pass-phrase is dramatically more secure, simply because it's longer and it would take a million more computers for a million more years to break it (uhmm, approximately). This is why websites that have a maximum length for your password are being stupid as well as lazy. They've made a security decision to make lives easier on their database rather than making a security decision for security.

The way round this is to salt your hashes. Instead of hashing just the password you pick a random salt (a word or string of characters) and hash the password plus the salt. You need to store the salt alongside the hash, and always use it when checking the password. Now a rainbow attack doesn't work because each password has a different salt, so they'd need a different rainbow table for each "password plus salt" combination. So even if your database of password hashes plus salts leaks the attacker still has to compute or already have a rainbow table for every salt. Effectively you just made every password a lot longer, and longer in a different way for each password, making the required rainbow table required to break it vastly (exponentially?) bigger. At some point, as computers continue to get faster and storage cheaper, this will not be enough, but at that point you can migrate your database to a different hashing algorithm and a longer salt. There are established techniques (annoying to do but well understood) for this migration process.

At this point it seems right to mention that it's not just salted hashes I'm a fan of, but the current fad of salted caramel is right up my alley (if you know what I mean) and Christmas is nearly upon us!


You may also be interested in the following programming related articles:

• The Craft of Software Engineering
• Abstractions and Business Processes
• Software Engineering Abstractions: Design and Testing

"It's not so much that I don't fit in a box, it's more that I really resent being pushed into a box that I'd probably fit into if I wanted."