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

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?

-
"salt" ? Please explain for those of us who are crypto (and cooking) challenged. –  Suresh Venkat Apr 17 '12 at 17:51
I think this is on topic here, but would do better at crypto.stackexchange.com. $\hspace{1 in}$ –  Ricky Demer Apr 17 '12 at 18:18
how do i send it to the other site? –  bernie2436 Apr 17 '12 at 18:46
You ask it there (as a new question), and mention (there) that you cross-posted from here because someone here suggested it. –  Ricky Demer Apr 17 '12 at 18:50
Don't forget to add a link in each question to the other question. –  Danny Varod Apr 22 '12 at 16:39

There are a couple of different things going on here, and you need to define your problem more clearly.

For starters, let's just look at a simple case where what is being stored in a database (for each user) is either $H(pw)$ or $s, H(s, pw)$ where $H$ is a hash function, $pw \in \{1, \ldots, N\}$ is a password, and $s \in \{0,1\}^\ell$ is a salt.

To attack a single user without a salt, the attacker can pre-compute $H(pw)$ for all possible values of $pw$ yielding a table of size $N$. Without knowing the salt, however, the attacker has to compute $H(s, pw)$ for all possible salts as well, thus requiring a table of size $N \cdot 2^\ell$. On the other hand, if the attacker does no pre-computation but instead just waits until it compromises the database and then obtains $s^*, H(s^*, pw)$, then we are back to the previous case where the attacker just has to compute $N$ values of $H(s^*, pw)$ to learn the password.

Thus, in the single-user case, the salt increases the attacker's off-line computation but does not increase the on-line computation needed.

Before continuing, let me note also that (in the case without the salt) the attacker can use to obtain various time-space tradeoffs. Use of salts makes rainbow tables less effective as well.

Salts also help, in a somewhat orthogonal way, in the multi-user setting. To see this, note that if the attacker got the database of hashed passwords in the unsalted case, then using $N$ work he gets the passwords of all users. But in the salted case, assuming each of $M$ users is assigned a different salt, the attacker must do $M \cdot N$ work to recover all passwords.

-

You don't need users X passwords entries...

You can store the passwords with one master set of salts (one or more salt - can be double salted, triple salted or more).

When the user tries to log-in, the server should send him a temporary salt, which should be used to salt the password prior to sending it.

The server should then unsalt the password using that temporary salt, then salt it with the master salt(s) and compare it with the DB version.

In other words the time complexity may grow, but the effect on the storage space should not (unless salting algorithm has larger output than input).

There are also alternatives such as asymmetric encryption and certificates.

-