Thread: Postgres: pg_hba.conf, md5, pg_shadow, encrypted passwords

Greetings,
 There appears to be some deficiencies in both the documentation of the 'md5' authentication methology (in pg_hba.conf)
andin the md5 hash generation which is stored in pg_shadow. 
 The md5 hash which is generated for and stored in pg_shadow does not use a random salt but instead uses the username
whichcan generally be determined ahead of time (especially for the 'postgres' superuser account).  This would allow for
thepregeneration of the entire md5 keyspace using that 'salt' and then quick breakage of the hash once it's retrieved
bythe attacker.  Were a decent random salt of some size used it would be difficult to guess and pregenerate the
keyspacefor.  Thus, keyspace generation would have to happen after pg_shadow was compramised, giving the admin time to
detectthe compramise and take corrective action. 
 A larger issue, which plays into the pg_shadow storage issue somewhat, is the lack of proper documentation of the
'md5'method of authentication available via pg_hba.conf.  When using the 'md5' method in pg_hba.conf this is what
happens:
 server sends a randomly generated 'seed' to the client client performs md5(md5(password+username)+salt) using the salt
from  the server and information provided by the user and sends the result   to the server server performs
md5(hash+salt)using the salt it sent to the client   and the hash which is stored in pg_shadow. 
 In so doing the server has effectively made the hash which is stored in pg_shadow the key for authentication- the
user'spassword is no longer necessary to authenticate to the database, only the hash from pg_shadow is required.  It is
notclear in the documentation that using 'md5' in pg_hba.conf defeats 'with encrypted password' and the hashing in
pg_shadow. It is also not made clear that if you are already handling transport-level security via SSL and/or IPSEC
thatusing md5 actually reduces security by not adding anything to the transport-level security and defeating the
on-disksecurity effectivness of using md5 for pg_shadow. 
 It is true that while Postgres continues to use a known salt for hash generation the effectiveness of md5 hashes in
pg_shadowis reduced, though not entirely defeated as not all have resources to generate the keyspace for a username
witha decent password (as the 'postgres' superuser should have) or to generate the keyspace for any number of user
accountswhich are the targetted accounts. 
 If password-based authentication is required (and other methods such as Kerberos are unavailable), then, personally I
would:
 Discourage the use of 'md5' in pg_hba.conf and favor 'password' Use good transport-level security via SSL and/or IPSEC
Changethe hashing for what goes into pg_shadow to use a randomly    generated salt instead of the username (this would
require   changing the protocol to allow for that randomly generated salt    to be provided to the client when 'md5' is
beingused in    pg_hba.conf); an alternative might be to use PAM in the meantime  Update the documetation accordingly
tobe clear on the issues  As soon as possible provide other hash algorithms such as sha1/2 
  I discussed this issue on IRC w/ some folks already though generally  they didn't appear to share my level of concern
overthis.  My  biggest concern is that using 'md5' in pg_hba.conf reduces security  when another transport-level
securitymechanism is in place by a  significant amount, in my view, and this isn't clear in the  documentation.
Thanksfor you time, happy to answer any questions/comments on my  analysis. 
      Stephen

Stephen Frost <sfrost@snowman.net> writes:
>   The md5 hash which is generated for and stored in pg_shadow does not
>   use a random salt but instead uses the username which can generally be
>   determined ahead of time (especially for the 'postgres' superuser
>   account).

So?

The fact that we encrypt the contents of pg_shadow at all is not to
provide security against breakins by people who have managed to
obtain the contents of pg_shadow.  Any such attacker knows as much as
the postmaster does, and so there isn't anything much the postmaster can
do to prevent a breakin.  The reason we do it is to prevent such a
person (or a dishonest DBA) from obtaining the user's actual original
password.  This doesn't improve the security of the database at all,
of course, but it does improve security globally if the user used the
same password for other systems.

>   This would allow for the pregeneration of the entire md5
>   keyspace using that 'salt' and then quick breakage of the hash once
>   it's retrieved by the attacker.

Considering the size of the possible keyspace, this is pretty silly.

>   Were a decent random salt of some
>   size used it would be difficult to guess and pregenerate the keyspace
>   for.  Thus, keyspace generation would have to happen after pg_shadow
>   was compramised, giving the admin time to detect the compramise and
>   take corrective action.

Another large assumption: that the admin knows about the compromise
before the results are used.

>.  It is also not made clear that if you are
>   already handling transport-level security via SSL and/or IPSEC that
>   using md5 actually reduces security by not adding anything to the
>   transport-level security and defeating the on-disk security
>   effectivness of using md5 for pg_shadow.

That's simply false.  The contents of pg_shadow are never sent over the
wire.

You're going to have to work a lot harder to convince us there's any
significant issue here.
        regards, tom lane

On Wed, Apr 20, 2005 at 05:03:18PM -0400, Tom Lane wrote:
> >   This would allow for the pregeneration of the entire md5
> >   keyspace using that 'salt' and then quick breakage of the hash once
> >   it's retrieved by the attacker.
> 
> Considering the size of the possible keyspace, this is pretty silly.

Actually, it's not as silly as you think. You can download rainbow
tables for Windows/LanMan passwords up to 14 or 15 characters in length.
Given the password hash and some code, you can determine the user's
password in a matter of minutes.

Simply put, MD5 is no longer strong enough for protecting secrets. It's
just too easy to brute-force. SHA1 is ok for now, but it's days are
numbered as well. I think it would be good to alter SHA1 (or something
stronger) as an alternative to MD5, and I see no reason not to use a
random salt instead of username.
-- 
Jim C. Nasby, Database Consultant               decibel@decibel.org 
Give your computer some brain candy! www.distributed.net Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"

"Jim C. Nasby" <decibel@decibel.org> writes:
> Simply put, MD5 is no longer strong enough for protecting secrets. It's
> just too easy to brute-force. SHA1 is ok for now, but it's days are
> numbered as well. I think it would be good to alter SHA1 (or something
> stronger) as an alternative to MD5, and I see no reason not to use a
> random salt instead of username.

Well, I have no particular problem with offering SHA1 as an alternative
hash method for those who find MD5 too weak ... but I still question the
value of putting any random salt in the table.  AFAICS you would have to
send that salt as part of the initial password challenge, which means
any potential attacker could find it out even before trying to
compromise pg_shadow; so Stephen's argument that there is a useful
improvement in protection against precomputation of password hashes
still falls down.

