Join Log in
Score:0
avatar Crypto

How many bits should change in a password salt?

ng flag
ManRow

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)...

112
1 + 3
J_H avatar
nr flag
J_H
Please make it explicit that the attack you’re contemplating is: we have two independent websites adhering to similar salt policies; user sets same cleartext password on both sites; attacker obtains the Site A hashes with salts; attacker obtains a Site B credential and spends cycles on rainbow attack against A. (Or nail down some alternate scenario that you want to protect against.)
0
Reply
ng flag
ManRow
@J_H but that is not the attack I'm contemplating. Also, the `pepper` (e.g, 128-bits or 256-bits) automatically makes all the salts on my website *globally-unique* anyway, but, still, not very "unpredictable" *between one another*. My question, in turn, is just asking *how much* of this "unpredictability" is really needed...
0
Reply
ng flag
ManRow
For an *extreme* example, if salts only changed just one bit (in the same place) between password resets for a given user, then merely just two different rainbow tables could possibly crack *any* (past, present, and future) low-entropy password chosen by that user. But, if one bit of unpredictability between salts is too little, how about 32-bits then? Is that enough, or do you need 64, or even 128-bits? What is a reasonable amount of "dynamic bits" here?
0
Reply
Score:2
fgrieu avatar Crypto
ng flag
fgrieu

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.

+ 4
ng flag
ManRow
Interesting, it seems that my question of "what is a reasonable # bits for such a nonce" (specifically, to protect against those "in-advance" password cracking schemes!) then in turn so depends on "how many resources does your attacker possess" and/or "how much time are you willing to give them", as per https://crypto.stackexchange.com/questions/27906/how-much-processing-power-should-you-assume-an-attacker-has. For example, what those million GPUs can accomplish in 5 years for 32-bit nonces, they could likewise accomplish in 1 week for 24-bit nonces (at merely just one less byte per user)!
0
Reply
fgrieu avatar
ng flag
fgrieu
@ManRow: yes. On the other hand, even with 24-bit nonce, if a password database leak goes un-remediated (including but not limited to un-detected) for 24 hours, during these 24 hours the same GPUs are >2.3 million time more likely to find a given password than in the week before, and they will do so at 15% the energy cost and GPU hogging. Thus arguably, even with 24-bit nonce, attack before the database leak is a non-issue compared to attack after, except if by some magic we are confident that any database leak is promptly remediated.
1
Reply
ng flag
ManRow
Interesting -- would there be a *minimal* recommendation as to the length of such a random nonce then? Even if an attacker can easily read the password database at "any time", a nonce that is long-enough could *still* make an "exhaustive search" (against a "current/latest" nonce & password-hash combo) much more practical than pre-computing/generating a bunch of rainbow tables for all (or even half of) the possible nonce values anyway.
0
Reply
ng flag
ManRow
Would this *minimum-length* (for the nonce) also depend on "how often" a database leak might be expected as well? If the attacker has to wait a long time in between subsequent database leaks (during which some password resets would occur), for a *short-enough* nonce they might as well try to make use of that time by pre-computing/generating some rainbow tables (for half or more of the possible nonce values) in advance...
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.