Salt length for a single password

Question

So I've been reading about salt, and am confused about why the length is so critical. From my understanding salt is used for protection against pre-computed attacks.

Say I have a single password that is hash with salt length n. Suppose this hash and salt is accessible to the attacker. My questions are as follow:

1. If the n is too short, is the problem that a pre-computed rainbow table may already exist?

2. If n is long enough that a pre-computed rainbow table doesn't exist, what function does a longer salt serve? A brute force attack would simply add the n length salt to each hash it's generating. 50 bit n, 500 bit n. No difference, because the salt is known and simply added to all the brute force password values being hashed.

So to summarize, when trying to crack a single salted password hash, as long as n is long enough that a rainbow table doesn't exist, then the salt length n adds no security to the hashed password. Is this true?

Answer 1

You are correct that the function of using a distinct salt for each user is to thwart any batch advantage an adversary attacking one of many targets might have gotten out of precomputed tables. If there are $2^n$ distinct salts and they're chosen uniformly at random for each user, it's only around $\sqrt{2^n} = 2^{n/2}$ users that a collision in the salts might happen so that the adversary might even get a chance to apply one precomputed table to many users.

• Pick $n = 256$ bits and you won't ever have to worry about it.
• Pick $n = 128$ bits and you probably won't ever have to worry about it even if everyone else uses the same hash function.
• Pick $n = 64$ variable bits and an application-specific constant that nobody else uses and you're probably mostly OK because the precomputation of the table is expensive already, even if there are a handful of collisions in a few billion users. But consider revisiting once you've hit a million users just to be safe.

No need for $n = 500$ bits or anything obscenely large like that.