BTW, one could also ask exactly what threat model Stephen is concerned
about.  ISTM anyone who can obtain the contents of pg_shadow has
*already* broken your database security.
        regards, tom lane

On Wed, Apr 20, 2005 at 06:03:18PM -0400, Tom Lane wrote:
> Well, I have no particular problem with offering SHA1 as an alternative
> hash method for those who find MD5 too weak ... but I still question the
> value of putting any random salt in the table.  AFAICS you would have to
> send that salt as part of the initial password challenge, which means
> any potential attacker could find it out even before trying to
> compromise pg_shadow; so Stephen's argument that there is a useful
> improvement in protection against precomputation of password hashes
> still falls down.
> 
> BTW, one could also ask exactly what threat model Stephen is concerned
> about.  ISTM anyone who can obtain the contents of pg_shadow has
> *already* broken your database security.

FWIW, I do think there's some benefit to not being able to pre-compute
an entire hash table for accounts such as 'postgres' and 'www'. But I
agree it would be useful to know the actual threat model.
-- 
Jim C. Nasby, Database Consultant               decibel@decibel.org 
Give your computer some brain candy! www.distributed.net Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"

Tom Lane wrote:
> "Jim C. Nasby" <decibel@decibel.org> writes:
> > Simply put, MD5 is no longer strong enough for protecting secrets. It's
> > just too easy to brute-force. SHA1 is ok for now, but it's days are
> > numbered as well. I think it would be good to alter SHA1 (or something
> > stronger) as an alternative to MD5, and I see no reason not to use a
> > random salt instead of username.
> 
> Well, I have no particular problem with offering SHA1 as an alternative
> hash method for those who find MD5 too weak ... but I still question the
> value of putting any random salt in the table.  AFAICS you would have to
> send that salt as part of the initial password challenge, which means
> any potential attacker could find it out even before trying to
> compromise pg_shadow; so Stephen's argument that there is a useful
> improvement in protection against precomputation of password hashes
> still falls down.
> 
> BTW, one could also ask exactly what threat model Stephen is concerned
> about.  ISTM anyone who can obtain the contents of pg_shadow has
> *already* broken your database security.

That's what I told him.  I think his concern about pre-computed hashes
is the only real issue, and give 'postgres' is usually the super-user, I
can see someone pre-computing md5 postgres hashes and doing quick
comparisons, perhaps as a root kit so you don't have to do the hashing
yourself.   I personally don't find that very compelling either.

--  Bruce Momjian                        |  http://candle.pha.pa.us pgman@candle.pha.pa.us               |  (610)
359-1001+  If your life is a hard drive,     |  13 Roberts Road +  Christ can be your backup.        |  Newtown Square,
Pennsylvania19073
 

Bruce Momjian <pgman@candle.pha.pa.us> writes:
> That's what I told him.  I think his concern about pre-computed hashes
> is the only real issue, and give 'postgres' is usually the super-user, I
> can see someone pre-computing md5 postgres hashes and doing quick
> comparisons, perhaps as a root kit so you don't have to do the hashing
> yourself.   I personally don't find that very compelling either.

Lessee ... we'll include a complete password hash table in a root kit,
which will be used at a point where we've already managed to read
pg_shadow but are somehow still lacking the ability to do anything else
we could want to the database ... nope, not very compelling.
        regards, tom lane

Bruce Momjian wrote:

>>BTW, one could also ask exactly what threat model Stephen is concerned
>>about.  ISTM anyone who can obtain the contents of pg_shadow has
>>*already* broken your database security.
> That's what I told him.  I think his concern about pre-computed hashes
> is the only real issue, and give 'postgres' is usually the super-user, I
> can see someone pre-computing md5 postgres hashes and doing quick
> comparisons, perhaps as a root kit so you don't have to do the hashing
> yourself.   I personally don't find that very compelling either.

The issue is that you should try your best to prevent dictionary attacks,
because often people use the same passwords for different things.
I know they shouldn't, but sometimes they do, so any measures you can
take to make a dictionary attack harder are worth doing, especially
when the random salt is so simple to implement.

--
David.

Tom Lane wrote:

