Re: Salt in encrypted password in pg_shadow - Mailing list pgsql-general

On Tue, Sep 07, 2004 at 10:27:40PM -0400, Tom Lane wrote:
> Steve Atkins <steve@blighty.com> writes:
> > 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.
>
> [ raised eyebrow... ]  It is not immediately obvious that a factor of
> 2^16 makes the difference between feasible and infeasible.  As
> counterexamples, if it would otherwise take you one microsecond to break
> the password, 64 milliseconds isn't going to scare you; if it would
> otherwise take you a century to break the password, raising it to
> 64k centuries isn't going to make for a very meaningful improvement in
> security either.
>
> Show me a scheme where the random salt isn't stored right beside the
> password, and I might start to get interested.

A password salt is a pretty well understood benefit. It's very, very
standard technology, and has been in use for decades. The primary use
for it is to increase the cost of a pre-computed dictionary attack.
While the value of that has decreased as the ratio of CPU speed to
mass storage size has changed it's still a significant
value. Particularly as it still applies to parallel attacks.

We're talking about one-way hashes here, again a fairly standard
technology. Given the hash of a password the only (currently known)
way to compute a password that will validate against it is to guess
a password, compute the hash, see if it's the same, repeat.

You're never going to 'decode' a password from the hash - it's about
guessing the right password. Some passwords will be well-chosen, some
will be poorly chosen, some will be in between. The ideal situation
is where I have a number of hashes and just need to find a password
to match one of them.

So, assume I have a password generator that will generate me an
endless stream of passwords, starting from the obvious ones and
getting increasingly complex - this is the usual approach, as used
by crack and other unix password file crackers.

As one example, say I have 1,000 hashes, that it takes me ten
milliseconds to hash a password and the easiest to guess password will
be the hundred millionth produced by my password generator.

I can simply calculate the hash of each password in turn and compare
that hash against each of the thousand hashes. That'll take me about
11.5 days to crack the simplest to guess account of that list of
a thouasand.

Now, lets say that instead I have a thousand hashes, and associated
with each hash is a salt, all different. That means that to test
each generated password I'll need to calculate not a single hash,
but a thousand hashes - one against the combination of my guessed
password and the first salt, then the combination of the passsword
and the second salt and so on.

To crack the simplest to guess account of the thousand accounts I
have access to in this case will take me a thousand times as long -
about 30 years.

That's an example of why a salt is still extremely valuable, despite
the change in CPU speed:storage speed/size ration

It actually takes around 300us to compute an MD5 hash on modern
hardware (which is fast enough that use of MD5 for password validation
isn't clearly a good idea anyway, but that's another issue[1]) which
changes the math somewhat, but the principle is the same.

There are other benefits to a random salt too. Lets assume that
I have (by doing something dubious with a combination of google
and an insecure application server) ten thousand password files.
If no salt is used, or the same ('postgres') salt is used for
all of them then any two accounts with the same password will
have the same hashed value. That means I can identify two
people using the same password - if I can social engineer it
out of one of them I can use it to access the others account.

Cheers,
  Steve

[1] The other issue being: When the concept was originally deployed it
 took around half a second to calculate the hash. As hardware has got
 faster, the calculation has got faster and brute force attacks against
 a password file have become easier. MD5 is way too fast to be used as
 part of a password based system that has attack trees including
 compromise of the crypted password file. That's one reason that
 unixen use shadow password files rather than making /etc/passwd
 readable to all local users, to reduce the chance of the known
 hash attack occuring.