[by]

"The length of the randomly generated salt shall be at least 128 bits."

nist-sp800-132.pdf http://csrc.nist.gov/publications/PubsSPs.html

Not quite the same application, but it would seem best to take a conservative approach and make your salts 128 bits because the storage required is so small - you are only storing one per username.

[yaakov34]

Right, but this doesn't make the search space 2^64 times larger, or anything of the sort. Once you've assigned a unique salt to every password, you're not getting any further benefits from salting. This is what the Mt. Gox owner doesn't seem to get, with his "triple-salting".

The NIST application involves generating keys from passwords, which you might do a gigantic number of times for every password to get unique sessions and so on. They're not talking about password storage. And even then, 128 bits seems like a huge overkill, which was included just because it's cheap, so why not. I don't mind 128-bit salts, but let's not promote that as some "ultra-secure" feature, which it isn't.