>Bruce Momjian <pgman@candle.pha.pa.us> writes:
>  
>
>>That's what I told him.  I think his concern about pre-computed hashes
>>is the only real issue, and give 'postgres' is usually the super-user, I
>>can see someone pre-computing md5 postgres hashes and doing quick
>>comparisons, perhaps as a root kit so you don't have to do the hashing
>>yourself.   I personally don't find that very compelling either.
>>    
>>
>
>Lessee ... we'll include a complete password hash table in a root kit,
>which will be used at a point where we've already managed to read
>pg_shadow but are somehow still lacking the ability to do anything else
>we could want to the database ... nope, not very compelling.
>
>
>  
>
[bugtraq removed - I don't think this belongs there, at least at this stage]

/etc/shadow is supposedly only readable by root (or things that are 
setuid root). If you have root you already own the box. Yet we store 
passwords there hashed with random salt.

My understanding is that Stephen would like a system where clear 
passwords are never stored. He's right in saying that our "encrypted" 
passwords are in effect cleartext, as a malicious client would only ever 
need to know the hashed pw to gain access, and not the original 
cleartext. Of course, adding random salt won't change that, and you are 
quite right in saying that the random salt would have to be sent as part 
of the challenge.

There's a choice between protecting the password over the wire via a 
challenge/response system, and protecting it in storage. Postgres has 
quite reasonably chosen the former. Stephen says "Well, I can protect 
the wire comms via ssh or IPSEC, and I'd like storage protection too." 
That also seems reasonable, although I don't think the sky is really 
falling in.

Lastly, I have seen Jan say several times (on IRC) that mission-critical 
DBs should not be exposed to untrusted networks, but always protected by 
appropriate middleware. I could not agree more.

cheers

andrew

Tom Lane wrote:

> Lessee ... we'll include a complete password hash table in a root kit,
> which will be used at a point where we've already managed to read
> pg_shadow but are somehow still lacking the ability to do anything else
> we could want to the database ... nope, not very compelling.

You are correct that the threat against the PostgreSQL installation itself
is not very compelling.  However, take a look at the bigger picture:
People crack into systems and then try to use those systems to crack
into other systems.  If you can make it harder to recover passwords
in the PostgreSQL system, then you've made it harder for attackers
to use those recovered passwords to attack other systems.

Think of the complete security environment, not just the security
of a particular PostgreSQL installation.  Having random salts makes
it much harder for attackers to answer questions like "Does user X
have the same password in PostgreSQL installation 1 as he does in PostgreSQL
installation 2".

Regards,

David.

* Tom Lane (tgl@sss.pgh.pa.us) wrote:
> Stephen Frost <sfrost@snowman.net> writes:
> >   The md5 hash which is generated for and stored in pg_shadow does not
> >   use a random salt but instead uses the username which can generally be
> >   determined ahead of time (especially for the 'postgres' superuser
> >   account).
>
> So?
>
> The fact that we encrypt the contents of pg_shadow at all is not to
> provide security against breakins by people who have managed to
> obtain the contents of pg_shadow.  Any such attacker knows as much as
> the postmaster does, and so there isn't anything much the postmaster can
> do to prevent a breakin.  The reason we do it is to prevent such a
> person (or a dishonest DBA) from obtaining the user's actual original
> password.  This doesn't improve the security of the database at all,
> of course, but it does improve security globally if the user used the
> same password for other systems.

A dishonest DBA would have no trouble obtaining the user's actual
original password regardless through any number of means, both technical
and social.  I can go into them if you'd like but the first one would
probably be just change pg_hba.conf to say 'password' instead of 'md5'
and you're basically done.

Additionally, a dishonest DBA has no need for the original password if
the user has the same username on multiple postgres databases (not
exactly unlikely) and those postgres systems use 'md5' in pg_hba.conf.
This is because when using the 'md5' mechanism in pg_hba.conf the
original password is irrelevant, all that matters is the
password+username hash, which is exactly what's stored in pg_shadow.

Were other systems such as ssh to use this same mechanism then again for
those you would not need the original password but only the hash in
order to authenticate yourself.  Thus, claiming that you're protecting
the user from a dishonest DBA is, imv, at best a false sense of
security.

> >   This would allow for the pregeneration of the entire md5
> >   keyspace using that 'salt' and then quick breakage of the hash once
> >   it's retrieved by the attacker.
>
> Considering the size of the possible keyspace, this is pretty silly.

Not as silly as I wish it was. :/

> >   Were a decent random salt of some
> >   size used it would be difficult to guess and pregenerate the keyspace
> >   for.  Thus, keyspace generation would have to happen after pg_shadow
> >   was compramised, giving the admin time to detect the compramise and
> >   take corrective action.
>
> Another large assumption: that the admin knows about the compromise
> before the results are used.

It would be nice to give the admin some time to detect the compromise.
If a known salt is used then the admin gets essentially no time.  If a
random salt is used then the admin will have at least some time while
the attacker generates the keyspace to find a cleartext version to pass
to the server- provided the server is using 'password' and *not* 'md5'
in pg_hba.conf.  If the server is using 'md5' in pg_hba.conf then all is
lost as soon as pg_shadow is compromised.

> >.  It is also not made clear that if you are
> >   already handling transport-level security via SSL and/or IPSEC that
> >   using md5 actually reduces security by not adding anything to the
> >   transport-level security and defeating the on-disk security
> >   effectivness of using md5 for pg_shadow.
>
> That's simply false.  The contents of pg_shadow are never sent over the
> wire.

I didn't mean to suggest that they were.  However, if you use 'md5' in
pg_hba.conf then what is stored in pg_shadow might as well be the
original password since it is all that is required to authenticate.
Sure, technically you also need the salt from the server for the
transport-md5-hash, but the server gives that to you and then all you
have to do is a simple md5hash.

> You're going to have to work a lot harder to convince us there's any
> significant issue here.

Happy to do my best.  Hope this helps some.  I strongly feel that using
'md5' in pg_hba.conf when using SSL or IPSEC should be strongly
discouraged.  It adds nothing in that case and does some harm in the
event pg_shadow is compromised (through stealing of a backup tape, or a
partial compromise of the system whereby an attacker is able to gain
privledged access to read part of a file or similar).
Thanks,    Stephen

* Tom Lane (tgl@sss.pgh.pa.us) wrote:
> "Jim C. Nasby" <decibel@decibel.org> writes:
> > Simply put, MD5 is no longer strong enough for protecting secrets. It's
> > just too easy to brute-force. SHA1 is ok for now, but it's days are
> > numbered as well. I think it would be good to alter SHA1 (or something
> > stronger) as an alternative to MD5, and I see no reason not to use a
> > random salt instead of username.
>
> Well, I have no particular problem with offering SHA1 as an alternative
> hash method for those who find MD5 too weak ... but I still question the

SHA2 would also be nice.

> value of putting any random salt in the table.  AFAICS you would have to
> send that salt as part of the initial password challenge, which means
> any potential attacker could find it out even before trying to
> compromise pg_shadow; so Stephen's argument that there is a useful
> improvement in protection against precomputation of password hashes
> still falls down.

Only if you're using 'md5' in pg_hba.conf.  In that case, yes, you would
have to send the salt as part of the password challenge.  Personally, I
would discourage use of 'md5' in pg_hba.conf because of this and because
it changes the authentication token from the password to the hash which
is what is directly stored in the database.

> BTW, one could also ask exactly what threat model Stephen is concerned
> about.  ISTM anyone who can obtain the contents of pg_shadow has
> *already* broken your database security.

Just because they have access to pg_shadow does not necessairly mean
they have access to the database files directly or are able to write to
anything (such as to destroy data).  It's possible they pulled
pg_shadow off a backup tape and are bent on destroying all the data in
your live database, and not in just reading it, or if your data is very
time sensitive then they want a more recent version for its value, etc.

There are other possibilities but my concern centers around a partial
system compromise where pg_shadow is obtained by the attacker, yes.
Thanks,
    Stephen

* Andrew Dunstan (andrew@dunslane.net) wrote:
> [bugtraq removed - I don't think this belongs there, at least at this stage]

Sure.

> /etc/shadow is supposedly only readable by root (or things that are
> setuid root). If you have root you already own the box. Yet we store
> passwords there hashed with random salt.

Right, exactly.

> My understanding is that Stephen would like a system where clear
> passwords are never stored. He's right in saying that our "encrypted"
> passwords are in effect cleartext, as a malicious client would only ever
> need to know the hashed pw to gain access, and not the original
> cleartext. Of course, adding random salt won't change that, and you are
> quite right in saying that the random salt would have to be sent as part
> of the challenge.

No, adding a random salt wouldn't change that, that's a direct flaw of
the 'md5' mechanism in pg_hba.conf.  However, I can choose not to use
the 'md5' mechanism in pg_hba.conf and can use 'password' instead.
There's not currently an option to say "use a random salt instead of the
username as the salt" for those of us concerned both about people
sniffing the wire and compromising pg_shadow.

> There's a choice between protecting the password over the wire via a
> challenge/response system, and protecting it in storage. Postgres has
> quite reasonably chosen the former. Stephen says "Well, I can protect
> the wire comms via ssh or IPSEC, and I'd like storage protection too."
> That also seems reasonable, although I don't think the sky is really
> falling in.

Right.

> Lastly, I have seen Jan say several times (on IRC) that mission-critical
> DBs should not be exposed to untrusted networks, but always protected by
> appropriate middleware. I could not agree more.

I agree with this also, of course, but there's only so much one can
do and security in layers...
Stephen

Am Mittwoch, den 20.04.2005, 16:23 -0500 schrieb Jim C. Nasby:
> On Wed, Apr 20, 2005 at 05:03:18PM -0400, Tom Lane wrote:
...
> Simply put, MD5 is no longer strong enough for protecting secrets. It's
> just too easy to brute-force. SHA1 is ok for now, but it's days are
> numbered as well. I think it would be good to alter SHA1 (or something
> stronger) as an alternative to MD5, and I see no reason not to use a
> random salt instead of username.

I wonder where you want to store that random salt and how this would add
to the security.

-- 
Tino Wildenhain <tino@wildenhain.de>

On Thu, 2005-04-21 at 11:06 +0200, Tino Wildenhain wrote:
> Am Mittwoch, den 20.04.2005, 16:23 -0500 schrieb Jim C. Nasby:
> > On Wed, Apr 20, 2005 at 05:03:18PM -0400, Tom Lane wrote:
> ...
> > Simply put, MD5 is no longer strong enough for protecting secrets. It's
> > just too easy to brute-force. SHA1 is ok for now, but it's days are
> > numbered as well. I think it would be good to alter SHA1 (or something
> > stronger) as an alternative to MD5, and I see no reason not to use a
> > random salt instead of username.
> 
> I wonder where you want to store that random salt and how this would add
> to the security.

One advantage of a random salt would be that the username can be changed
without having to reset the password at the same time.

-- 

Am Donnerstag, den 21.04.2005, 09:32 -0400 schrieb Rod Taylor:
> On Thu, 2005-04-21 at 11:06 +0200, Tino Wildenhain wrote:
> > Am Mittwoch, den 20.04.2005, 16:23 -0500 schrieb Jim C. Nasby:
> > > On Wed, Apr 20, 2005 at 05:03:18PM -0400, Tom Lane wrote:
> > ...
> > > Simply put, MD5 is no longer strong enough for protecting secrets. It's
> > > just too easy to brute-force. SHA1 is ok for now, but it's days are
> > > numbered as well. I think it would be good to alter SHA1 (or something
> > > stronger) as an alternative to MD5, and I see no reason not to use a
> > > random salt instead of username.
> > 
> > I wonder where you want to store that random salt and how this would add
> > to the security.
> 
> One advantage of a random salt would be that the username can be changed
> without having to reset the password at the same time.

Still this does not answer the question where that salt is to be
stored :)

(instead of username one could use somefacyhash(userid) to be 
independend from username - otoh, if you change usernames 
you usually face some other serious problems like object
ownership and friends)
-- 
Tino Wildenhain <tino@wildenhain.de>

> Simply put, MD5 is no longer strong enough for protecting secrets. It's
> just too easy to brute-force. SHA1 is ok for now, but it's days are
> numbered as well. I think it would be good to alter SHA1 (or something
> stronger) as an alternative to MD5, and I see no reason not to use a
> random salt instead of username.

If you aren't paying close enough attention to your database server to
see that someone is trying to brute force your MD5 password you have 
bigger problems.

Sincerely,

Joshua D. Drake





-- 
Your PostgreSQL solutions company - Command Prompt, Inc. 1.800.492.2240
PostgreSQL Replication, Consulting, Custom Programming, 24x7 support
Managed Services, Shared and Dedication Hosting
Co-Authors: plPHP, plPerlNG - http://www.commandprompt.com/

Joshua Drake wrote:

> If you aren't paying close enough attention to your database server to
> see that someone is trying to brute force your MD5 password you have 
> bigger problems.

Everybody is completely missing the point. :-(

The point of a random salt is *NOT* to increase the security of your
particular PostgreSQL installation.  A random salt won't help that at
all.

The point of the random salt *IS* to make it harder for an attacker
who has compromised your system to derive the plain-text passwords
from the hashes.  Attackers love to derive plain-text passwords
because the odds are very good they can be used to compromise a
*different* system.  (Come on, be honest, how many people here have
the same password on more than one system, or the same PostgreSQL
password as UNIX login password?)

The "information leakage" scenario mentioned earlier, whereby
attackers could determine valid user names, is trivial to defeat: If
the user name exists, return the salt in the password table.  If not,
return an algorithmically derived salt md5(username + x) where "x"
is some server-wide parameter that's set to a random number upon
installation.

We have an application that requires customers to log into our site.
We store passwords in cleartext.  However, these passwords are randomly
generated *by us* and we don't allow customers to choose them.  So if
our server is compromised, (a) we don't care if the attacker gets the
customers' passwords, because they've already compromised the server, and
(b) the customers' passwords are useless for anything else, so the security
of our customers is not compromised.

Regards,

David.

* Joshua D. Drake (jd@commandprompt.com) wrote:
> >Simply put, MD5 is no longer strong enough for protecting secrets. It's
> >just too easy to brute-force. SHA1 is ok for now, but it's days are
> >numbered as well. I think it would be good to alter SHA1 (or something
> >stronger) as an alternative to MD5, and I see no reason not to use a
> >random salt instead of username.
>
> If you aren't paying close enough attention to your database server to
> see that someone is trying to brute force your MD5 password you have
> bigger problems.

If the attacker knows the salt then she can do almost all of the
brute-force work up-front before even attempting to attack the system
directly.  The sys admin would have no way of knowing this was
happening.  Once this is done the attacker just needs the hash from
pg_shadow to quickly find the user's password (or something that hashes
to the same thing).

In this situation I'm assuming the system is using the 'password'
method in pg_hba.conf.  If the system used the 'md5' method in
pg_hba.conf the attacker would need only the hash from pg_shadow to
authenticate and wouldn't need the users original password at all.

If a random salt were used in this situation, and 'password' were used
in pg_hba.conf then the attacker would be unable to determine the salt
ahead of time and would be forced to generate the keyspace after
obtaining pg_shadow to brute-force the password, a time consuming
process hopefully given the admin an opportunity to discover the
compromise.
Thanks,
    Stephen

* Josh Berkus (josh@agliodbs.com) wrote:
> David, Stephen,

[Changed back to pgsql-hackers]

> Well, from our perspective, a random salt only protects against a very narrow
> range of attack types -- ones in which the attacker already has access to the
> physical database and wants to reverse-engineer user's passwords.  We'd be
> much more interested in the implementation of more/better authentication
> mechanisms.   See follow-up dicussion on pgsql-hackers.

I'm concerned about both using a random salt in pg_shadow and about
better documentation about what happens when you use 'md5' in
pg_hba.conf.

> Of course, if either of you *wrote* a random-salt patch for PostgreSQL, psql
> and libpq, then that would be a different story.   I don't know that anyone
> has anything *against* a random salt.   It's just not nearly as useful as,
> for example, implementing SHA1.

It was generally my understanding that it was better to get it
'sanctioned' and on the TODO list before just writing something up and
expecting it to be included.  I've already offered elsewhere to work on
writing a random-salt patch for PostgreSQL targeted at 8.1 and this
encourages me further.  I understand that I'd need to be sure it was
backwards compatible to some extent (do both older client <-> newer
server and newer client <-> older server need to work?  I seem to recall
only older client <-> newer server had to work, but perhaps I'm not
remembering right).
Stephen

Stephen,

> I'm concerned about both using a random salt in pg_shadow and about
> better documentation about what happens when you use 'md5' in
> pg_hba.conf.

Yep, per our conversation on IRC.  Frankly, I responded on Bugtraq mainly to 
the other person's comment that we'd been ignoring the issue since 2002.  Few 
of the people on bugtraq read pgsql-hackers and I didn't want to leave them 
with the impression that our group ignored security threats.

> It was generally my understanding that it was better to get it
> 'sanctioned' and on the TODO list before just writing something up and
> expecting it to be included. 

Absolutely.

> I've already offered elsewhere to work on 
> writing a random-salt patch for PostgreSQL targeted at 8.1 and this
> encourages me further.  I understand that I'd need to be sure it was
> backwards compatible to some extent (do both older client <-> newer
> server and newer client <-> older server need to work?  I seem to recall
> only older client <-> newer server had to work, but perhaps I'm not
> remembering right).

Actually, I think older client <-> newer server is the least critical.   We'd 
be incrementing libpq for this.  Right, Bruce?

While you're at it, maybe you should look at ways that pg_shadow could be 
double-encrypted on backup but still restored easily?

-- 
Josh Berkus
Aglio Database Solutions
San Francisco

Josh,

* Josh Berkus (josh@agliodbs.com) wrote:
> Actually, I think older client <-> newer server is the least critical.   We'd
> be incrementing libpq for this.  Right, Bruce?

I'm not 100% sure that libpq's API/ABI would need to change for this,
which is what would cause an SONAME change.  This will probably require
a protocol change if we're going to continue to support the 'md5' option
in pg_hba.conf so that the protocol will allow for the server to send
the randomly generated salt to the client.

> While you're at it, maybe you should look at ways that pg_shadow could be
> double-encrypted on backup but still restored easily?

That's an interesting thought.  That's actually what a Kerberos KDC does
(encrypts the database with all of the hashes to protect tem) since
the hashes are the keys in Kerberos (and as such the users actual
original password isn't necessary).  Of course, to do it safely you'd
have to *not* store the 'master' pg_shadow password on the system, which
means you'd have to have someone manually start Postgres after the box
boots.

I do this for my KDCs but thankfully there's only very few of those,
doing it for Postgres would probably be much more annoying I'd think-
but then, if you're having Postgres store your passwords instead of
Kerberos (which is what I *normally* do, this particular case is a
special one for me where I can't use Kerberos) then perhaps it makes
sense, at least as an option.
Thanks,    Stephen

Josh Berkus wrote:
> > I've already offered elsewhere to work on 
> > writing a random-salt patch for PostgreSQL targeted at 8.1 and this
> > encourages me further.  I understand that I'd need to be sure it was
> > backwards compatible to some extent (do both older client <-> newer
> > server and newer client <-> older server need to work?  I seem to recall
> > only older client <-> newer server had to work, but perhaps I'm not
> > remembering right).
> 
> Actually, I think older client <-> newer server is the least critical.   We'd 
> be incrementing libpq for this.  Right, Bruce?

Yes, in fact we might need to change the wire protocol version, not just
the library major number.

--  Bruce Momjian                        |  http://candle.pha.pa.us pgman@candle.pha.pa.us               |  (610)
359-1001+  If your life is a hard drive,     |  13 Roberts Road +  Christ can be your backup.        |  Newtown Square,
Pennsylvania19073
 

On Wed, Apr 20, 2005 at 22:27:01 -0400, Stephen Frost <sfrost@snowman.net> wrote:
> 
> SHA2 would also be nice.

I think the new hash functions are called SHA256 and SHA512.
For Postgres' purposes the recent weaknesses found in SHA1 and MD5
aren't a big deal.

pgman wrote:
> Stephen Frost wrote:
> -- Start of PGP signed section.
> > * Andrew Dunstan (andrew@dunslane.net) wrote:
> > > The docs say: "only md5 supports encrypted passwords stored in
> > > pg_shadow; the other two require unencrypted passwords to be stored
> > > there."  So either your assertion that 'password' auth does not imply
> > > plaintext password storage is wrong, or the docs are.
> >
> > The docs are wrong.  Sorry, I knew that and forgot to mention it
> > explicitly previously.  Using 'password' in pg_hba.conf while using
> > 'with encrypted password'/md5 in pg_shadow works just fine.
> >
> > Just tested here to make 100% sure, under 8.0.1.
>
> I see the documentation is slightly confusing.  I have applied this
> patch to HEAD and 8.0.X to clarify it.

With the documentation text clarified, this patch fixes the actual
documentation problem that both 'password' and 'md5' supporte encrypted
pg_shadow passwords, while only crypt does not.  Applied to 8.0.X and
HEAD.

--
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073
Index: doc/src/sgml/client-auth.sgml
===================================================================
RCS file: /cvsroot/pgsql/doc/src/sgml/client-auth.sgml,v
retrieving revision 1.75
diff -c -c -r1.75 client-auth.sgml
*** doc/src/sgml/client-auth.sgml    21 Apr 2005 22:19:19 -0000    1.75
--- doc/src/sgml/client-auth.sgml    21 Apr 2005 22:23:47 -0000
***************
*** 575,583 ****
      The password-based authentication methods are <literal>md5</>,
      <literal>crypt</>, and <literal>password</>. These methods operate
      similarly except for the way that the password is sent across the
!     connection.  However, only <literal>md5</> allows encrypted
!     passwords to be stored in <structname>pg_shadow</structname>;
!     the other two require unencrypted passwords to be stored there.
     </para>

     <para>
--- 575,582 ----
      The password-based authentication methods are <literal>md5</>,
      <literal>crypt</>, and <literal>password</>. These methods operate
      similarly except for the way that the password is sent across the
!     connection.  However, <literal>crypt</> does not allow encrypted
!     passwords to be stored in <structname>pg_shadow</structname>.
     </para>

     <para>

* Bruce Momjian (pgman@candle.pha.pa.us) wrote:
> With the documentation text clarified, this patch fixes the actual
> documentation problem that both 'password' and 'md5' supporte encrypted
> pg_shadow passwords, while only crypt does not.  Applied to 8.0.X and
> HEAD.

Great, thanks.  Here's a suggestion to replace the last two sentences:

These methods differ in how the password is sent across the network and
in the meaning of what is stored in pg_shadow.

The 'password' method sends the password across the network in
plaintext which could allow someone sniffing the network to retrieve
it unless there is encryption being done in the transport layer (ie:
SSL or IPSEC).  Using the 'password' method the server will either
compare the provided password to what is stored in pg_shadow or, if
the 'with encrypted password' option was used to md5 the password in
pg_shadow, the server will concatenate the user's name to the
password and perform an md5 hash and compare that to what is in
pg_shadow.

With the 'md5' method the server will send will send a randomly
generated salt to the client which will then concatenate the user's name
to the password, perform an md5 on that result, then concatenate the
result of the md5 to the salt provided by the server and will then md5
that.  The client sends the result of that md5 to the server which then
reads what is in pg_shadow, which must be md5 using 'with encrypted
password', concatenates that with the random salt sent to client,
performs an md5 on the result and compares that to what was sent by the
client.  Note: this makes the md5 hash stored in pg_shadow what is known
as a 'password-equivilant', which means that an attacker does not need
the original password to authenticate to PostgreSQL, the attacker needs
only the hash which is stored directly in pg_shadow.  In other words, if
pg_shadow is compromised an attacker can then log into the database as
any user without any effort.
Thanks,    Stephen

* Bruno Wolff III (bruno@wolff.to) wrote:
> On Wed, Apr 20, 2005 at 22:27:01 -0400,
>   Stephen Frost <sfrost@snowman.net> wrote:
> > SHA2 would also be nice.
>
> I think the new hash functions are called SHA256 and SHA512.
> For Postgres' purposes the recent weaknesses found in SHA1 and MD5
> aren't a big deal.

Well, alright, SHA256 and SHA512.  It would be nice to have Postgres
support them.
Stephen

I think the behaviour on the wire should be more explcitly stated.

cheers

andrew

Bruce Momjian wrote:

>------------------------------------------------------------------------
>
>Index: doc/src/sgml/client-auth.sgml
>===================================================================
>RCS file: /cvsroot/pgsql/doc/src/sgml/client-auth.sgml,v
>retrieving revision 1.75
>diff -c -c -r1.75 client-auth.sgml
>*** doc/src/sgml/client-auth.sgml    21 Apr 2005 22:19:19 -0000    1.75
>--- doc/src/sgml/client-auth.sgml    21 Apr 2005 22:23:47 -0000
>***************
>*** 575,583 ****
>      The password-based authentication methods are <literal>md5</>,
>      <literal>crypt</>, and <literal>password</>. These methods operate
>      similarly except for the way that the password is sent across the
>!     connection.  However, only <literal>md5</> allows encrypted
>!     passwords to be stored in <structname>pg_shadow</structname>;
>!     the other two require unencrypted passwords to be stored there.
>     </para>
>  
>     <para>
>--- 575,582 ----
>      The password-based authentication methods are <literal>md5</>,
>      <literal>crypt</>, and <literal>password</>. These methods operate
>      similarly except for the way that the password is sent across the
>!     connection.  However, <literal>crypt</> does not allow encrypted
>!     passwords to be stored in <structname>pg_shadow</structname>.
>     </para>
>  
>     <para>
>  
>
>------------------------------------------------------------------------
>
>
>  
>

* Andrew Dunstan (andrew@dunslane.net) wrote:
> I think the behaviour on the wire should be more explcitly stated.

Please comment on the message I just sent to -hackers which has a much
longer and more detailed explanation of what happens.
Thanks,
    Stephen

Stephen Frost wrote:
-- Start of PGP signed section.
> * Andrew Dunstan (andrew@dunslane.net) wrote:
> > I think the behaviour on the wire should be more explcitly stated.
> 
> Please comment on the message I just sent to -hackers which has a much
> longer and more detailed explanation of what happens.

The next paragraph in the docs is:
   If you are at all concerned about password   <quote>sniffing</> attacks then <literal>md5</> is preferred, with
<literal>crypt</>a second choice if you must support pre-7.2   clients. Plain <literal>password</> should especially be
avoidedfor   connections over the open Internet (unless you use <acronym>SSL</acronym>, SSH, or   other communications
securitywrappers around the connection).
 

--  Bruce Momjian                        |  http://candle.pha.pa.us pgman@candle.pha.pa.us               |  (610)
359-1001+  If your life is a hard drive,     |  13 Roberts Road +  Christ can be your backup.        |  Newtown Square,
Pennsylvania19073
 

* Bruce Momjian (pgman@candle.pha.pa.us) wrote:
> Stephen Frost wrote:
> -- Start of PGP signed section.
> > * Andrew Dunstan (andrew@dunslane.net) wrote:
> > > I think the behaviour on the wire should be more explcitly stated.
> >
> > Please comment on the message I just sent to -hackers which has a much
> > longer and more detailed explanation of what happens.
>
> The next paragraph in the docs is:
>
>     If you are at all concerned about password
>     <quote>sniffing</> attacks then <literal>md5</> is preferred, with
>     <literal>crypt</> a second choice if you must support pre-7.2
>     clients. Plain <literal>password</> should especially be avoided for
>     connections over the open Internet (unless you use <acronym>SSL</acronym>, SSH, or
>     other communications security wrappers around the connection).

Huh, I thought I had looked and hadn't seen anything after the paragraph
you modified in the online stuff.  Apparently I was being deliusional.
Even so though, I think my description was somewhat more verbose and
useful.  A merge of the two may be in order actually, it's true that
sniffing attacks may be thwarted by the md5 method but this does not
mention that the hash in pg_shadow becomes password-equivilant in that
method and it really should.
Thanks,
    Stephen

Stephen Frost <sfrost@snowman.net> writes:

> With the 'md5' method the server will send will send a randomly
> generated salt to the client which will then concatenate the user's name
> to the password, perform an md5 on that result, then concatenate the
> result of the md5 to the salt provided by the server and will then md5
> that.  

I think that in this case calling it a salt altogether is wrong. It's a
"challenge".

And I'm inclined to suggest that this authentication method be removed
altogether. The security flaw is that it exists at all. Not the details of the
implementation.

-- 
greg

Greg Stark wrote:
> Stephen Frost <sfrost@snowman.net> writes:
> 
> > With the 'md5' method the server will send will send a randomly
> > generated salt to the client which will then concatenate the user's name
> > to the password, perform an md5 on that result, then concatenate the
> > result of the md5 to the salt provided by the server and will then md5
> > that.  
> 
> I think that in this case calling it a salt altogether is wrong. It's a
> "challenge".
> 
> And I'm inclined to suggest that this authentication method be removed
> altogether. The security flaw is that it exists at all. Not the details of the
> implementation.

That idea is so detached from reality, I don't know how to respond.

--  Bruce Momjian                        |  http://candle.pha.pa.us pgman@candle.pha.pa.us               |  (610)
359-1001+  If your life is a hard drive,     |  13 Roberts Road +  Christ can be your backup.        |  Newtown Square,
Pennsylvania19073
 

* Greg Stark (gsstark@mit.edu) wrote:
> Stephen Frost <sfrost@snowman.net> writes:
> > With the 'md5' method the server will send will send a randomly
> > generated salt to the client which will then concatenate the user's name
> > to the password, perform an md5 on that result, then concatenate the
> > result of the md5 to the salt provided by the server and will then md5
> > that.
>
> I think that in this case calling it a salt altogether is wrong. It's a
> "challenge".

Ah, yeah, you're right.

> And I'm inclined to suggest that this authentication method be removed
> altogether. The security flaw is that it exists at all. Not the details of the
> implementation.

I'm not quite sure it's as dire as all that.  It's intended to solve a
different problem.  As I recall, Kerberos does much the same, it takes
the password, the user's princ, performs a hash and uses *that* as
password-equiv by using it as the key to encrypt with.  One big reason
why you had better be *very* careful with your KDC, and why the KDC
encrypts its database again with the Master KDC password.  Additionally,
KDCs can be locked down and you can pretty easily set up slaves of them
for backup purposes and just not put the Master KDC password on the
system anywhere and type it in by hand when bringing up the system.

Unfortunately, Postgres doesn't currently encrypt pg_shadow and even if
it did you'd have to have the password stored on disk somewhere in the
clear if you wanted the database to start automatically, which is more
important if you havn't got backup databases and whatnot (which aren't
really as easy to set up w/ Postgres and generally Postgres requires
more disk space than a KDC).
Stephen

On Thu, 2005-04-21 at 17:27 -0500, Bruno Wolff III wrote:
> On Wed, Apr 20, 2005 at 22:27:01 -0400,
>   Stephen Frost <sfrost@snowman.net> wrote:
> > 
> > SHA2 would also be nice.
> 
> I think the new hash functions are called SHA256 and SHA512.
> For Postgres' purposes the recent weaknesses found in SHA1 and MD5
> aren't a big deal.
It is irrelevant here, if I am reading this correctly:
http://theory.csail.mit.edu/~yiqun/shanote.pdf
"collision search attacks"
Basically, multiple input data that have the same output hash, which is
of no use when what you are trying to find is the input.
Finding collisions quicker for a known input is one thing, but that is
not going to reduce the search space, not even your storage space (it is
unlikely that the colliding results would all be valid input).

Is adding the non-guessable salt that hard anyway?

Joshua D. Drake wrote:
>> Simply put, MD5 is no longer strong enough for protecting secrets. It's
>> just too easy to brute-force. SHA1 is ok for now, but it's days are
>> numbered as well. I think it would be good to alter SHA1 (or something
>> stronger) as an alternative to MD5, and I see no reason not to use a
>> random salt instead of username.
> 
> 
> If you aren't paying close enough attention to your database server to
> see that someone is trying to brute force your MD5 password you have 
> bigger problems.

The comments on md5 and sha1 are both inaccurate if you're comparing 
them. Encrypted passwords are as strong as the design of the password. 
In some cases, SHA-1 is a faster brute force because SHA-1 is a faster 
hash. There are two issues here. Using SHA-1 to hash a password, and the 
strength of a password. If the implementation of SHA-1 is not effective, 
there could be weaknesses that enable reducing the time required to 
perform exhaustive/dictionary attacks against sha-1 protected password.

I'm out of context, but I had to make some corrections.


-- 
Best Regards,
Lance James
Secure Science Corporation
www.securescience.com
Author of 'Phishing Exposed'
http://www.securescience.net/amazon/
Have Phishers stolen your customers' logins? Find out with DIA
https://slam.securescience.com/signup.cgi - it's free!    

Stephen Frost wrote:
> Unfortunately, Postgres doesn't currently encrypt pg_shadow and even if
> it did you'd have to have the password stored on disk somewhere in the 
> clear if you wanted the database to start automatically, which is more
> important if you havn't got backup databases and whatnot (which aren't
> really as easy to set up w/ Postgres and generally Postgres requires
> more disk space than a KDC).

Yeah, but who cares?  If the attacker has enough access to the box
that they can grab the stored master password, then they can modify
the postgresql binaries and intercept the salt information (at a
minimum) as it's being sent to the client anyway.

That's because in any sane implementation, you'd store the master
password in a root-readable-only file, and have Postgres start up as
root, grab the password, and then immediately setuid() to the postgres
account, so that accessing the database itself isn't enough to allow
you to compromise the master password.  If they can grab the master
password with that setup, then they have root on the box anyway and
can do anything they want.




-- 
Kevin Brown                          kevin@sysexperts.com

* Antoine Martin (antoine@nagafix.co.uk) wrote:
> Basically, multiple input data that have the same output hash, which is
> of no use when what you are trying to find is the input.
> Finding collisions quicker for a known input is one thing, but that is
> not going to reduce the search space, not even your storage space (it is
> unlikely that the colliding results would all be valid input).

Erm, you aren't necessairly trying to find the input...  It may be the
case that you're trying to find what you need to authenticate to this
server, or any other PostgreSQL server where the same userid & input are
used.  In that case you just need something that hashes to the same
thing.  Using a random salt would mean that it's different per server so
breaking it on one doesn't help you against another server unless you
happened to find the actual original input.

> Is adding the non-guessable salt that hard anyway?

It is if you want to continue to support the 'md5' method in pg_hba.conf
because the wireline protocol will probably need to change.  A less
intrusive alternative would be to add an 'with encrypted password 'xyz'
with random salt' or some such which would only be supported with the
'password' method in pg_hba.conf.

One problem with this is that you then can't just switch from password
to md5 or back again.  Perhaps that's ok though?  Comments?
Stephen

* Kevin Brown (kevin@sysexperts.com) wrote:
> Stephen Frost wrote:
> > Unfortunately, Postgres doesn't currently encrypt pg_shadow and even if
> > it did you'd have to have the password stored on disk somewhere in the
> > clear if you wanted the database to start automatically, which is more
> > important if you havn't got backup databases and whatnot (which aren't
> > really as easy to set up w/ Postgres and generally Postgres requires
> > more disk space than a KDC).
>
> Yeah, but who cares?  If the attacker has enough access to the box
> that they can grab the stored master password, then they can modify
> the postgresql binaries and intercept the salt information (at a
> minimum) as it's being sent to the client anyway.

