Salt in encrypted password in pg_shadow

[David Garamond]

I read that the password hash in pg_shadow is salted with username. Is
this still the case? If so, since probably 99% of all PostgreSQL has
"postgres" as the superuser name, wouldn't it be better to use standard
Unix/Apache MD5 hash instead?

--
dave


---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddres sHere" to majordomo@postg resql.org)

[Tom Lane]

Re: Salt in encrypted password in pg_shadow

David Garamond <lists@zara.6.i sreserved.com> writes:[color=blue]
> I read that the password hash in pg_shadow is salted with username. Is
> this still the case? If so, since probably 99% of all PostgreSQL has
> "postgres" as the superuser name, wouldn't it be better to use standard
> Unix/Apache MD5 hash instead?[/color]

How does that improve anything? If we add a random salt into it, we'd
have to store the salt in pg_shadow, so there wouldn't be any secrecy
added --- an attacker who can read pg_shadow could see the salt too.

(Actually, an attacker who can read pg_shadow is already superuser,
so it's not clear there's anything left to hide from him anyway.)

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faqs/FAQ.html

[David Garamond]

Re: Salt in encrypted password in pg_shadow

Tom Lane wrote:[color=blue][color=green]
>>I read that the password hash in pg_shadow is salted with username. Is
>>this still the case? If so, since probably 99% of all PostgreSQL has
>>"postgres" as the superuser name, wouldn't it be better to use standard
>>Unix/Apache MD5 hash instead?[/color]
>
> How does that improve anything? If we add a random salt into it, we'd
> have to store the salt in pg_shadow, so there wouldn't be any secrecy
> added --- an attacker who can read pg_shadow could see the salt too.[/color]

Consider someone who creates a long list of:

MD5( "postgres" + "aaaaaaaa" )
MD5( "postgres" + "aaaaaaab" )
MD5( "postgres" + "aaaaaaac" )
...

Now if he has access to other people's pg_shadow, he can compare the
hashes with his dictionary. Replacing "postgres" with a random salt
defeats this dictionary attack (and thus he will have to resort to brute
force).
[color=blue]
> (Actually, an attacker who can read pg_shadow is already superuser,
> so it's not clear there's anything left to hide from him anyway.)[/color]

But consider someone who finds a harddisk or tape containing a database
backup... he can then gain access to the real, online database.

--
dave


---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postg resql.org so that your
message can get through to the mailing list cleanly

[Richard Huxton]

Re: Salt in encrypted password in pg_shadow

David Garamond wrote:[color=blue]
> Consider someone who creates a long list of:
>
> MD5( "postgres" + "aaaaaaaa" )
> MD5( "postgres" + "aaaaaaab" )
> MD5( "postgres" + "aaaaaaac" )
> ...
>
> Now if he has access to other people's pg_shadow, he can compare the
> hashes with his dictionary. Replacing "postgres" with a random salt
> defeats this dictionary attack (and thus he will have to resort to brute
> force).[/color]

But surely you have to store the random salt in pg_shadow too? Or am I
missing something?

--
Richard Huxton
Archonet Ltd

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org

[Tom Lane]

Re: Salt in encrypted password in pg_shadow

Richard Huxton <dev@archonet.c om> writes:[color=blue]
> David Garamond wrote:[color=green]
>> Consider someone who creates a long list of:
>> MD5( "postgres" + "aaaaaaaa" )
>> MD5( "postgres" + "aaaaaaab" )
>> MD5( "postgres" + "aaaaaaac" )[/color][/color]
[color=blue]
> But surely you have to store the random salt in pg_shadow too? Or am I
> missing something?[/color]

I think David is suggesting that the hypothetical attacker could gain
economies of scale in multiple attacks (ie, if he'd been able to steal
the contents of multiple installations' pg_shadow, he'd only need to
generate his long list of precalculated hashes once). I think this is
too far-fetched to justify an authentication protocol change though.

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.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddres sHere" to majordomo@postg resql.org)

[David Garamond]

Re: Salt in encrypted password in pg_shadow

Tom Lane wrote:[color=blue]
> I think David is suggesting that the hypothetical attacker could gain
> economies of scale in multiple attacks (ie, if he'd been able to steal
> the contents of multiple installations' pg_shadow, he'd only need to
> generate his long list of precalculated hashes once). I think this is
> too far-fetched to justify an authentication protocol change though.
>
> 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.[/color]

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 considering many people use the
same password for several things, Postgres could become one of the easy
sources to get/guess people's plaintext passwords from hacked machines.

At least Apache and Unix have been random-salting passwords for a while now.

However, I realize this will break the current MD5 hash, probably too
painful to do at the moment. Perhaps for the future, non-MD5 hash...

--
dave

---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings

[Tom Lane]

Re: Salt in encrypted password in pg_shadow

David Garamond <lists@zara.6.i sreserved.com> writes:[color=blue]
> Tom Lane wrote:[color=green]
>> 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.[/color][/color]
[color=blue]
> 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.[/color]

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.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postg resql.org so that your
message can get through to the mailing list cleanly

[Steve Atkins]

Re: Salt in encrypted password in pg_shadow

