How many bits should change in a password salt?

Question

In https://crypto.stackexchange.com/a/27828/79037, it's indicated that one can "save space" by using something globally-unique, like an application-wide "pepper", together with something locally-unique (e.g, a user-id field, unique per-user). In other words, by simply "deriving" a salt (from some other fields/values/etc already there), instead of having to explicitly store a completely random full GUID next to each password.

However, in Should you change salt when changing password?, it's also indicated that salts should also change whenever a user resets their password as well.

And in https://security.stackexchange.com/a/41627/25009 it's also suggested that password salts should also be "unpredictable" relative to one another.

But, precisely how much "unpredictability" is enough? For example, I can construct a globally-unique, per-user password salt like pepper || user-id || nonce, where

• pepper is a globally-unique, application-wide constant
• user-id is a locally-unique, per-user constant
• nonce is a simple random 4-byte integer (changed during password resets) stored alongside the password hash in the database

So, the nonce is only "dynamic" part of the salt. It's only 4 bytes long, which is pretty short, so can definitely be used to save space in the database (at least, relative to simply storing a full 128-bit random GUID next to each password hash as the salt).

But, is 4-bytes of "unpredictability" really sufficient for a password salt? Or, would this nonce have to be even longer, like 64-bits? What if it's a highly-targeted website/app? (Obviously, requiring "128-bits of unpredictability" would negate any "space savings" from this approach anyway, but perhaps so much "unpredictability" between salts may be overkill)...

---

*Edit -- for reference, I'm imagining a scenario where an attacker gets to "discover" the salt (i.e, the pepper || user-id || nonce combination) and password hash for any user at any time. But, there is a specific user, or group of users, however, that are highly targeted, who upon getting hacked merely change their passwords (to perhaps just another simple, low-entropy "human" password!), and thus buy themselves maybe "just a little more time". But -- can they really expect enough "time", with only 4-bytes of "unpredictability" between salts? (Granted, of course, these salted hashes are themselves computed with a pretty nice slow KDF)...

Answer 1

pepper is a globally-unique, application-wide constant

That's a possible definition. Some make pepper public (e.g. server name). Others make pepper a secret decided at installation, and that can help security if it's is not stored and backed up along the hashed passwords (but loss of pepper is a major availability disaster). Yet others make it a per-password random that's not stored, and must be found iteratively when testing a password, which is beneficial to a degree (see this).

precisely how much "unpredictability" is enough?

This depends towards exactly what goal.

The primary goal of salt is to prevent the amortization of password cracking effort over multiple users and servers, assuming leaked database(s) of hashed passwords. If a server has $u$ users, a unique salt per user increases the average effort per password found by a factor of about $u$. Towards that goal, it's enough that the proportion of salts that are duplicate of another salt is low, unpredictability is not needed, and it's satisfactory that nonce is empty, if salt contains a unique user-id (which is typical).

A secondary goal of salt is to delay password cracking effort until after the leak of the database of passwords. Towards that goal, we need a nonce, and it's misnamed: beside being used once it must be secret (until the database leaks). A counter of password resets won't do. $b$ bits of uniform random reduce the effectiveness of in-advance password cracking effort by a factor of $2^b$, thus 32 bits is typically ample: using a million GPUs for 5 years before getting the password database accomplishes less than using a single GPU for 12 hours afterwards.

As to the recommendation to change salt (that is, nonce) at each password change: it helps against amortizing the cost of password search between multiple passwords that have been used by a given user. This is useful because users tend to reuse variations of old passwords to devise new ones.

---

In summary: a 32-bit random nonce drawn afresh at each password change is fine, assuming that salt also contains a unique user-id. The random generator must be unpredictable and it's result secret (assuming no leak of password hashes that is), with uniformity non-critical. Larger nonce is not much useful, and increases the size of the database of user passwords.