How much bigger does a precomputed lookup table get when salt is added?

Question

I am trying to wrap my head around the benefits of salt in cryptography.

http://en.wikipedia.org/wiki/Salt_(cryptography)

I understand that adding salt makes it harder to precompute a table. But exactly how much harder do things get with salt?

It seems to me, like when you add salt, the number of entries in your precomputed table would = number of common passwords to precompute x number of entries in the password table (ie number of different possibile salts).

So if you have a list of 100 common passwords, then without salt, you would have 100 hashed passwords. But if you have 10 users on a system, with 10 different salts, then you would now have 1000 different combinations to check.

So as the numbers of users or the size of common password list increases, the precomputed table gets so big that you can't pre-compute it easily (if at all)

Am I getting this? Do I have it right?

NoteCross posted on cs theory https://cstheory.stackexchange.com/questions/11118/how-much-bigger-does-a-precomputed-lookup-table-get-when-salt-is-added#comment30381_11118 CS Theory Users suggested I post here too

Answer 1

Looks right to me, assuming you know what the 10 salts are.

If you don't know a priori what the salts are (which is typically the case when building a rainbow table), you'd have to compute for the entire salt space. This is where the big gain comes into play as for each additional salt bit, the storage requirement doubles. Thus you get exponential growth of the storage requirement.

Answer 2

Well, you've got the main gist of it ("it tries to make precomputation take too long to be practical") correct, but you've gotten some of the details wrong. Here are the corrected details:

• When someone actually uses a precomputed table, an attacker with a big table of passwords and hashed versions of those passwords isn't the only thing we have to worry about. Another thing we need to worry about is if someone puts together a Rainbow table. In essence, a rainbow table is a clever way of compressing the table of passwords and hashes; a rainbow table that covers N passwords still takes $O(N)$ time to build, but it may take up only $O(N/k)$ space (at the cost of making a check to see if something is in the table take up $O(k)$ time; the attacker chooses $k$ when he builds the Rainbow table). What a salt does to a Rainbow table is force the table to cover various passwords and salts; if you have $M$ possible salts, this effectively increases the amount of time building the table to $O(NM)$.

  Salt does have this limitation; it limits the amount of precomputation that the attacker can do, however if the attacker is interested in one specific password, then after he has recovered the salt/hash, then he can still spend $O(N)$ time to check to see if $N$ passwords are correct; this implies that huge values of $M$ (that is, really large salts) don't really add that much protection.

• As mikeazo mentioned, it doesn't really matter how many salts are currently active. If the attacker doesn't know the salt when he is precomputing, he'll need to cover all the salt values (or, at least, any salt value he doesn't cover will be a guaranteed miss when he actually gets the salt/hash combination).

• Salt also has another advantage (which has nothing to do with precomputation); it also disguises when two passwords are the same. If Alice and Bob happen to pick the same password (perhaps because they're really the same person), then without salt, their password will hash the same, and that will be apparent to someone just viewing the hash. However, if we add salt, the hashes will appear to be unrelated (unless we happen to pick the same salts). Of course, there are other ways to achieve this as well (say, include the username in the hash).

Answer 3

when you add salt you multiply the number possible hashes by the number of possible salts.

The time to generate a rainbow table is proportional to the number of hashes.

Now the time to crack for a rainbow table is proportional to the square of the number of hashes divided by the square of size of the table.

So for every bit of salt you add, you make generating a table twice as long and using a table 4 times as slow, if the size of the table is limited.

You want to add salt until it is not feasible to create a table anymore (2^80 combinations of salt and passwords should be safe, but use 128 bits of salt anyway to be on the safe side)