On Tue, Sep 07, 2004 at 03:09:28PM -0400, Tom Lane wrote:[color=blue]
> David Garamond <lists@zara.6.i sreserved.com> writes:[color=green]
> > Tom Lane wrote:[color=darkred]
> >> 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.[/color][/color]
>[color=green]
> > 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.[/color]
>
> 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.[/color]

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

---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings

[David Garamond]

Re: Salt in encrypted password in pg_shadow

Tom Lane wrote:[color=blue][color=green]
>>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.[/color]
>
> 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.[/color]

Hm, I thought the purpose of salt is generally well understood? A
well-known string such as "postgres" is *not* a good salt at all.

Here's a couple of pages that hopefully can explain better:

http://en.wikipedia.org/wiki/Dictionary_attack

http://en.wikipedia.org/wiki/Salt_(cryptography)

--
dave

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org

[Tom Lane]

Re: Salt in encrypted password in pg_shadow

Steve Atkins <steve@blighty. com> writes:[color=blue]
> 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.[/color]

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

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

[Tom Lane]

Re: Salt in encrypted password in pg_shadow

David Garamond <lists@zara.6.i sreserved.com> writes:[color=blue]
> Hm, I thought the purpose of salt is generally well understood?[/color]

Apparently not.

The purpose of salting the encrypted passwords in pg_shadow is *not* to
protect them against attackers who have somehow managed to
illegitimately read pg_shadow. (As I explained before, such attackers
are effectively superuser already, and so protecting the superuser
password from them is not nearly as interesting as all that.) The
purpose is to prevent unscrupulous DBAs from deducing the cleartext
passwords being used by their users. Since the users presumably are not
all named "postgres", the argument you are advancing is not relevant.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faqs/FAQ.html

[Greg Stark]

Re: Salt in encrypted password in pg_shadow


Tom Lane <tgl@sss.pgh.pa .us> writes:
[color=blue]
> Steve Atkins <steve@blighty. com> writes:[color=green]
> > A random salt stored with the hashed password increases the storage[/color][/color]
....[color=blue]
> [ 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.[/color]

*Storage* requirements. There's a pretty big range in the middle where the
extra 2^16 does make the difference.

The entire premise of cryptographic hashes after all depends on the assumption
that you cannot simply store an index of every possible hash value with the
plain-text that generated it.

That's only true if the number of plain-texts of concern is large enough to
make storing the hash value of each impractical. That's not true for human
chosen guessable passwords.

Now it's true that if you only want to try the top 1,000 guessable passwords
and you store a dictionary of all those with all 2^16 possible salts then it
requires only a gigabyte of storage. Perhaps a four character random salt
would make more sense.

However with a known salt you only have to store the 1,000 hashes with the
known salt. You could instead store a dictionary of 64 million password
guesses in the same gigabyte.

There's no question using a predictable salt is bad idea, postgres may as well
have not bothered salting at all. But realistically it seems kind of
irrelevant. It seems pretty unlikely that someone will gain access to
pg_shadow on many postgres installs which is the only way a dictionary attack
becomes a worry.

pg_shadow is not a public /etc/passwd like on a traditional unix machine where
I first saw salted crypt strings and it doesn't have hundreds or thousands of
entries like a public unix machine (at least not with predictable salts). The
threat model just doesn't apply.

--
greg


---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

[Steve Atkins]

Re: Salt in encrypted password in pg_shadow

On Tue, Sep 07, 2004 at 10:27:40PM -0400, Tom Lane wrote:[color=blue]
> Steve Atkins <steve@blighty. com> writes:[color=green]
> > 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.[/color]
>
> [ 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.[/color]

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.


---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

[Steve Atkins]

Re: Salt in encrypted password in pg_shadow

On Tue, Sep 07, 2004 at 08:48:13PM -0700, Steve Atkins wrote:
[color=blue]
> That's an example of why a salt is still extremely valuable, despite
> the change in CPU speed:storage speed/size ration[/color]

But, to clarify, I don't see any practical problem in the current
PostgreSQL implementation. It's not particularly secure, but not much
worse than the underlying OS authentication. Most of the feasible
attack trees are going to start with compromising the OS platform, by
which point weaknesses in the postgresql authentication are fairly
meaningless.

If we need to tweak the authentication protocol _anyway_ at some
point it'd be great to improve things. But until then... not worth
the pain.

Cheers,
Steve

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org

[Tom Lane]

Re: Salt in encrypted password in pg_shadow

Greg Stark <gsstark@mit.ed u> writes:[color=blue]
> However with a known salt you only have to store the 1,000 hashes with the
> known salt. You could instead store a dictionary of 64 million password
> guesses in the same gigabyte.[/color]

This is still not responding to my original point though: if you know
the salt that was used, you can try brute-force scan of a few thousand
probable passwords in less CPU time than it will take to read a gigabyte
of precomputed hashes. The fact that common passwords are much shorter
than the fixed-size MD5 hashes works against you in a big way.

I think the only way for the defender to get any real traction is to not
store the random salt right next to the encrypted password, so that the
attacker who hypothetically has read pg_shadow still has to guess about
the salt that was used. If someone shows me a plausible way to do that,
I'm all ears.
[color=blue]
> The threat model just doesn't apply.[/color]

This we agree on ...

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend