[Cryptography] CSPRNG for password salt

[Jerry Leichter]

On Aug 20, 2014, at 12:23 AM, John B <vertex.vr4 at gmail.com> wrote:
> In answer to your question - "Where did you see this?" here are the top 2 hits:
> 
> https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet#Use_a_cryptographically_strong_credential-specific_salt
> (As pertaining to salt) "Use cryptographically-strong random [*3] data;"
> 
> https://crackstation.net/hashing-security.htm#properhashing
> Salt should be generated using a Cryptographically Secure Pseudo-Random Number Generator (CSPRNG). CSPRNGs are very different than ordinary pseudo-random number generators, like the "C" language's rand() function.
The second of these just makes a bald assertion, so one can't really respond to it.  It does have the text:  "The salt needs to be unique per-user per-password. Every time a user creates an account or changes their password, the password should be hashed using a new random salt. Never reuse a salt."  Since some of the standard algorithms use a 32-bit salt, this is an impossible requirement:  The birthday paradox implies that you'll likely repeat a salt within 65000 or so "new password" events.  That's not long at many organizations.  (Maybe they meant "never reuse a salt for a given user".  Even then, with 32-bit random salts, you're taking *some* noticeable risk that this might happen by chance - but unless you're worried about targeted attacks against particular users, rather than population attacks against all of them, the distinction makes no sense at all.)

The OWASP page has a tad of justification:  "Salts serve two purposes: 1) prevent the protected form from revealing two identical credentials and 2) augment entropy fed to protecting function without relying on credential complexity.   The second aims to make pre-computed lookup attacks [*2] on an individual credential and time-based attacks on a population intractable."  "*2" is a reference to rainbow tables.  So, yes, if you have a situation in which the salts that will be used in the future are predictable, even in a probabilistic sense, an attacker could pre-compute rainbow tables that will be useful against some user in the population, or maybe against a particular user perhaps by forcing his hand (e.g., if I know what salts will be used tomorrow - even a small number of possibilities - I can do something that will make the user change his password, like making it *look* as if it's been attacked or sending a fake administration message or triggering an alert by repeatedly trying and failing to log into his account), then I can pre-compute rainbow tables that will likely work against some account, or a particular account.

This assumes rainbow tables (the only pre-computation mechanism of which I'm aware) are a reasonable attack mechanism.  Yes, at one time they were.  But today there's little reason to bother with them, as attacks based on multiple GPU's are cheap and fast enough to beat them easily.

Is it *prudent* to use unpredictable salts?  Sure, on a defense-in-depth principle:  It costs almost nothing for the defender, can't possibly *help* the attacker, and does help protect against an attack that once made sense, was rendered obsolete by changes in hardware - but, who knows, might become relevant again at some point in the future.

If random number generation were expensive, and I had to generate salts in batches, it would be fine to generate one random starting point for the batch, then the rest from the starting point in some simple way.  Why?  Because this breaks an attackers ability to predict *ahead of time*.  Sure, in principle, once he sees one new salt, he may know a bunch of others - but that doesn't help him get out ahead of the process by more than the interval between the beginning of the batch and the end.  (I suppose you could worry about more sophisticate attacks, easier to visualize if you imagine you just add one to generate the next salt.  This produces bands of sequential salts as long as a batch, and a clever attacker could choose to start rainbow tables with samples spaced apart by the expected length of a batch.  But that's just the starting point - after one hash round, he's just probing randomly.  So the advantage is tiny.)

My personal conclusion:  If, in your environment, you can generate salts in an unpredictable way without imposing too much cost on the system - you might as well go for it.  If not ... nothing terrible is likely to happen from using predictable salts.

BTW, there's little justification for using short (32-bit) salts.  You can easily eliminate all possible birthday attacks by using 80 or more bits of salt.  If your hashing function doesn't accept a longer salt, XOR the extra bits in before hashing.  (Just to avoid any possible interaction, *don't* XOR in those bits that will actually go into your hashing function.)

                                                        -- Jerry

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140820/ff574f59/attachment.html>