Security in layers *is* good.  It is not unlikely that an attacker would
be able to gain enough access to read some small portion of protected
data without having full root access to the system.  Your argument would
suggest that we should put plaintext passwords in /etc/shadow and that
there's no reason for a KDC to encrypt its database.

> That's because in any sane implementation, you'd store the master
> password in a root-readable-only file, and have Postgres start up as
> root, grab the password, and then immediately setuid() to the postgres
> account, so that accessing the database itself isn't enough to allow
> you to compromise the master password.  If they can grab the master
> password with that setup, then they have root on the box anyway and
> can do anything they want.

Postgres won't start, atm anyway, if it's being run as root.  You could
have something else do what you're suggesting though, yes.  And, yes,
it'd be better than having the master password be readable from the disk
directly as the Postgres user.  I certainly wouldn't complain if this
was available in Postgres and it would alliviate some of my concerns
about the 'md5' method in pg_hba.conf.
Stephen

On Sat, 2005-04-23 at 09:02 -0400, Stephen Frost wrote:
> * Antoine Martin (antoine@nagafix.co.uk) wrote:
> > Basically, multiple input data that have the same output hash, which is
> > of no use when what you are trying to find is the input.
> > Finding collisions quicker for a known input is one thing, but that is
> > not going to reduce the search space, not even your storage space (it is
> > unlikely that the colliding results would all be valid input).
> 
> Erm, you aren't necessairly trying to find the input...  It may be the
> case that you're trying to find what you need to authenticate to this
> server, or any other PostgreSQL server where the same userid & input are
> used.  In that case you just need something that hashes to the same
> thing.
Agreed, what I said was that it is highly unlikely you will find
colliding inputs that are valid, so the "SHA weakness" does not really
help you here as it does not reduce the search space:
You are much better off pre-calculating hashes for possible usernames &
passwords than working backwards and generating all possible hashes
hoping that one would happen to be matching a real entry...
Usernames are not exactly random, passwords are less predictable, the
chance of a useful collision on the username+password is remote at best.
> Using a random salt would mean that it's different per server so
> breaking it on one doesn't help you against another server unless you
> happened to find the actual original input.
Absolutely.
> 
> > Is adding the non-guessable salt that hard anyway?
> 
> It is if you want to continue to support the 'md5' method in pg_hba.conf
> because the wireline protocol will probably need to change.  A less
> intrusive alternative would be to add an 'with encrypted password 'xyz'
> with random salt' or some such which would only be supported with the
> 'password' method in pg_hba.conf.
> 
> One problem with this is that you then can't just switch from password
> to md5 or back again.  Perhaps that's ok though?  Comments?
Just add another authentication method - call it 'md5-salt' (sharing
most of the 'md5' code), you get backwards compatibility and you advise
users to migrate to the new salt hash. Shouldn't be too hard...
Might as well do a 'sha512-salt' too.

Antoine