RE: Values to use for a salt?

> From: Scott Cleven-Mulcahy [mailto:scottcm3@xxxxxxxxxxx] 
> Sent: Thursday, December 18, 2003 7:13 PM

> Still, the point remains that salt can provide two functions: 
> increased randomness and uniqueness of a password's hash.  Highly 
> random salt, if used for all password's, only increases the
> randomness of a password.  It does not solve the uniqueness problem
> - two people with the same password would still have the same
> password hash code.

Not unless the random salt happened to be the same for both.  Even with
Unix's 14-bit salt (just checked crypt(3)), by the Birthday Paradox the
chance of two users getting the same salt is 1/128.  That probably satisfies
most people's threat model.  If not, use more salt.  For every additional
two bits of salt, you halve the chance of a collision (again by Birthday
Paradox).

> Since the password hash is normally protected, why would you 
> want to use a unique salt?  Layered security.  In the event that the 
> password hashes become exposed, a birthday attack can be used to
> decrease the effectiveness of the hash.

Ensuring unique salt does not scale well and becomes unnecessarily complex
if more than one authenticator is involved (eg if you're trying to ensure
unique salt in multiple domains, which is generally one of the roles salt
plays).  It also becomes increasingly hard to keep salts secret if you have
to ensure uniqueness across multiple authenticators.  You're much better off
making the salt large enough that collisions are vanishingly unlikely.

No one tries to ensure that RC4 keys used in SSL are unique.  We just trust
the probabilities, which are very, very much in our favor.

> The secrecy of the salt will also assist in protecting the 
> passwords.  The problem is that now you must map username to 
> password hash to salt.

So you're assuming an attacker who has the password hashes but not the salt.
That seems like a rather implausible situation to me, frankly.  What
protected the latter but failed to protect the former?  What's the threat
model?

> Another possibility would be the following.  A mapping table 
> with the hash of the username as the table's key,

What's the advantage of using the hashed username as the key?

> the username, and the user's encrypted password hash code.
> The hash code is encrypted with the authenticator's 
> asymmetric public key.

Hashing the username adds no strength (anyone can do it).

If the authenticator's "public key" is actually public, an attacker can
generate hashes, encrypt them with this public key, and compare the
encrypted hashes with the harvested ones.  (I'm assuming the attacker has
harvested the encrypted hashes; otherwise there's no reason to have them
encrypted.)

In essence, encrypting the hashes - with any sort of key - is just another
hashing stage.  It doesn't add any strength unless your threat model assumes
the key is kept secret.  That's tough; the authenticator has to use it,
which means it has to get it at startup and it has to keep it somewhere.
Those have both proven problematic in real-world applications (which isn't
to say they aren't being done - just that they're tough).

Password hashes fall to dictionary attacks because of poorly-chosen
passwords and too little salt.  Use plenty of salt and use filters that
require minimally-strong passwords (as appropriate for your threat model,
and remembering that users are lousy at picking passwords and keeping them
secret).  Having a decently flexible password mechanism probably helps.

> Now, if the user database is compromised the attacker needs the 
> authentictor's asymmetric private key before they can begin 
> to brute force the password hash codes.

Nope.  Just the public key, because they can encrypt their precomputed hash
dictionary with it and compare the result.

> If the salt value is unique per person then the attacker can't compare
> hash codes to identify identical passwords.

Erm, that's true if there are no {password,salt}-pair collisions.  It has
nothing to do with unique-per-person (unless there are other constraints
which make unique-per-person equivalent to unique-per-password-entry, eg no
person is allowed more than one username).

> Could the salt, or HMAC key, be the hash code of the username?  It 
> would provide a unique salt or HMAC key per user, but I don't know the 
> security impact it may have.

An attacker who knows the username would know the salt for the corresponding
password.  Not good.  Random salt is the only safe way to go.

-- 
Michael Wojcik
Principal Software Systems Developer, Micro Focus