What is a salt and Why Is It Useful?

Dennis J. McWherter, Jr. bio photo By Dennis J. McWherter, Jr. Comment

Someone recently asked me why we should use a salt if we€™re simply going to store it in plaintext. I mean, after all, if an attacker is trying to crack a password, they simply add the salt to whatever generated string they€™re checking and it has seemingly negligible effect. While this is true, it misses some fundamental concepts as to what a cryptographic salt actually adds by way of security.

Wait a second. Salt? That€™s what I put on my fries.

Well, yes. Salt is the delicious €œwhite crystalline substance€ which we often use to add flavor to our food. However, it can also be used to add flavor (so to speak) to our passwords. When people are talking about €œsalting€ in the context of cryptography, they are typically referring to a random string which is deterministically combined (i.e. usually appended or prepended) with some value which is then hashed. For instance, if we had some hash function h(x), we might €œsalt€ a password as follows:

// This is Berstein's hash, btw
var h = function(str) { return str.split('').reduce(function(x, y) { return 33 * x + y.charCodeAt(); }, 0); };
var SALT_LEN = 10;
var salt = [];

// Random salt
for(var i = 0 ; i < SALT_LEN ; ++i) {
  // Limit to printables
  var value = 32 + Math.ceil(Math.random() * 94);
  salt.push(value);
}

// Convert back to string
salt = salt.reduce(function(x,y){ return x + String.fromCharCode(y); }, "");

var password = "myPassword";

console.log("Unsalted hash: " + h(password));
console.log("Salting password: " + password + " with " + salt);
console.log("Result: " + h(salt + password));

As you can see, all we are doing is simply combining (i.e. prepending) our salt with our secret (i.e. our password) before we hash it. Pretty simple, huh?

What does this even buy us?

Naturally, if an attacker is trying to crack a single password, this buys us nothing. In fact, a brute-force attack on this hash would be as effective as a brute-force attack on any hash (i.e. exponentially slow). However, there is another class of attacks which this guards against. In particular, this thwarts the attempts of rainbow table attacks. Similarly, by salting each password with a unique, this makes it even harder for an attacker to actually execute such an attack on a mass scale.

Unsalted hashes. So how exactly does this attack work? Well, simply put, many attackers try to brute force many hashes and they save the results. Consequently, they come up with a list of values that map to a hash for a given function.

NOTE: Remember, when you€™re attacking a hash a collision is just as good as the €œreal€ input.

This table is precomputed and simply used as a lookup. For sake of example, say we have computed a rainbow table for the hash function h shown above. Typically, we would probably store the values in a hash table for quick lookup. Now, say we are trying to crack the passwords of a user from a database dump we happened to acquire (read: if you actually acquire one of these, you€™re probably breaking the law) and we notice that the user€™s hash value is 4282592. Since we have computed our rainbow table and stored it as a hash table, we will do a simple lookup:

var plaintext = rainbowTable[4282592];
// The result here for an unsalted hash would be "test" or a collision

We have now successfully recovered a plaintext which we can use to login as this user on the service (again, regardless of whether it is the real password or not).

Hashes with same salt. With a salted hash, however, we would have made this attack harder to achieve. Instead of using the original precomputed table, the attacker would have to precompute a new table with the salt combined appropriately. Remember, rainbow attacks work well because they are computed once (often by many people) and then reused many times. It is very expensive to compute a rainbow table. However, once a rainbow table is computed for your particular salted implementation (since you used the same salt), cracking these hashes is as trivial as with the unsalted hash. That is, if you salt your table with some fixed s, then computing a table h(s + x) for all outputs of h is feasible.

Hashes with random salt. This technique tends to work better in most cases. In this case, there is no way to compute a rainbow table for your hashing scheme. Even though the attacker knows the salt, this is effectively reduced to a brute-force attack. Namely, since every salt is different, there is no way to effectively compute a rainbow table for all of your stored hashes. What I mean is, since s is not fixed in this case, h(s + x) cannot be effectively computed for all outputs of h since the combination of random s and x will have an unpredictable effect on the hash function. Thus, for a specific value s€™ (i.e. one random hash) for a particular x you€™re trying to crack, you would need to (theoretically) explore the entire output space of h(s€™ + x) before uncovering an acceptable output value for x. This is brute-force.

How do I do this in practice?

Fortunately, you are not likely going to have to implement salting schemes yourself anymore. That is, of course, if you decide to use a hashing algorithm such as bcrypt. Bcrypt adds your salt directly as part of the hash and– if you€™re using a library– often abstracts away the messy details of generating a proper salt for your hash. That said, you should see this post for more information on how you can easily screw up using bcrypt.

Next time someone starts talking about hashing and salting, you now have at least an idea about what they€™re talking about. What€™s more, you might be able to do a little more research and even help ensure the proposed scheme is actually effective against certain attack classes!

comments powered by Disqus