Re: Salt in encrypted password in pg_shadow

On Tue, Sep 07, 2004 at 03:09:28PM -0400, Tom Lane wrote:
> David Garamond <lists@zara.6.isreserved.com> writes:
> > Tom Lane wrote:
> >> Also, MD5 hashing is fast enough that I'm not sure the above is really
> >> significantly cheaper than a straight brute-force attack, ie, you just
> >> take your list of possible passwords and compute the hashes on the fly.
> >> The hashes are going to be much longer than the average real-world
> >> password, so reading in a list of hashes is going to take several times
> >> as much I/O as reading the passwords --- seems to me that it'd be
> >> cheaper just to re-hash each password.
>
> > Many people use short and easy-to-guess passwords (remember we're not
> > talking about the superuser only here), so the dictionary attack can be
> > more effective than people think.
>
> And that responds to the speed argument how?  I quite agree that a
> guessable password is risky, but putting in a random salt offers no
> real advantage if the salt has to be stored in the same place as the
> encrypted password.

The usual attack against hashed passwords is to use a dictionary
driven password generator to create a large number of passwords, find
the hash of each of those, then store the passwords on disk indexed by
the hash.

That's a one-time effort that can then be used in the future to crack
any number of password hashes extremely cheaply - given any hash you
can find the corresponding password, if you have one, with one index
lookup.

A random salt stored with the hashed password increases the storage
and precomputation time required by the size of the salt (so a 16 bit
salt would increase the storage and precomputation time needed by
a factor of 65536). That increase makes the pre-computed dictionary
attack pretty much infeasible.

Cheers,
  Steve