[CWuestefeld]

Salt is a large random string unique per user, not per password.

Of course it's per user.

But "large" makes some sense. My current implementation has maybe 20-22 bits of uniqueness in the salt, certainly less than 16 bytes.

I don't think 16 bytes is necessary even as insurance against the future. Rainbow tables are still expensive to build.

On the other hand, maybe to build just a small table addressing the stupidest passwords ("password","12345678",etc.) it's worth making it more difficult.

[dchest]

Of course it's per user.

What I meant is that it shouldn't be per user, it should be per password. If a user changes his password, he should get a new salt.

[CiPHPerCoder]

> I don't think 16 bytes is necessary even as insurance against the future.

The birthday problem comes into play here.

If you have 22 bits of entropy in your salt, after 2048 users (2^11) you will find two with the same salt, with 50% probability. If they also use the same password, this makes attacking your users much easier.

Don't make it easy for attackers. Use 16 bytes from a CSPRNG. Better yet: Use a password hashing library that takes care of this for you.

If you use a 128-bit (16-byte) salt, you have a 50% chance of a collision after 2^64 passwords.