Thread: MD5 authentication needs help

It feels like MD5 has accumulated enough problems that we need to start
looking for another way to store and pass passwords.  The MD5 problems
are:

1)  MD5 makes users feel uneasy (though our usage is mostly safe) 

2)  The per-session salt sent to the client is only 32-bits, meaning
that it is possible to reply an observed MD5 hash in ~16k connection
attempts. 

3)  Using the user name for the MD5 storage salt allows the MD5 stored
hash to be used on a different cluster if the user used the same
password. 

4)  Using the user name for the MD5 storage salt causes the renaming of
a user to break the stored password.

For these reasons, it is probably time to start thinking about a
replacement that fixes these issues.  We would keep MD5 but recommend
a better option.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

Bruce, all,

* Bruce Momjian (bruce@momjian.us) wrote:
> It feels like MD5 has accumulated enough problems that we need to start
> looking for another way to store and pass passwords.  The MD5 problems
> are:
>
> 1)  MD5 makes users feel uneasy (though our usage is mostly safe)
>
> 2)  The per-session salt sent to the client is only 32-bits, meaning
> that it is possible to reply an observed MD5 hash in ~16k connection
> attempts.
>
> 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> hash to be used on a different cluster if the user used the same
> password.
>
> 4)  Using the user name for the MD5 storage salt causes the renaming of
> a user to break the stored password.
>
> For these reasons, it is probably time to start thinking about a
> replacement that fixes these issues.  We would keep MD5 but recommend
> a better option.

For more background, I'd suggest taking a look at this recent thread:

CA+TgmoaWdkNBT4mNZ+wf=fgjd7aV9bq7NtsvCha7yeoX0LyQPg@mail.gmail.com
Thanks!
    Stephen

Bruce, all,

I've been discussing this with a few folks outside of the PG community
(Debian and Openwall people specifically) and a few interesting ideas
have come out of that which might be useful to discuss.

The first is a "don't break anything" approach which would move the
needle between "network data sensitivity" and "on-disk data sensitivity"
a bit back in the direction of making the network data more sensitive.

this approach looks like this: pre-determine and store the values (on a
per-user basis, so a new field in pg_authid or some hack on the existing
field) which will be sent to the client in the AuthenticationMD5Password
message.  Further, calculate a random salt to be used when storing data
in pg_authid.  Then, for however many variations we feel are necessary,
calculate and store, for each AuthenticationMD5Password value:

md5_challenge, hash(salt || response)

We wouldn't store 4 billion of these, of course, which means that the
challenge / response system becomes less effective on a per-user basis.
We could, however, store X number of these and provide a lock-out
mechanism (something users have asked after for a long time..) which
would make it likely that the account would be locked before the
attacker was able to gain access.  Further, an attacker with access to
the backend still wouldn't see the user's cleartext password, nor would
we store the cleartext password or a token in pg_authid which could be
directly used for authentication, and we don't break the wireline
protocol or existing installations (since we could detect that the
pg_authid entry has the old-style and simply 'upgrade' it).

That's probably the extent of what we could do to improve the current
'md5' approach without breaking the wireline protocol or existing stored
data.

A lot of discussion has been going on with SCRAM and SASL, which is all
great, but that means we end up with a dependency on SASL or we have to
reimplement SCRAM (which I've been thinking might not be a bad idea-
it's actually not that hard), but another suggestion was made which may
be worthwhile to consider- OpenSSL and GnuTLS both support TLS-SRP, the
RFC for which is here: http://www.ietf.org/rfc/rfc5054.txt.  We already
have OpenSSL and therefore this wouldn't create any new dependencies and
might be slightly simpler to implement.

Thoughts?
Thanks!
    Stephen

Hi,

On 2015-03-04 10:52:30 -0500, Stephen Frost wrote:
> I've been discussing this with a few folks outside of the PG community
> (Debian and Openwall people specifically) and a few interesting ideas
> have come out of that which might be useful to discuss.
> 
> The first is a "don't break anything" approach which would move the
> needle between "network data sensitivity" and "on-disk data sensitivity"
> a bit back in the direction of making the network data more sensitive.

I think that's a really bad tradeoff for pg. There's pretty good reasons
not to encrypt database connections. I don't think you really can
compare routinely encrypted stuff like imap and submission with
pg. Neither is it as harmful to end up with leaked hashes for database
users as it is for a email provider's authentication database.

> A lot of discussion has been going on with SCRAM and SASL, which is all
> great, but that means we end up with a dependency on SASL or we have to
> reimplement SCRAM (which I've been thinking might not be a bad idea-
> it's actually not that hard), but another suggestion was made which may
> be worthwhile to consider- OpenSSL and GnuTLS both support TLS-SRP, the
> RFC for which is here: http://www.ietf.org/rfc/rfc5054.txt.  We already
> have OpenSSL and therefore this wouldn't create any new dependencies and
> might be slightly simpler to implement.

We don't have a hard dependency openssl, so I can't really see that
being a fully viable alternative to md5 TBH.

Greetings,

Andres Freund

-- Andres Freund                       http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training &
Services

Magnus,

* Magnus Hagander (magnus@hagander.net) wrote:
> On Wed, Mar 4, 2015 at 4:52 PM, Stephen Frost <sfrost@snowman.net> wrote:
> > A lot of discussion has been going on with SCRAM and SASL, which is all
> > great, but that means we end up with a dependency on SASL or we have to
> > reimplement SCRAM (which I've been thinking might not be a bad idea-
> > it's actually not that hard), but another suggestion was made which may
>
> I'd really rather not add a dependency on SASL if we can avoid it. I
> haven't read up on SCRAM, but if it's reasonable enough to reimplement - or
> if there is a BSD licensed implementation that we can import into our own
> sourcetree without adding a dependency on SASL, that sounds like a good way
> to proceed.

I actually like the idea of supporting SASL generally, but I agree that
we don't really want to force it as a dependency.  I've started looking
around for BSD-licensed SCRAM implementations and will update with any I
find that are worthwhile to review.

> > be worthwhile to consider- OpenSSL and GnuTLS both support TLS-SRP, the
> > RFC for which is here: http://www.ietf.org/rfc/rfc5054.txt.  We already
> > have OpenSSL and therefore this wouldn't create any new dependencies and
> > might be slightly simpler to implement.
>
> OpenSSL is not a *requirement* today, it's an optional dependency.  Given
> it's license we really can't make it a mandatory requirement I think. So if
> we go down that route, we still leave md5 in there as the one that works
> everywhere.
>
> Also AFAICT TLS-SRP actually requires the connection to be over TLS - so
> are you suggesting that TLS becomes mandatory?
>
> It sounds like something that could be interesting to have, but not as a
> solution to the "md5 problem", imo.

No, I'm not suggesting that OpenSSL or TLS become mandatory but was
thinking it might be good alternative as a middle-ground between full
client-and-server side certificates and straight password-based auth
(which is clearly why it was invented in the first place) and so, yes,
md5 would still have to be kept around, but we'd at least be able to
deprecate it and tell people "Use TLS-SRP if you really want to use
passwords and care about network security".

SCRAM doesn't actually fix the issue with network connection hijacking
or eavesdropping, except to the extent that it protects the password
itself, and so we might want to recommend, for people who are worried
about network-based attacks, using TLS-SRP.
Thanks!
    Stephen

* Andres Freund (andres@2ndquadrant.com) wrote:
> Hi,
>
> On 2015-03-04 10:52:30 -0500, Stephen Frost wrote:
> > I've been discussing this with a few folks outside of the PG community
> > (Debian and Openwall people specifically) and a few interesting ideas
> > have come out of that which might be useful to discuss.
> >
> > The first is a "don't break anything" approach which would move the
> > needle between "network data sensitivity" and "on-disk data sensitivity"
> > a bit back in the direction of making the network data more sensitive.
>
> I think that's a really bad tradeoff for pg. There's pretty good reasons
> not to encrypt database connections. I don't think you really can
> compare routinely encrypted stuff like imap and submission with
> pg. Neither is it as harmful to end up with leaked hashes for database
> users as it is for a email provider's authentication database.

I'm confused..  The paragraph you reply to here discusses an approach
which doesn't include encrypting the database connection.

> > A lot of discussion has been going on with SCRAM and SASL, which is all
> > great, but that means we end up with a dependency on SASL or we have to
> > reimplement SCRAM (which I've been thinking might not be a bad idea-
> > it's actually not that hard), but another suggestion was made which may
> > be worthwhile to consider- OpenSSL and GnuTLS both support TLS-SRP, the
> > RFC for which is here: http://www.ietf.org/rfc/rfc5054.txt.  We already
> > have OpenSSL and therefore this wouldn't create any new dependencies and
> > might be slightly simpler to implement.
>
> We don't have a hard dependency openssl, so I can't really see that
> being a fully viable alternative to md5 TBH.

Right, agreed, that wasn't intended to be a complete replacement for md5
but rather an additional auth mechanism we could get nearly "for free"
which would provide password-based authentication with network-level
encryption for users who are worried about network-based attacks (and
therefore want to or are already using TLS, as Debian is configured to
do by default...).
Thanks!
    Stephen

On 2015-03-04 11:06:33 -0500, Stephen Frost wrote:
> * Andres Freund (andres@2ndquadrant.com) wrote:
> > On 2015-03-04 10:52:30 -0500, Stephen Frost wrote:
> > > The first is a "don't break anything" approach which would move the
> > > needle between "network data sensitivity" and "on-disk data sensitivity"
> > > a bit back in the direction of making the network data more sensitive.
> > 
> > I think that's a really bad tradeoff for pg. There's pretty good reasons
> > not to encrypt database connections. I don't think you really can
> > compare routinely encrypted stuff like imap and submission with
> > pg. Neither is it as harmful to end up with leaked hashes for database
> > users as it is for a email provider's authentication database.
> 
> I'm confused..  The paragraph you reply to here discusses an approach
> which doesn't include encrypting the database connection.

An increase in "network data sensitivity" also increases the need for
encryption.

Greetings,

Andres Freund

-- Andres Freund                       http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training &
Services

* Magnus Hagander (magnus@hagander.net) wrote:
> On Wed, Mar 4, 2015 at 5:03 PM, Stephen Frost <sfrost@snowman.net> wrote:
> > No, I'm not suggesting that OpenSSL or TLS become mandatory but was
> > thinking it might be good alternative as a middle-ground between full
> > client-and-server side certificates and straight password-based auth
> > (which is clearly why it was invented in the first place) and so, yes,
> > md5 would still have to be kept around, but we'd at least be able to
> > deprecate it and tell people "Use TLS-SRP if you really want to use
> > passwords and care about network security".
> >
> > SCRAM doesn't actually fix the issue with network connection hijacking
> > or eavesdropping, except to the extent that it protects the password
> > itself, and so we might want to recommend, for people who are worried
> > about network-based attacks, using TLS-SRP.
>
> Assuming we do implement SCRAM, what does TLS-SRP give us that we wouldn't
> get by just using SCRAM over a TLS connection?

Good question and I'll have to dig more into that.  SCRAM does appear to
support channel binding with TLS and therefore there might not be much
to be gained from having both.
Thanks!
    Stephen

* Andres Freund (andres@2ndquadrant.com) wrote:
> On 2015-03-04 11:06:33 -0500, Stephen Frost wrote:
> > * Andres Freund (andres@2ndquadrant.com) wrote:
> > > On 2015-03-04 10:52:30 -0500, Stephen Frost wrote:
> > > > The first is a "don't break anything" approach which would move the
> > > > needle between "network data sensitivity" and "on-disk data sensitivity"
> > > > a bit back in the direction of making the network data more sensitive.
> > >
> > > I think that's a really bad tradeoff for pg. There's pretty good reasons
> > > not to encrypt database connections. I don't think you really can
> > > compare routinely encrypted stuff like imap and submission with
> > > pg. Neither is it as harmful to end up with leaked hashes for database
> > > users as it is for a email provider's authentication database.
> >
> > I'm confused..  The paragraph you reply to here discusses an approach
> > which doesn't include encrypting the database connection.
>
> An increase in "network data sensitivity" also increases the need for
> encryption.

Ok, I see what you're getting at there, though our existing md5
implementation with no lock-out mechanism or ability to deal with
hijacking isn't exactly making us all that safe when it comes to network
based attacks.  The best part about md5 is that we don't send the user's
password over the wire in the clear, the actual challenge/response piece
is not considered terribly secure today, nor is the salt+password we use
for pg_authid for that matter. :/

SCRAM won't fix network connection hijacking but it does address replay
attacks better than our current challenge/response system (at least the
example in the RFC uses a 16-byte base64-encoded salt)) and the on-disk
storage risk (multiple iterations are supported), and multiple hashing
algorithms can be supported including ones much better than what we
support today (eg: SHA256) which applies to both network and on-disk
vectors.
Thanks,
    Stephen

On Wed, Mar  4, 2015 at 10:52:30AM -0500, Stephen Frost wrote:
> The first is a "don't break anything" approach which would move the
> needle between "network data sensitivity" and "on-disk data sensitivity"
> a bit back in the direction of making the network data more sensitive.
> 
> this approach looks like this: pre-determine and store the values (on a
> per-user basis, so a new field in pg_authid or some hack on the existing
> field) which will be sent to the client in the AuthenticationMD5Password
> message.  Further, calculate a random salt to be used when storing data
> in pg_authid.  Then, for however many variations we feel are necessary,
> calculate and store, for each AuthenticationMD5Password value:
> 
> md5_challenge, hash(salt || response)
> 
> We wouldn't store 4 billion of these, of course, which means that the
> challenge / response system becomes less effective on a per-user basis.
> We could, however, store X number of these and provide a lock-out
> mechanism (something users have asked after for a long time..) which
> would make it likely that the account would be locked before the
> attacker was able to gain access.  Further, an attacker with access to
> the backend still wouldn't see the user's cleartext password, nor would
> we store the cleartext password or a token in pg_authid which could be
> directly used for authentication, and we don't break the wireline
> protocol or existing installations (since we could detect that the
> pg_authid entry has the old-style and simply 'upgrade' it).

What does storing multiple hash(password || stoarage_salt) values do for
us that session_salt doesn't already do?

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

On Wed, Mar  4, 2015 at 11:36:23AM -0500, Stephen Frost wrote:
> * Andres Freund (andres@2ndquadrant.com) wrote:
> > On 2015-03-04 11:06:33 -0500, Stephen Frost wrote:
> > > * Andres Freund (andres@2ndquadrant.com) wrote:
> > > > On 2015-03-04 10:52:30 -0500, Stephen Frost wrote:
> > > > > The first is a "don't break anything" approach which would move the
> > > > > needle between "network data sensitivity" and "on-disk data sensitivity"
> > > > > a bit back in the direction of making the network data more sensitive.
> > > > 
> > > > I think that's a really bad tradeoff for pg. There's pretty good reasons
> > > > not to encrypt database connections. I don't think you really can
> > > > compare routinely encrypted stuff like imap and submission with
> > > > pg. Neither is it as harmful to end up with leaked hashes for database
> > > > users as it is for a email provider's authentication database.
> > > 
> > > I'm confused..  The paragraph you reply to here discusses an approach
> > > which doesn't include encrypting the database connection.
> > 
> > An increase in "network data sensitivity" also increases the need for
> > encryption.
> 
> Ok, I see what you're getting at there, though our existing md5
> implementation with no lock-out mechanism or ability to deal with
> hijacking isn't exactly making us all that safe when it comes to network
> based attacks.  The best part about md5 is that we don't send the user's
> password over the wire in the clear, the actual challenge/response piece                                    -----
hereis where I was lost
 
> is not considered terribly secure today, nor is the salt+password we use
> for pg_authid for that matter. :/

Can you please rephrase the last sentence as it doesn't make sense to
me?

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Bruce Momjian (bruce@momjian.us) wrote:
> On Wed, Mar  4, 2015 at 10:52:30AM -0500, Stephen Frost wrote:
> > The first is a "don't break anything" approach which would move the
> > needle between "network data sensitivity" and "on-disk data sensitivity"
> > a bit back in the direction of making the network data more sensitive.
> >
> > this approach looks like this: pre-determine and store the values (on a
> > per-user basis, so a new field in pg_authid or some hack on the existing
> > field) which will be sent to the client in the AuthenticationMD5Password
> > message.  Further, calculate a random salt to be used when storing data
> > in pg_authid.  Then, for however many variations we feel are necessary,
> > calculate and store, for each AuthenticationMD5Password value:
> >
> > md5_challenge, hash(salt || response)
> >
> > We wouldn't store 4 billion of these, of course, which means that the
> > challenge / response system becomes less effective on a per-user basis.
> > We could, however, store X number of these and provide a lock-out
> > mechanism (something users have asked after for a long time..) which
> > would make it likely that the account would be locked before the
> > attacker was able to gain access.  Further, an attacker with access to
> > the backend still wouldn't see the user's cleartext password, nor would
> > we store the cleartext password or a token in pg_authid which could be
> > directly used for authentication, and we don't break the wireline
> > protocol or existing installations (since we could detect that the
> > pg_authid entry has the old-style and simply 'upgrade' it).
>
> What does storing multiple hash(password || stoarage_salt) values do for
> us that session_salt doesn't already do?

By storing a hash of the result of the challenge/response, we wouldn't
be susceptible to attacks where the user has gained access to the
contents of pg_authid because the values there would not be (directly)
useful for authentication.  Today, an attacker can take what's in
pg_authid and directly use it to authenticate (which is what the
interwebs are complaining about).

We wouldn't want to do that for just a single value though because then
there wouldn't be any value to the challenge/response system (which is
intended to prevent replay attacks where the attacker has sniffed a
value from the network and then uses that value to authenticate
themselves).

The only way we can keep the session salt random without breaking the
wireline protocol is to keep the raw data necessary for authentication
in pg_authid (as we do now) since we'd need that information to recreate
the results of the random session salt+user-hash for comparison.

This is essentially a middle ground which maintains the existing
wireline protocol while changing what is in pg_authid to be something
that an attacker can't trivially use to authenticate.  It is not a
proper solution as that requires changing the wireline protocol (or,
really, extending it with another auth method that's better).
Thanks,
    Stephen

* Bruce Momjian (bruce@momjian.us) wrote:
> On Wed, Mar  4, 2015 at 11:36:23AM -0500, Stephen Frost wrote:
> > * Andres Freund (andres@2ndquadrant.com) wrote:
> > > On 2015-03-04 11:06:33 -0500, Stephen Frost wrote:
> > > > * Andres Freund (andres@2ndquadrant.com) wrote:
> > > > > On 2015-03-04 10:52:30 -0500, Stephen Frost wrote:
> > > > > > The first is a "don't break anything" approach which would move the
> > > > > > needle between "network data sensitivity" and "on-disk data sensitivity"
> > > > > > a bit back in the direction of making the network data more sensitive.
> > > > >
> > > > > I think that's a really bad tradeoff for pg. There's pretty good reasons
> > > > > not to encrypt database connections. I don't think you really can
> > > > > compare routinely encrypted stuff like imap and submission with
> > > > > pg. Neither is it as harmful to end up with leaked hashes for database
> > > > > users as it is for a email provider's authentication database.
> > > >
> > > > I'm confused..  The paragraph you reply to here discusses an approach
> > > > which doesn't include encrypting the database connection.
> > >
> > > An increase in "network data sensitivity" also increases the need for
> > > encryption.
> >
> > Ok, I see what you're getting at there, though our existing md5
> > implementation with no lock-out mechanism or ability to deal with
> > hijacking isn't exactly making us all that safe when it comes to network
> > based attacks.  The best part about md5 is that we don't send the user's
> > password over the wire in the clear, the actual challenge/response piece
>                                      ----- here is where I was lost
> > is not considered terribly secure today, nor is the salt+password we use
> > for pg_authid for that matter. :/
>
> Can you please rephrase the last sentence as it doesn't make sense to
> me?

The best part of the existing authentication method we call "md5" is
that the user's password is never sent over the network in the clear.

The challenge/response implementation we have only provides for 4 bytes
of hash (or around four billion possible permutations) which is not very
secure today (as compared to the 16-character base64 salt used in SCRAM,
which is 16^64 or 2^96 instead of 2^32).
Thanks,
    Stephen

* Stephen Frost (sfrost@snowman.net) wrote:
> * Bruce Momjian (bruce@momjian.us) wrote:
> > On Wed, Mar  4, 2015 at 11:36:23AM -0500, Stephen Frost wrote:
> > > * Andres Freund (andres@2ndquadrant.com) wrote:
> > > > On 2015-03-04 11:06:33 -0500, Stephen Frost wrote:
> > > > > * Andres Freund (andres@2ndquadrant.com) wrote:
> > > > > > On 2015-03-04 10:52:30 -0500, Stephen Frost wrote:
> > > > > > > The first is a "don't break anything" approach which would move the
> > > > > > > needle between "network data sensitivity" and "on-disk data sensitivity"
> > > > > > > a bit back in the direction of making the network data more sensitive.
> > > > > >
> > > > > > I think that's a really bad tradeoff for pg. There's pretty good reasons
> > > > > > not to encrypt database connections. I don't think you really can
> > > > > > compare routinely encrypted stuff like imap and submission with
> > > > > > pg. Neither is it as harmful to end up with leaked hashes for database
> > > > > > users as it is for a email provider's authentication database.
> > > > >
> > > > > I'm confused..  The paragraph you reply to here discusses an approach
> > > > > which doesn't include encrypting the database connection.
> > > >
> > > > An increase in "network data sensitivity" also increases the need for
> > > > encryption.
> > >
> > > Ok, I see what you're getting at there, though our existing md5
> > > implementation with no lock-out mechanism or ability to deal with
> > > hijacking isn't exactly making us all that safe when it comes to network
> > > based attacks.  The best part about md5 is that we don't send the user's
> > > password over the wire in the clear, the actual challenge/response piece
> >                                      ----- here is where I was lost
> > > is not considered terribly secure today, nor is the salt+password we use
> > > for pg_authid for that matter. :/
> >
> > Can you please rephrase the last sentence as it doesn't make sense to
> > me?
>
> The best part of the existing authentication method we call "md5" is
> that the user's password is never sent over the network in the clear.
>
> The challenge/response implementation we have only provides for 4 bytes
> of hash (or around four billion possible permutations) which is not very
> secure today (as compared to the 16-character base64 salt used in SCRAM,
> which is 16^64 or 2^96 instead of 2^32).

Err, 64^16 or 2^96, that is.  16^64 is not the same and would be way
larger. :)
Thanks!
    Stephen

On Wed, Mar  4, 2015 at 12:43:54PM -0500, Stephen Frost wrote:
> > What does storing multiple hash(password || stoarage_salt) values do for
> > us that session_salt doesn't already do?
> 
> By storing a hash of the result of the challenge/response, we wouldn't
> be susceptible to attacks where the user has gained access to the
> contents of pg_authid because the values there would not be (directly)
> useful for authentication.  Today, an attacker can take what's in
> pg_authid and directly use it to authenticate (which is what the
> interwebs are complaining about).
> 
> We wouldn't want to do that for just a single value though because then
> there wouldn't be any value to the challenge/response system (which is
> intended to prevent replay attacks where the attacker has sniffed a
> value from the network and then uses that value to authenticate
> themselves).

So you are storing the password + storage-salt + session-saltX, where X
is greater than the maximum number of login attempts?  How do you know
the attacker will not be given a salt that was already seen before?

> The only way we can keep the session salt random without breaking the
> wireline protocol is to keep the raw data necessary for authentication
> in pg_authid (as we do now) since we'd need that information to recreate
> the results of the random session salt+user-hash for comparison.
> 
> This is essentially a middle ground which maintains the existing
> wireline protocol while changing what is in pg_authid to be something
> that an attacker can't trivially use to authenticate.  It is not a

I don't understand how this works.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Bruce Momjian (bruce@momjian.us) wrote:
> On Wed, Mar  4, 2015 at 12:43:54PM -0500, Stephen Frost wrote:
> > > What does storing multiple hash(password || stoarage_salt) values do for
> > > us that session_salt doesn't already do?
> >
> > By storing a hash of the result of the challenge/response, we wouldn't
> > be susceptible to attacks where the user has gained access to the
> > contents of pg_authid because the values there would not be (directly)
> > useful for authentication.  Today, an attacker can take what's in
> > pg_authid and directly use it to authenticate (which is what the
> > interwebs are complaining about).
> >
> > We wouldn't want to do that for just a single value though because then
> > there wouldn't be any value to the challenge/response system (which is
> > intended to prevent replay attacks where the attacker has sniffed a
> > value from the network and then uses that value to authenticate
> > themselves).
>
> So you are storing the password + storage-salt + session-saltX, where X
> is greater than the maximum number of login attempts?  How do you know
> the attacker will not be given a salt that was already seen before?

The password isn't stored and I don't know what you're talking about
regarding the number of login attempts.  Further, we don't know today if
an attacker has seen a particular challege/response sequence or not (nor
can we...) and we can certainly repeat it.

> > The only way we can keep the session salt random without breaking the
> > wireline protocol is to keep the raw data necessary for authentication
> > in pg_authid (as we do now) since we'd need that information to recreate
> > the results of the random session salt+user-hash for comparison.
> >
> > This is essentially a middle ground which maintains the existing
> > wireline protocol while changing what is in pg_authid to be something
> > that an attacker can't trivially use to authenticate.  It is not a
>
> I don't understand how this works.

Ok, let me try to explain it another way.

The current system looks like this:

client has username and password
server has hash(username + password)

client:
 send auth request w/ username and database

server:
 send random salt to client

client:
 send hash(hash(username + password) + salt) to server

server:
 calculate hash(hash(username + password) + salt) compare to what client sent

What the interwebs are complaining about is that the
"hash(username + password)" piece that's stored in pg_authid is
sufficient to authenticate.

Here's what was proposed as an alternative which would prevent that
without breaking the existing wireline protocol:

client has username and password
server has user_salt,      N *     {salt, hash(hash(hash(username + password) + salt), user_salt)}

client:
 send auth request w/ username and database

server:
 picks random salt from the salts available for this user sends salt to the user

client:
 send hash(hash(username + password) + salt) to server

server:
 server calculates, using the data from the client,   hash(FROM_CLIENT + user_salt) compares to hash stored for salt
chosen

This makes what is stored in pg_authid no longer directly useful for
authentication (similar to how Unix passwd-based authentication works)
because if the client sent any of those values, we'd add the user_salt
and hash it again and it wouldn't match what's stored.

This further makes what is sent over the network not directly
susceptible to a replay attack because the server has multiple values
available to pick for the salt to use and sends one at random to the
client, exactly how our current challenge/response replay-prevention
system works.  The downside is that the number of possible values for
the server to send to prevent replay attacke is reduced from 2^32 to N.

To mitigate the replay risk we would, ideally, support a lock-out
mechanism.  This won't help if the attacker has extended network access
though as we would almost certainly eventually go through all N
permutations for this user.

However, use of TLS would prevent the network-based attack vector.

Using TLS + the 'password' authentication mechanism would also achieve
the goal of making what is in pg_authid not directly useful for
authentication, but that would mean that the postmaster would see the
user's password (post-decryption), leading to a risk that the password
could be reused for access to other systems by a rogue server
administrator.  Now, that's what SSH and *most* systems have had for
ages when it comes to password-based authentication and therefore it's
well understood in the industry and session-level encryption is
generally considered to avoid the network-based vector associated with
that approach.

For PG users, however, we encourage using md5 instead of password as we
consider that "better", but users familiar with SSH and other
unix-password based authentication mechanisms might, understandably,
think that MD5+TLS prevents both attack vectors, but it doesn't.
Password+TLS is what they would actually want to get the traditional
unix-password-style trade-offs.

Of course, the hashing algorithm used for all of the current
authentication systems we support is no longer generally considered
secure and that we use a non-random salt for storage (the username)
makes it worse.
Thanks!
    Stephen

On 03/04/2015 04:52 PM, Stephen Frost wrote:
> Bruce, all,
> 
> I've been discussing this with a few folks outside of the PG community
> (Debian and Openwall people specifically) and a few interesting ideas
> have come out of that which might be useful to discuss.
> 
> The first is a "don't break anything" approach which would move the
> needle between "network data sensitivity" and "on-disk data sensitivity"
> a bit back in the direction of making the network data more sensitive.
> 
> this approach looks like this: pre-determine and store the values (on a
> per-user basis, so a new field in pg_authid or some hack on the existing
> field) which will be sent to the client in the AuthenticationMD5Password
> message.  Further, calculate a random salt to be used when storing data
> in pg_authid.  Then, for however many variations we feel are necessary,
> calculate and store, for each AuthenticationMD5Password value:
> 
> md5_challenge, hash(salt || response)
> 
> We wouldn't store 4 billion of these, of course, which means that the
> challenge / response system becomes less effective on a per-user basis.
> We could, however, store X number of these and provide a lock-out
> mechanism (something users have asked after for a long time..) which
> would make it likely that the account would be locked before the
> attacker was able to gain access.  Further, an attacker with access to
> the backend still wouldn't see the user's cleartext password, nor would
> we store the cleartext password or a token in pg_authid which could be
> directly used for authentication, and we don't break the wireline
> protocol or existing installations (since we could detect that the
> pg_authid entry has the old-style and simply 'upgrade' it).
> 
> That's probably the extent of what we could do to improve the current
> 'md5' approach without breaking the wireline protocol or existing stored
> data.
> 
> A lot of discussion has been going on with SCRAM and SASL, which is all
> great, but that means we end up with a dependency on SASL or we have to
> reimplement SCRAM (which I've been thinking might not be a bad idea-
> it's actually not that hard), but another suggestion was made which may
> be worthwhile to consider- OpenSSL and GnuTLS both support TLS-SRP, the
> RFC for which is here: http://www.ietf.org/rfc/rfc5054.txt.  We already
> have OpenSSL and therefore this wouldn't create any new dependencies and
> might be slightly simpler to implement.

not sure we should depend on TLS-SRP - the libressl people removed the
support for SRP pretty early in the development process:
https://github.com/libressl/libressl/commit/f089354ca79035afce9ec649f54c18711a950ecd



Stefan

On 03/04/2015 06:11 PM, Stephen Frost wrote:
> * Magnus Hagander (magnus@hagander.net) wrote:
>> On Wed, Mar 4, 2015 at 5:03 PM, Stephen Frost <sfrost@snowman.net> wrote:
>>> No, I'm not suggesting that OpenSSL or TLS become mandatory but was
>>> thinking it might be good alternative as a middle-ground between full
>>> client-and-server side certificates and straight password-based auth
>>> (which is clearly why it was invented in the first place) and so, yes,
>>> md5 would still have to be kept around, but we'd at least be able to
>>> deprecate it and tell people "Use TLS-SRP if you really want to useou
>>> passwords and care about network security".
>>>
>>> SCRAM doesn't actually fix the issue with network connection hijacking
>>> or eavesdropping, except to the extent that it protects the password
>>> itself, and so we might want to recommend, for people who are worried
>>> about network-based attacks, using TLS-SRP.
>>
>> Assuming we do implement SCRAM, what does TLS-SRP give us that we wouldn't
>> get by just using SCRAM over a TLS connection?
>
> Good question and I'll have to dig more into that.  SCRAM does appear to
> support channel binding with TLS and therefore there might not be much
> to be gained from having both.

The big difference between SRP and SCRAM is that if you eavesdrop the 
SCRAM handshake, you can use that information to launch a brute-force or 
dictionary attack. With SRP, you cannot do that. That makes it 
relatively safe to use weak passwords with SRP, which is not the case 
with SCRAM (nor MD5)

Let me list the possible attacks that we're trying to protect against:

A) Eve eavesdrops on the authentication exchange. Can she use the 
information gathered directly to authenticate to the server?

B) Can Eve use the information to launch a dictionary or brute force the 
password?

C) Can a malicious server impersonate the real server? (i.e. does the 
protocol not authenticate the server to the client)

D) If Eve obtains a copy pg_authid (e.g from a backup tape), can she use 
that information to authenticate directly? (Brute forcing the passwords 
is always possible in this case)
    A)    B)    C)    D)
password    Yes    Yes    Yes    No [1]
MD5        No    Yes    Yes    Yes
SCRAM        No    Yes    No    No
SRP        No    No    No    No

[1] assuming that pg_authid stored MD5 hashes, not plaintext passwords, 
which should be the case these days.

Note that this table does not consider how difficult a brute-force 
attack is in each case; MD5 is a lot cheaper to calculate than SCRAM or 
SRP hashes. And there are more things to consider like implementation 
effort, strength of the underlying hash and other algorithms etc.

Also, attacks A), B) and C) can be thwarted by using SSL, with the 
client configured to check the server certificate (sslmode=verify-full). 
So actually, password authentication with SSL is not a bad option at 
all; it's actually better than MD5 because it doesn't allow attack D).

- Heikki

* Heikki Linnakangas (hlinnaka@iki.fi) wrote:
> The big difference between SRP and SCRAM is that if you eavesdrop
> the SCRAM handshake, you can use that information to launch a
> brute-force or dictionary attack. With SRP, you cannot do that. That
> makes it relatively safe to use weak passwords with SRP, which is
> not the case with SCRAM (nor MD5)

Thanks for the info!

Looking around a bit, one issue with SRP (as pointed out by Simon
Josefsson, the author of the SCRAM implementation for GNU SASL) is that
the username is included in the verifier (similar to our implementation
today with MD5) meaning that the stored data on the server is no longer
valid if the username is changed.  Obviously, our users are used to
that, but it's still something to be considered.

One question though- isn't the iteration option to SCRAM intended to
address the dictionary/brute force risk?  SRP uses an exponentiation
instead of iterations but it's unclear to me if one is really strictly
better or worse than the other (nor have I found any discussion of that
comparison) for this vector.
Thanks!
    Stephen

On 03/04/2015 08:59 PM, Stephen Frost wrote:
> * Heikki Linnakangas (hlinnaka@iki.fi) wrote:
>> The big difference between SRP and SCRAM is that if you eavesdrop
>> the SCRAM handshake, you can use that information to launch a
>> brute-force or dictionary attack. With SRP, you cannot do that. That
>> makes it relatively safe to use weak passwords with SRP, which is
>> not the case with SCRAM (nor MD5)
>
> Thanks for the info!
>
> Looking around a bit, one issue with SRP (as pointed out by Simon
> Josefsson, the author of the SCRAM implementation for GNU SASL) is that
> the username is included in the verifier (similar to our implementation
> today with MD5) meaning that the stored data on the server is no longer
> valid if the username is changed.  Obviously, our users are used to
> that, but it's still something to be considered.

Yes, good point, that's yet another thing that needs to be considered.

> One question though- isn't the iteration option to SCRAM intended to
> address the dictionary/brute force risk?  SRP uses an exponentiation
> instead of iterations but it's unclear to me if one is really strictly
> better or worse than the other (nor have I found any discussion of that
> comparison) for this vector.

Not sure what you mean. Yes, the iterations option in SCRAM is designed 
to make brute forcing more expensive. For both a captured authentication 
handshake, or if you steal a backup tape.

I'm not sure how expensive a brute force attack on SRP would be, using a 
stolen backup tape. There doesn't seem to be an iterations count similar 
to SCRAM. But note that SRP's resistance to brute-forcing the 
authentication handshake is of a different kind. It's not just 
expensive, but outright impossible. (Don't ask me how that works; I'm 
not well-versed in the maths involved.) That's a big advantage because 
it means that it's OK to use a fairly weak password like 'foobar123' 
that would be trivially cracked with a dictionary attack. (You can still 
connect to the server and try different passwords, but the server can 
log that and throttle how many guesses / minute it let's you do)

- Heikki

On Wed, Mar  4, 2015 at 01:27:32PM -0500, Stephen Frost wrote:
> This further makes what is sent over the network not directly
> susceptible to a replay attack because the server has multiple values
> available to pick for the salt to use and sends one at random to the
> client, exactly how our current challenge/response replay-prevention
> system works.  The downside is that the number of possible values for
> the server to send to prevent replay attacke is reduced from 2^32 to N.

OK, I understand now --- by not using a random session salt, you can
store a post-hash of what you receive from the client, preventing the
pg_authid from being resent by a client.  Nice trick, though going from
2^32 to N randomness doesn't seem like a win.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Heikki Linnakangas (hlinnaka@iki.fi) wrote:
> I'm not sure how expensive a brute force attack on SRP would be,
> using a stolen backup tape. There doesn't seem to be an iterations
> count similar to SCRAM. But note that SRP's resistance to
> brute-forcing the authentication handshake is of a different kind.
> It's not just expensive, but outright impossible. (Don't ask me how
> that works; I'm not well-versed in the maths involved.) That's a big
> advantage because it means that it's OK to use a fairly weak
> password like 'foobar123' that would be trivially cracked with a
> dictionary attack.

If it's actually impossible then that's certainly interesting..  I don't
get how that's possible, but ok.

> (You can still connect to the server and try
> different passwords, but the server can log that and throttle how
> many guesses / minute it let's you do)

Wouldn't that be nice...  Wish we did it. :(
Thanks,
    Stephen

* Bruce Momjian (bruce@momjian.us) wrote:
> On Wed, Mar  4, 2015 at 01:27:32PM -0500, Stephen Frost wrote:
> > This further makes what is sent over the network not directly
> > susceptible to a replay attack because the server has multiple values
> > available to pick for the salt to use and sends one at random to the
> > client, exactly how our current challenge/response replay-prevention
> > system works.  The downside is that the number of possible values for
> > the server to send to prevent replay attacke is reduced from 2^32 to N.
>
> OK, I understand now --- by not using a random session salt, you can
> store a post-hash of what you receive from the client, preventing the
> pg_authid from being resent by a client.  Nice trick, though going from
> 2^32 to N randomness doesn't seem like a win.

You're only looking at it from the network attack vector angle where
clearly that's a reduction in strength.  That is not the only angle and
in many environments the network attack vector is already addressed with
TLS.

From the perspective of what everyone is currently complaining about on
the web, which is the pg_authid compromise vector, it'd be a huge
improvement over the current situation and we wouldn't be breaking any
existing clients, nor does it require having the postmaster see the
user's cleartext password during authentication (which is a common
argument against recommending the 'password' authentication method).
Thanks,
    Stephen

On Wed, Mar  4, 2015 at 02:21:51PM -0500, Stephen Frost wrote:
> * Bruce Momjian (bruce@momjian.us) wrote:
> > On Wed, Mar  4, 2015 at 01:27:32PM -0500, Stephen Frost wrote:
> > > This further makes what is sent over the network not directly
> > > susceptible to a replay attack because the server has multiple values
> > > available to pick for the salt to use and sends one at random to the
> > > client, exactly how our current challenge/response replay-prevention
> > > system works.  The downside is that the number of possible values for
> > > the server to send to prevent replay attacke is reduced from 2^32 to N.
> > 
> > OK, I understand now --- by not using a random session salt, you can
> > store a post-hash of what you receive from the client, preventing the
> > pg_authid from being resent by a client.  Nice trick, though going from
> > 2^32 to N randomness doesn't seem like a win.
> 
> You're only looking at it from the network attack vector angle where
> clearly that's a reduction in strength.  That is not the only angle and
> in many environments the network attack vector is already addressed with
> TLS.

Well, passwords are already addressed by certificate authentication, so
what's your point?  I think we decided we wanted a way to do passwords
without requiring network encryption.

> From the perspective of what everyone is currently complaining about on
> the web, which is the pg_authid compromise vector, it'd be a huge
> improvement over the current situation and we wouldn't be breaking any
> existing clients, nor does it require having the postmaster see the
> user's cleartext password during authentication (which is a common
> argument against recommending the 'password' authentication method).

We are not designing only for what people are complaining about today.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Bruce Momjian (bruce@momjian.us) wrote:
> On Wed, Mar  4, 2015 at 02:21:51PM -0500, Stephen Frost wrote:
> > * Bruce Momjian (bruce@momjian.us) wrote:
> > > On Wed, Mar  4, 2015 at 01:27:32PM -0500, Stephen Frost wrote:
> > > > This further makes what is sent over the network not directly
> > > > susceptible to a replay attack because the server has multiple values
> > > > available to pick for the salt to use and sends one at random to the
> > > > client, exactly how our current challenge/response replay-prevention
> > > > system works.  The downside is that the number of possible values for
> > > > the server to send to prevent replay attacke is reduced from 2^32 to N.
> > >
> > > OK, I understand now --- by not using a random session salt, you can
> > > store a post-hash of what you receive from the client, preventing the
> > > pg_authid from being resent by a client.  Nice trick, though going from
> > > 2^32 to N randomness doesn't seem like a win.
> >
> > You're only looking at it from the network attack vector angle where
> > clearly that's a reduction in strength.  That is not the only angle and
> > in many environments the network attack vector is already addressed with
> > TLS.
>
> Well, passwords are already addressed by certificate authentication, so
> what's your point?  I think we decided we wanted a way to do passwords
> without requiring network encryption.

It's completely unclear to me what you mean by "passwords are already
addressed by certificate authentication."  Password-based and
certificate-based authentication are two independent mechanisms
available today, and both can be used with TLS.  Certainly the more
common implementation that I've come across is password-based
authentication through the md5 mechanism with TLS.  There are few places
which actually use client-side certificate-based authentication but tons
which use TLS.

> > From the perspective of what everyone is currently complaining about on
> > the web, which is the pg_authid compromise vector, it'd be a huge
> > improvement over the current situation and we wouldn't be breaking any
> > existing clients, nor does it require having the postmaster see the
> > user's cleartext password during authentication (which is a common
> > argument against recommending the 'password' authentication method).
>
> We are not designing only for what people are complaining about today.

I was simply trying to explain what the 'newly discovered' vector
being discussed today is.  I complained about our implementation here 10
years ago and it has come up before this recent wave of complaints since
then, though perhaps with a bit less publicity, but I suspect that's
just because PG is getting popular.

And, no, I'm not suggesting that we design differently because we're now
popular, but I do think we need to address this issue because it's very
clearly an obvious deficiency.  I trust you feel the same as you started
this thread.

I brought up this approach because it avoids breaking the wireline
protocol or forcing everyone to switch to a new authentication method.
Thanks,
    Stephen

On Wed, Mar  4, 2015 at 02:46:54PM -0500, Stephen Frost wrote:
> > Well, passwords are already addressed by certificate authentication, so
> > what's your point?  I think we decided we wanted a way to do passwords
> > without requiring network encryption.
> 
> It's completely unclear to me what you mean by "passwords are already
> addressed by certificate authentication."  Password-based and
> certificate-based authentication are two independent mechanisms
> available today, and both can be used with TLS.  Certainly the more
> common implementation that I've come across is password-based
> authentication through the md5 mechanism with TLS.  There are few places
> which actually use client-side certificate-based authentication but tons
> which use TLS.

My point is we can't design a new authentication method to replace MD5
if it doesn't work well without TLS.

> > > From the perspective of what everyone is currently complaining about on
> > > the web, which is the pg_authid compromise vector, it'd be a huge
> > > improvement over the current situation and we wouldn't be breaking any
> > > existing clients, nor does it require having the postmaster see the
> > > user's cleartext password during authentication (which is a common
> > > argument against recommending the 'password' authentication method).
> > 
> > We are not designing only for what people are complaining about today.
> 
> I was simply trying to explain what the 'newly discovered' vector
> being discussed today is.  I complained about our implementation here 10
> years ago and it has come up before this recent wave of complaints since
> then, though perhaps with a bit less publicity, but I suspect that's
> just because PG is getting popular.
> 
> And, no, I'm not suggesting that we design differently because we're now
> popular, but I do think we need to address this issue because it's very
> clearly an obvious deficiency.  I trust you feel the same as you started
> this thread.
> 
> I brought up this approach because it avoids breaking the wireline
> protocol or forcing everyone to switch to a new authentication method.

Let me update my list of possible improvements:

1)  MD5 makes users feel uneasy (though our usage is mostly safe)

2)  The per-session salt sent to the client is only 32-bits, meaning
that it is possible to reply an observed MD5 hash in ~16k connection
attempts.

3)  Using the user name for the MD5 storage salt allows the MD5 stored
hash to be used on a different cluster if the user used the same
password.

4)  Using the user name for the MD5 storage salt allows the MD5 stored
hash to be used on the _same_ cluster.

5)  Using the user name for the MD5 storage salt causes the renaming of
a user to break the stored password.

I see your idea of hashing what the client sends to the server is to
currect #4?  And #2 becomes more of a problem?  And my idea of using a
random storage salt and longer session salt fix numbers 2 and 3, but not
4?

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

Bruce Momjian <bruce@momjian.us> writes:
> Let me update my list of possible improvements:

> 1)  MD5 makes users feel uneasy (though our usage is mostly safe)

> 2)  The per-session salt sent to the client is only 32-bits, meaning
> that it is possible to reply an observed MD5 hash in ~16k connection
> attempts.

> 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> hash to be used on a different cluster if the user used the same
> password.

> 4)  Using the user name for the MD5 storage salt allows the MD5 stored
> hash to be used on the _same_ cluster.

> 5)  Using the user name for the MD5 storage salt causes the renaming of
> a user to break the stored password.

What happened to "possession of the contents of pg_authid is sufficient
to log in"?  I thought fixing that was one of the objectives here.
        regards, tom lane

* Bruce Momjian (bruce@momjian.us) wrote:
> On Wed, Mar  4, 2015 at 02:46:54PM -0500, Stephen Frost wrote:
> > > Well, passwords are already addressed by certificate authentication, so
> > > what's your point?  I think we decided we wanted a way to do passwords
> > > without requiring network encryption.
> >
> > It's completely unclear to me what you mean by "passwords are already
> > addressed by certificate authentication."  Password-based and
> > certificate-based authentication are two independent mechanisms
> > available today, and both can be used with TLS.  Certainly the more
> > common implementation that I've come across is password-based
> > authentication through the md5 mechanism with TLS.  There are few places
> > which actually use client-side certificate-based authentication but tons
> > which use TLS.
>
> My point is we can't design a new authentication method to replace MD5
> if it doesn't work well without TLS.

This isn't a discussion about designing a new authentication method to
replace MD5.  I'm not interested in doing that- we should be using one
which has already been designed by experts in that field (just like we'd
prefer they use PG instead of writing their own relational databases).

This is about trying to make the current situation around MD5 better
without breaking existing clients.  This proposal, in my view and at
least that of some others, does that.  Does it make the md5
authentication method secure?  No, but nothing is going to do that
except deprecating it entirely.

Further, to the extent that we can make *common use-cases* of md5-based
authentication better, that's a good thing.

> > I was simply trying to explain what the 'newly discovered' vector
> > being discussed today is.  I complained about our implementation here 10
> > years ago and it has come up before this recent wave of complaints since
> > then, though perhaps with a bit less publicity, but I suspect that's
> > just because PG is getting popular.
> >
> > And, no, I'm not suggesting that we design differently because we're now
> > popular, but I do think we need to address this issue because it's very
> > clearly an obvious deficiency.  I trust you feel the same as you started
> > this thread.
> >
> > I brought up this approach because it avoids breaking the wireline
> > protocol or forcing everyone to switch to a new authentication method.
>
> Let me update my list of possible improvements:
>
> 1)  MD5 makes users feel uneasy (though our usage is mostly safe)

Saying it's "mostly safe" is questionable, at best.

> 2)  The per-session salt sent to the client is only 32-bits, meaning
> that it is possible to reply an observed MD5 hash in ~16k connection
> attempts.

Yes, and we have no (PG-based) mechanism to prevent those connection
attempts, which is a pretty horrible situation to be in.

> 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> hash to be used on a different cluster if the user used the same
> password.
>
> 4)  Using the user name for the MD5 storage salt allows the MD5 stored
> hash to be used on the _same_ cluster.
>
> 5)  Using the user name for the MD5 storage salt causes the renaming of
> a user to break the stored password.
>
> I see your idea of hashing what the client sends to the server is to
> currect #4?  And #2 becomes more of a problem?  And my idea of using a
> random storage salt and longer session salt fix numbers 2 and 3, but not
> 4?

The proposal I've been discussing for improving md5 while not breaking
the existing wireline protocol would address 3 and 4 in your list while
making #2 require fewer connection attempts by an attacker (but then
again, with either approach, it's not like it takes a long time on
today's systems to reach the requisite number of attempts to get a
successful login).

I've not seen a detailed explanation of what your proposal is and so I'm
not sure that I can really comment on it since I don't really know what
it is.  The comment about "using a random storage salt" doesn't make any
sense since we can't have both a session salt *and* a storage salt, and
the comment about a "longer session salt" implies a break in the
wireline protocol, which goes against the premise of this discussion.

If we're going to break the wireline protocol then we need to go to
SCRAM or some existing, well-defined authentication system and not
something home-grown.

I'd suggest reviewing Heikki's list of attack vectors and the matrix he
built.
Thanks!
    Stephen

* Tom Lane (tgl@sss.pgh.pa.us) wrote:
> Bruce Momjian <bruce@momjian.us> writes:
> > Let me update my list of possible improvements:
>
> > 1)  MD5 makes users feel uneasy (though our usage is mostly safe)
>
> > 2)  The per-session salt sent to the client is only 32-bits, meaning
> > that it is possible to reply an observed MD5 hash in ~16k connection
> > attempts.
>
> > 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> > hash to be used on a different cluster if the user used the same
> > password.
>
> > 4)  Using the user name for the MD5 storage salt allows the MD5 stored
> > hash to be used on the _same_ cluster.
>
> > 5)  Using the user name for the MD5 storage salt causes the renaming of
> > a user to break the stored password.
>
> What happened to "possession of the contents of pg_authid is sufficient
> to log in"?  I thought fixing that was one of the objectives here.

Yes, it certainly was.  I think Bruce was thinking that we could simply
hash what goes on to disk with an additional salt that's stored, but
that wouldn't actually work without requiring a change to the wireline
protocol, which is the basis of this entire line of discussion, in my
view.
Thanks!
    Stephen

Stephen Frost <sfrost@snowman.net> writes:
> * Tom Lane (tgl@sss.pgh.pa.us) wrote:
>> What happened to "possession of the contents of pg_authid is sufficient
>> to log in"?  I thought fixing that was one of the objectives here.

> Yes, it certainly was.  I think Bruce was thinking that we could simply
> hash what goes on to disk with an additional salt that's stored, but
> that wouldn't actually work without requiring a change to the wireline
> protocol, which is the basis of this entire line of discussion, in my
> view.

Hm, well, "don't change the wireline protocol" could be another wanna-have
... but if we want to stop using MD5, that's not really a realistic goal
is it?
        regards, tom lane

* Tom Lane (tgl@sss.pgh.pa.us) wrote:
> Stephen Frost <sfrost@snowman.net> writes:
> > * Tom Lane (tgl@sss.pgh.pa.us) wrote:
> >> What happened to "possession of the contents of pg_authid is sufficient
> >> to log in"?  I thought fixing that was one of the objectives here.
>
> > Yes, it certainly was.  I think Bruce was thinking that we could simply
> > hash what goes on to disk with an additional salt that's stored, but
> > that wouldn't actually work without requiring a change to the wireline
> > protocol, which is the basis of this entire line of discussion, in my
> > view.
>
> Hm, well, "don't change the wireline protocol" could be another wanna-have
> ... but if we want to stop using MD5, that's not really a realistic goal
> is it?

I'm trying to address both sides of the issue- improve the current
situation without breaking existing clients AND provide a new auth
method and encourage everyone to move to it as soon as they're able.  We
can't simply deprecate md5 as that would break pg_upgrade for any users
who are currently using it.

This half of the discussion has been all about improving md5 without
breaking the wireline protocol or existing users.

The other half of the discussion is about implementing a new
password-based authentication based on one of the vetted authentication
protocols already in use today (SCRAM or SRP, for example).  Using those
new authentication protocols would include a move off of the MD5 hashing
function, of course.  This would also mean breaking the on-disk hash,
but that's necessary anyway because what we do there today isn't secure
either and no amount of futzing is going to change that.

I've got nearly zero interest in trying to go half-way on this by
designing something that we think is secure which has had no external
review or anyone else who uses it.  Further, going that route makes me
very nervous that we'd decide on certain compromises in order to make
things easier for users without actually realising the problems with
such an approach (eg: "well, if we use hack X we wouldn't have to
change what is stored on disk and therefore we wouldn't break
pg_upgrade..").  I'd *much* rather have a clean break and migration
path for users.  If we had a password rotation capability then this kind
of a transistion would be a lot easier on our users and I'd definitely
recommend that we add that with this new authentication mechanism, to
address this kind of issue in the future (not to mention that's often
asked for..).  Password complexity would be another thing we should
really add and is also often requested.

Frankly, in the end, I don't see us being able to produce something in
time for this release unless someone can be dedicated to the effort over
the next couple of months, and therefore I'd prefer to improve the
current issues with md5 without breaking the wireline protocol than
simply do nothing (again).
Thanks,
    Stephen

On Wed, Mar 4, 2015 at 10:52 AM, Stephen Frost <sfrost@snowman.net> wrote:
> I've been discussing this with a few folks outside of the PG community
> (Debian and Openwall people specifically) and a few interesting ideas
> have come out of that which might be useful to discuss.
>
> The first is a "don't break anything" approach which would move the
> needle between "network data sensitivity" and "on-disk data sensitivity"
> a bit back in the direction of making the network data more sensitive.
>
> this approach looks like this: pre-determine and store the values (on a
> per-user basis, so a new field in pg_authid or some hack on the existing
> field) which will be sent to the client in the AuthenticationMD5Password
> message.  Further, calculate a random salt to be used when storing data
> in pg_authid.  Then, for however many variations we feel are necessary,
> calculate and store, for each AuthenticationMD5Password value:
>
> md5_challenge, hash(salt || response)
>
> We wouldn't store 4 billion of these, of course, which means that the
> challenge / response system becomes less effective on a per-user basis.
> We could, however, store X number of these and provide a lock-out
> mechanism (something users have asked after for a long time..) which
> would make it likely that the account would be locked before the
> attacker was able to gain access.  Further, an attacker with access to
> the backend still wouldn't see the user's cleartext password, nor would
> we store the cleartext password or a token in pg_authid which could be
> directly used for authentication, and we don't break the wireline
> protocol or existing installations (since we could detect that the
> pg_authid entry has the old-style and simply 'upgrade' it).

So, the server can only authenticate the user with the salts it has
stored, because those are the only salts for which it knows what the
response should be?  But then if somebody steels pg_authid, they'll
have the answers to the exact same set of questions that the server
knows how to ask.  And on top of that, replay attacks become massively
easier.  Any value you pick for X is going to be many orders of
magnitude smaller than 4 billion, and if it's not entirely trivial
you'll also have a huge expansion of the size of a pg_authid row.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

* Robert Haas (robertmhaas@gmail.com) wrote:
> So, the server can only authenticate the user with the salts it has
> stored, because those are the only salts for which it knows what the
> response should be?

That's correct- except that it doesn't directly know what the response
is, it only knows what the result of hashing the response with the
information provided by the client is.

> But then if somebody steels pg_authid, they'll
> have the answers to the exact same set of questions that the server
> knows how to ask.

Not quite.  They can't provide what's in pg_authid as an authentication
token in this case; that's the main thrust of this change from what is
in pg_authid today.  They would know which of the challenges are able to
be sent to the client and the result of hashing that with what they
actually need to send as an auth token to the server, but that's no
easier than today's unix password-based /etc/shadow approach where even
if you know the "answer" (in the form of the salt and the resulting
hash), you can't trivially provide the token needed to authenticate (the
password).

> And on top of that, replay attacks become massively
> easier.  Any value you pick for X is going to be many orders of
> magnitude smaller than 4 billion, and if it's not entirely trivial
> you'll also have a huge expansion of the size of a pg_authid row.

This is correct, as I was discussing with Bruce, replay attacks would
certainly require fewer attempts, though it's not like it'd take long to
do ~16k connection attempts today (how many you'd actually need to
attempt to have a high probability of getting in successfully with our
existing 4-byte salt).
Thanks!
    Stephen

On Wed, Mar  4, 2015 at 03:54:09PM -0500, Tom Lane wrote:
> Bruce Momjian <bruce@momjian.us> writes:
> > Let me update my list of possible improvements:
> 
> > 1)  MD5 makes users feel uneasy (though our usage is mostly safe)
> 
> > 2)  The per-session salt sent to the client is only 32-bits, meaning
> > that it is possible to reply an observed MD5 hash in ~16k connection
> > attempts.
> 
> > 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> > hash to be used on a different cluster if the user used the same
> > password.
> 
> > 4)  Using the user name for the MD5 storage salt allows the MD5 stored
> > hash to be used on the _same_ cluster.
> 
> > 5)  Using the user name for the MD5 storage salt causes the renaming of
> > a user to break the stored password.
> 
> What happened to "possession of the contents of pg_authid is sufficient
> to log in"?  I thought fixing that was one of the objectives here.

That is #4.

Addressing Stephen's ideas, I question whether there are enough people
who care about fixing #3 and #4 to require the use of TLS to fix it.  It
would be nice if we knew if the system was only using TLS, but we can't,
so we would need a GUC for the administrator to choose always-TLS to fix
#3 and #4.

One way to fix #2 would be to use a per-user or per-cluster counter for
the session salt, rather than a random number --- that would change
replays from ~16k to 4 billion, with no wire protocol change needed.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

On Wed, Mar  4, 2015 at 03:59:02PM -0500, Stephen Frost wrote:
> * Tom Lane (tgl@sss.pgh.pa.us) wrote:
> > Bruce Momjian <bruce@momjian.us> writes:
> > > Let me update my list of possible improvements:
> > 
> > > 1)  MD5 makes users feel uneasy (though our usage is mostly safe)
> > 
> > > 2)  The per-session salt sent to the client is only 32-bits, meaning
> > > that it is possible to reply an observed MD5 hash in ~16k connection
> > > attempts.
> > 
> > > 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> > > hash to be used on a different cluster if the user used the same
> > > password.
> > 
> > > 4)  Using the user name for the MD5 storage salt allows the MD5 stored
> > > hash to be used on the _same_ cluster.
> > 
> > > 5)  Using the user name for the MD5 storage salt causes the renaming of
> > > a user to break the stored password.
> > 
> > What happened to "possession of the contents of pg_authid is sufficient
> > to log in"?  I thought fixing that was one of the objectives here.
> 
> Yes, it certainly was.  I think Bruce was thinking that we could simply
> hash what goes on to disk with an additional salt that's stored, but
> that wouldn't actually work without requiring a change to the wireline
> protocol, which is the basis of this entire line of discussion, in my
> view.

I was not really focused on needing or not needing wire protocol
changes, but rather trying to understand the attack vectors and how they
could be fixed, in general.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

On Wed, Mar  4, 2015 at 04:19:00PM -0500, Stephen Frost wrote:
> > Hm, well, "don't change the wireline protocol" could be another wanna-have
> > ... but if we want to stop using MD5, that's not really a realistic goal
> > is it?
> 
> I'm trying to address both sides of the issue- improve the current
> situation without breaking existing clients AND provide a new auth
> method and encourage everyone to move to it as soon as they're able.  We
> can't simply deprecate md5 as that would break pg_upgrade for any users
> who are currently using it.

Actually, pg_upgrade uses 'trust' and a private socket file, at least on
Unix.  Of course, post-upgrade, users would have trouble logging in.

> This half of the discussion has been all about improving md5 without
> breaking the wireline protocol or existing users.
> 
> The other half of the discussion is about implementing a new
> password-based authentication based on one of the vetted authentication
> protocols already in use today (SCRAM or SRP, for example).  Using those
> new authentication protocols would include a move off of the MD5 hashing
> function, of course.  This would also mean breaking the on-disk hash,
> but that's necessary anyway because what we do there today isn't secure
> either and no amount of futzing is going to change that.

While I don't like the requirement to use TLS to improve MD5 fix, I also
don't like the idea of having users go through updating all these
passwords only to have us implement the _right_ solution in the next
release.  I don't see why it is useful to be patching up MD5 with a TLS
requirement when we know they should be moving to SCRAM or SRP.  If the
MD5 change was transparent to users/admins, that would be different.

> I've got nearly zero interest in trying to go half-way on this by
> designing something that we think is secure which has had no external
> review or anyone else who uses it.  Further, going that route makes me
> very nervous that we'd decide on certain compromises in order to make
> things easier for users without actually realising the problems with
> such an approach (eg: "well, if we use hack X we wouldn't have to
> change what is stored on disk and therefore we wouldn't break

I am not happy to blindly accept a new security setup without
understanding exactly what it is trying to fix, which is why I am asking
all these questions.

> pg_upgrade..").  I'd *much* rather have a clean break and migration
> path for users.  If we had a password rotation capability then this kind

Yes, I think we are now saying the same thing.

> of a transistion would be a lot easier on our users and I'd definitely
> recommend that we add that with this new authentication mechanism, to
> address this kind of issue in the future (not to mention that's often
> asked for..).  Password complexity would be another thing we should
> really add and is also often requested.

I agree our password management could use improvement.

> Frankly, in the end, I don't see us being able to produce something in
> time for this release unless someone can be dedicated to the effort over
> the next couple of months, and therefore I'd prefer to improve the
> current issues with md5 without breaking the wireline protocol than
> simply do nothing (again).

I am not sure why we have to shove something into 9.5 --- as you said,
this issue has been known about for 10+ years.

I think we should do what we can to improve MD5 in cases where the
user/admin needs to take no action, and then move to add a better
authentication method.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

Catching up here ...

On 03/03/2015 06:01 PM, Bruce Momjian wrote:
> It feels like MD5 has accumulated enough problems that we need to start
> looking for another way to store and pass passwords.  The MD5 problems
> are:
> 
> 1)  MD5 makes users feel uneasy (though our usage is mostly safe) 
> 
> 2)  The per-session salt sent to the client is only 32-bits, meaning
> that it is possible to reply an observed MD5 hash in ~16k connection
> attempts.

Seems like we could pretty easily increase the size of the salt.  Of
course, that just increases the required number of connection attempts,
without really fixing the problem.

> 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> hash to be used on a different cluster if the user used the same
> password. 

This is a feature as well as a bug. For example, pgBouncer relies on
this aspect of md5 auth.

> 4)  Using the user name for the MD5 storage salt causes the renaming of
> a user to break the stored password.

Wierdly, in 17 years of Postgres, I've never encountered this issue.

So, are we more worried about attackers getting a copy of pg_authid, or
sniffing the hash on the wire?

-- 
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Wed, Mar  4, 2015 at 05:56:25PM -0800, Josh Berkus wrote:
> Catching up here ...
> 
> On 03/03/2015 06:01 PM, Bruce Momjian wrote:
> > It feels like MD5 has accumulated enough problems that we need to start
> > looking for another way to store and pass passwords.  The MD5 problems
> > are:
> > 
> > 1)  MD5 makes users feel uneasy (though our usage is mostly safe) 
> > 
> > 2)  The per-session salt sent to the client is only 32-bits, meaning
> > that it is possible to reply an observed MD5 hash in ~16k connection
> > attempts.
> 
> Seems like we could pretty easily increase the size of the salt.  Of
> course, that just increases the required number of connection attempts,
> without really fixing the problem.
> 
> > 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> > hash to be used on a different cluster if the user used the same
> > password. 
> 
> This is a feature as well as a bug. For example, pgBouncer relies on
> this aspect of md5 auth.
> 
> > 4)  Using the user name for the MD5 storage salt causes the renaming of
> > a user to break the stored password.
> 
> Wierdly, in 17 years of Postgres, I've never encountered this issue.
> 
> So, are we more worried about attackers getting a copy of pg_authid, or
> sniffing the hash on the wire?

Both.  Stephen is more worried about pg_authid, but I am more worried
about sniffing.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Josh Berkus (josh@agliodbs.com) wrote:
> Catching up here ...
>
> On 03/03/2015 06:01 PM, Bruce Momjian wrote:
> > It feels like MD5 has accumulated enough problems that we need to start
> > looking for another way to store and pass passwords.  The MD5 problems
> > are:
> >
> > 1)  MD5 makes users feel uneasy (though our usage is mostly safe)
> >
> > 2)  The per-session salt sent to the client is only 32-bits, meaning
> > that it is possible to reply an observed MD5 hash in ~16k connection
> > attempts.
>
> Seems like we could pretty easily increase the size of the salt.  Of
> course, that just increases the required number of connection attempts,
> without really fixing the problem.

Please do not propose hacks on top of the existing "md5" authentication
method which break the wireline protocol.  There is absolutely nothing
useful to be gained from that.  We need to introduce a new auth method
with whatever protocol changes that requires without breaking the
existing auth method.  Discussing trade-offs of changing the existing
md5 mechanism *without* breaking the wireline protocol may be worthwhile
as we might be able to improve things a bit there, but nothing there is
a proper solution for security conscious individuals.

> > 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> > hash to be used on a different cluster if the user used the same
> > password.
>
> This is a feature as well as a bug. For example, pgBouncer relies on
> this aspect of md5 auth.

It's not a feature and pgBouncer could be made to not rely on this.

> > 4)  Using the user name for the MD5 storage salt causes the renaming of
> > a user to break the stored password.
>
> Wierdly, in 17 years of Postgres, I've never encountered this issue.

I agree, that's kind of odd. :)

> So, are we more worried about attackers getting a copy of pg_authid, or
> sniffing the hash on the wire?

They are both attack vectors to consider but most applications address
the network-based risk through TLS and have a hash-based approach to
address the pg_authid-based risk.  Administrators are used to that and
are quite surprised to discover that PG doesn't work that way.  As I
mentioned up-thread, it's certainly very rare for anyone concerned about
a network-based risk to *not* use TLS, but they tend to still use
passwords for the actual authentication mechansim and the md5 auth mech
makes the wrong trade-off for them.  The password auth mech isn't ideal
either since the server ends up seeing the PW.  The change I'm
suggesting addresses both the pg_authid-based risk and the "server
seeing the PW" risk without changing the wireline protocol.
Thanks,
    Stephen

* Bruce Momjian (bruce@momjian.us) wrote:
> On Wed, Mar  4, 2015 at 05:56:25PM -0800, Josh Berkus wrote:
> > So, are we more worried about attackers getting a copy of pg_authid, or
> > sniffing the hash on the wire?
>
> Both.  Stephen is more worried about pg_authid, but I am more worried
> about sniffing.

I'm also worried about both, but if the admin is worried about sniffing
in their environment, they're much more likely to use TLS than to set up
client side certificates, kerberos, or some other strong auth mechanism,
simply because TLS is pretty darn easy to get working and distros set it
up for you by default.
Thanks,    Stephen

* Bruce Momjian (bruce@momjian.us) wrote:
> One way to fix #2 would be to use a per-user or per-cluster counter for
> the session salt, rather than a random number --- that would change
> replays from ~16k to 4 billion, with no wire protocol change needed.

I'm not against doing that if we decide to ignore the pg_authid-based
vector (which we could certainly do), but given the relatively poor
hashing algorithm we use and the small salt, along with the commonly
used practice of using TLS to address network-based attacks, I'm not
sure it's really worth it.

Note that changing the algorithm or the salt would require a wireline
protocol change and therefore isn't interesting to consider as, if we're
going to do that, we should be moving to a vetted solution instead.
Thanks!
    Stephen

* Bruce Momjian (bruce@momjian.us) wrote:
> On Wed, Mar  4, 2015 at 04:19:00PM -0500, Stephen Frost wrote:
> > > Hm, well, "don't change the wireline protocol" could be another wanna-have
> > > ... but if we want to stop using MD5, that's not really a realistic goal
> > > is it?
> >
> > I'm trying to address both sides of the issue- improve the current
> > situation without breaking existing clients AND provide a new auth
> > method and encourage everyone to move to it as soon as they're able.  We
> > can't simply deprecate md5 as that would break pg_upgrade for any users
> > who are currently using it.
>
> Actually, pg_upgrade uses 'trust' and a private socket file, at least on
> Unix.  Of course, post-upgrade, users would have trouble logging in.

The post-upgrade trouble logging in is what I was getting at.  Of
course, that issue exists with a pg_dump-based approach also, so my
reference to pg_upgrade above wasn't accurate and it shold have been
"would break upgrades for any users who are currently using it."

> > This half of the discussion has been all about improving md5 without
> > breaking the wireline protocol or existing users.
> >
> > The other half of the discussion is about implementing a new
> > password-based authentication based on one of the vetted authentication
> > protocols already in use today (SCRAM or SRP, for example).  Using those
> > new authentication protocols would include a move off of the MD5 hashing
> > function, of course.  This would also mean breaking the on-disk hash,
> > but that's necessary anyway because what we do there today isn't secure
> > either and no amount of futzing is going to change that.
>
> While I don't like the requirement to use TLS to improve MD5 fix, I also
> don't like the idea of having users go through updating all these
> passwords only to have us implement the _right_ solution in the next
> release.  I don't see why it is useful to be patching up MD5 with a TLS
> requirement when we know they should be moving to SCRAM or SRP.  If the
> MD5 change was transparent to users/admins, that would be different.

So, TLS *isn't* an actual requirement with the approach that I've
outlined, it's just that if you're not using it then you have a somewhat
larger risk of successful network-based attacks, but then, if you're
not using TLS then you're unlikely to be worried about that vector.

> > I've got nearly zero interest in trying to go half-way on this by
> > designing something that we think is secure which has had no external
> > review or anyone else who uses it.  Further, going that route makes me
> > very nervous that we'd decide on certain compromises in order to make
> > things easier for users without actually realising the problems with
> > such an approach (eg: "well, if we use hack X we wouldn't have to
> > change what is stored on disk and therefore we wouldn't break
>
> I am not happy to blindly accept a new security setup without
> understanding exactly what it is trying to fix, which is why I am asking
> all these questions.

I certainly didn't intend to suggest that anyone blindly accept a new
security setup.  I don't mind the questions but I do get a bit
frustrated at the suggestions that we can "fix" the md5 auth mechanism
by simply increasing the salt or putting in a better hashing algorithm.
Those are not solutions to this authentication challenge- for that, we
need to look at SCRAM or SRP, where RFCs have been reviewed and
published which outline exactly how they work and why they work the way
they do.  I'd certainly encourage everyone interested in this to go look
at those RFCs.

SCRAM - https://tools.ietf.org/html/rfc5802
SRP - https://www.ietf.org/rfc/rfc2945.txt

> > of a transistion would be a lot easier on our users and I'd definitely
> > recommend that we add that with this new authentication mechanism, to
> > address this kind of issue in the future (not to mention that's often
> > asked for..).  Password complexity would be another thing we should
> > really add and is also often requested.
>
> I agree our password management could use improvement.

I'm *very* glad to hear that.  When I brought it up 10-or-so years ago,
there was very little interest in these kinds of improvements.

> > Frankly, in the end, I don't see us being able to produce something in
> > time for this release unless someone can be dedicated to the effort over
> > the next couple of months, and therefore I'd prefer to improve the
> > current issues with md5 without breaking the wireline protocol than
> > simply do nothing (again).
>
> I am not sure why we have to shove something into 9.5 --- as you said,
> this issue has been known about for 10+ years.

It'd be nice to show that we're being responsive when issues are brought
up, even if they've existed for a long time (because, in the minds of
some, that we've done nothing in 10 years doesn't exactly reflect very
well on us :( ).

> I think we should do what we can to improve MD5 in cases where the
> user/admin needs to take no action, and then move to add a better
> authentication method.

Great, I believe that we're on the same page with this then.
Thanks!
    Stephen

On 3/4/15 2:56 PM, Stephen Frost wrote:
>> 2)  The per-session salt sent to the client is only 32-bits, meaning
>> >that it is possible to reply an observed MD5 hash in ~16k connection
>> >attempts.
> Yes, and we have no (PG-based) mechanism to prevent those connection
> attempts, which is a pretty horrible situation to be in.

Is there some reason we don't just fix that? I'm thinking that this is a 
special case where we could just modify the pg_auth tuple in-place 
without bloating the catalog (we already do that somewhere else). Is 
there something else that makes this difficult? Are we afraid of an 
extra GUC to control it?
-- 
Jim Nasby, Data Architect, Blue Treble Consulting
Data in Trouble? Get it in Treble! http://BlueTreble.com

* Jim Nasby (Jim.Nasby@BlueTreble.com) wrote:
> On 3/4/15 2:56 PM, Stephen Frost wrote:
> >>2)  The per-session salt sent to the client is only 32-bits, meaning
> >>>that it is possible to reply an observed MD5 hash in ~16k connection
> >>>attempts.
> >Yes, and we have no (PG-based) mechanism to prevent those connection
> >attempts, which is a pretty horrible situation to be in.
>
> Is there some reason we don't just fix that? I'm thinking that this
> is a special case where we could just modify the pg_auth tuple
> in-place without bloating the catalog (we already do that somewhere
> else). Is there something else that makes this difficult? Are we
> afraid of an extra GUC to control it?

I'm all for it, though I would ask that we provide a way for superusers
to delegate the ability to reset locked accounts to non-superusers.

I'd want to think about it a bit more before settling on using pg_authid
to track the data.  In any case, I do think we need a way to disable
this ability for certain roles and, furtherr, that we not track failed
logins in cases where it's disabled (which might well be the default- I
don't think we want to add this overhead for systems which have lots of
recurring logins (think application users where they aren't doing
pooling).
Thanks!
    Stephen

On 3/5/15 2:17 PM, Stephen Frost wrote:
> * Jim Nasby (Jim.Nasby@BlueTreble.com) wrote:
>> On 3/4/15 2:56 PM, Stephen Frost wrote:
>>>> 2)  The per-session salt sent to the client is only 32-bits, meaning
>>>>> that it is possible to reply an observed MD5 hash in ~16k connection
>>>>> attempts.
>>> Yes, and we have no (PG-based) mechanism to prevent those connection
>>> attempts, which is a pretty horrible situation to be in.
>>
>> Is there some reason we don't just fix that? I'm thinking that this
>> is a special case where we could just modify the pg_auth tuple
>> in-place without bloating the catalog (we already do that somewhere
>> else). Is there something else that makes this difficult? Are we
>> afraid of an extra GUC to control it?
>
> I'm all for it, though I would ask that we provide a way for superusers
> to delegate the ability to reset locked accounts to non-superusers.
>
> I'd want to think about it a bit more before settling on using pg_authid

I guess it's a question of how durable we want it to be. We could 
conceivable keep it in shared memory and let it wipe on a crash.

But we already have code that ignores MVCC on a catalog table (IIRC for 
updating pg_class stats after vacuum) so the pattern is there. I don't 
see that we need more sophistication than that...

> to track the data.  In any case, I do think we need a way to disable
> this ability for certain roles

In the interest of something for this release... do we really need that? 
My thought is we just special-case the postgres user and be done with 
it. Though, if there's some other way to reset an account from the 
shell, no need to even special case postgres.

Though, I guess if we just follow the normal GUC behavior of allowing 
per-database and -user overrides it wouldn't be that hard.

> and, furtherr, that we not track failed
> logins in cases where it's disabled (which might well be the default- I
> don't think we want to add this overhead for systems which have lots of
> recurring logins (think application users where they aren't doing
> pooling).

Yeah, presumably if allowed_authentication_failures < 0 then we don't 
bother with the check at all.
-- 
Jim Nasby, Data Architect, Blue Treble Consulting
Data in Trouble? Get it in Treble! http://BlueTreble.com

* Jim Nasby (Jim.Nasby@BlueTreble.com) wrote:
> On 3/5/15 2:17 PM, Stephen Frost wrote:
> >* Jim Nasby (Jim.Nasby@BlueTreble.com) wrote:
> >I'm all for it, though I would ask that we provide a way for superusers
> >to delegate the ability to reset locked accounts to non-superusers.
> >
> >I'd want to think about it a bit more before settling on using pg_authid
>
> I guess it's a question of how durable we want it to be. We could
> conceivable keep it in shared memory and let it wipe on a crash.
>
> But we already have code that ignores MVCC on a catalog table (IIRC
> for updating pg_class stats after vacuum) so the pattern is there. I
> don't see that we need more sophistication than that...

I'm not sure we should jump to that immediately..

> >to track the data.  In any case, I do think we need a way to disable
> >this ability for certain roles
>
> In the interest of something for this release... do we really need
> that? My thought is we just special-case the postgres user and be
> done with it. Though, if there's some other way to reset an account
> from the shell, no need to even special case postgres.

I don't think this is going to happen for 9.5 unless someone shows up
with code in the *very* short term..  Further, realistically, we would
want to design this properly and not just hack something together.

> Though, I guess if we just follow the normal GUC behavior of
> allowing per-database and -user overrides it wouldn't be that hard.

Yes, using the GUC-based approach would allow users to be excluded from
an overall (or per-database) policy.
Thanks,
    Stephen

Stephen Frost wrote:
> * Tom Lane (tgl@sss.pgh.pa.us) wrote:
>> Bruce Momjian <bruce@momjian.us> writes:
>>> Let me update my list of possible improvements:
>>
>>> 1)  MD5 makes users feel uneasy (though our usage is mostly safe)
>>
>>> 2)  The per-session salt sent to the client is only 32-bits, meaning
>>> that it is possible to reply an observed MD5 hash in ~16k connection
>>> attempts.
>>
>>> 3)  Using the user name for the MD5 storage salt allows the MD5 stored
>>> hash to be used on a different cluster if the user used the same
>>> password.
>>
>>> 4)  Using the user name for the MD5 storage salt allows the MD5 stored
>>> hash to be used on the _same_ cluster.
>>
>>> 5)  Using the user name for the MD5 storage salt causes the renaming of
>>> a user to break the stored password.
>>
>> What happened to "possession of the contents of pg_authid is sufficient
>> to log in"?  I thought fixing that was one of the objectives here.
> 
> Yes, it certainly was.  I think Bruce was thinking that we could simply
> hash what goes on to disk with an additional salt that's stored, but
> that wouldn't actually work without requiring a change to the wireline
> protocol, which is the basis of this entire line of discussion, in my
> view.

This article
https://hashcat.net/misc/postgres-pth/postgres-pth.pdf
has some ideas about how to improve the situation.

Yours,
Laurenz Albe

<p dir="ltr">Locked accounts are a terrible terrible idea. All they do is hand attackers an easy DOS vulnerability.
They'repure security theatre if your authentication isn't vulnerable to brute force attacks and an unreliable band-aid
ifthey are.<p dir="ltr">Having dealt with mechanisms for locking accounts in other database they're much more
complicatedthan they appear. You need to deal with different requirements for different users, have multiple knobs for
howit triggers and resolves, have tools for auditing the connection attempts to determine if they're legitimate and
identifywhere the incorrect attempts are coming from, and so on. And all that accomplishes in the best case scenario is
havinglots of busy-work support requests responding to locked accounts  and in the worst case scenario upgrading minor
issuesinto major service outages. 

* Albe Laurenz (laurenz.albe@wien.gv.at) wrote:
> Stephen Frost wrote:
> > Yes, it certainly was.  I think Bruce was thinking that we could simply
> > hash what goes on to disk with an additional salt that's stored, but
> > that wouldn't actually work without requiring a change to the wireline
> > protocol, which is the basis of this entire line of discussion, in my
> > view.
>
> This article
> https://hashcat.net/misc/postgres-pth/postgres-pth.pdf
> has some ideas about how to improve the situation.

This falls into the same category as some other proposed changes- it
requires wireline protocol changes, which means it really isn't
interesting to consider.

While I'm not surprised, it's certainly unfortunate that none of these
articles bother to point out what would be really useful to PG users-
how they can decide which risks they want to accept by choosing the
authentication method.  Using 'password', while it isn't great because
of the poor salt used (username), it isn't vulnerable to the 'PTH'
attack, and better authentication methods are available (certificates,
Kerberos, PAM, etc).  Admittedly, the default is md5 for most
distributions, but that's because the better auth methods require
depending on external systems and distribution installers can't know if
those systems have been set up or not.
Thanks,
    Stephen

Greg,

* Greg Stark (stark@mit.edu) wrote:
> Locked accounts are a terrible terrible idea. All they do is hand attackers
> an easy DOS vulnerability. They're pure security theatre if your
> authentication isn't vulnerable to brute force attacks and an unreliable
> band-aid if they are.

For starters, our authentication *is* vulnerable to brute force attacks
(as is any password-based system, and I doubt we're going to completely
drop support for them regardless of what else we do here), and second
the account lock-out capability is still required in NIST 800-53 rev4 and
is covered by AC-7.

http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-53r4.pdf

AC-7 does address the DOS risk and allows organizations to unlock the
account after an organization-specified delay.

I've been able to address that in the past by using Kerberos for PG
instead and implementing the lock-out and other requirements in this
area that PG doesn't support that way, but that isn't available in all
situations which leads to far worse solutions having to be used to meet
these requirements (sorry, but hacking up a PAM-based approach which
uses cracklib and pam_deny is *really* ugly).

> Having dealt with mechanisms for locking accounts in other database they're
> much more complicated than they appear. You need to deal with different
> requirements for different users, have multiple knobs for how it triggers
> and resolves, have tools for auditing the connection attempts to determine
> if they're legitimate and identify where the incorrect attempts are coming
> from, and so on. And all that accomplishes in the best case scenario is
> having lots of busy-work support requests responding to locked accounts
> and in the worst case scenario upgrading minor issues into major service
> outages.

I agree that they're complicated and that auditing is another necessary
component that we don't currently have.  We are woefully behind in these
areas and should certainly look to what others have done and learned
over the past 10 years that these issues have more-or-less been ignored,
but I don't believe we can or should continue to ignore them as it makes
PG unnecessairly more difficult to use in many areas.
Thanks,
    Stephen

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

> > > 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> > > hash to be used on a different cluster if the user used the same
> > > password. 
> > 
> > This is a feature as well as a bug. For example, pgBouncer relies on
> > this aspect of md5 auth.
> 
> It's not a feature and pgBouncer could be made to not rely on this.

Perhaps one of the requirements of a new auth method should be to allow
middlemen such as connection poolers.  It's been over two years since I
had a look, but IIRC pgbouncer had the very ugly requirement of its own
copy of user/passwords in a file, and of course you had to update it
separately if you changed the password in the server.  We need to make
it possible for it not to require any such thing.

-- 
Álvaro Herrera                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Alvaro,

* Alvaro Herrera (alvherre@2ndquadrant.com) wrote:
> Stephen Frost wrote:
> > * Josh Berkus (josh@agliodbs.com) wrote:
>
> > > > 3)  Using the user name for the MD5 storage salt allows the MD5 stored
> > > > hash to be used on a different cluster if the user used the same
> > > > password.
> > >
> > > This is a feature as well as a bug. For example, pgBouncer relies on
> > > this aspect of md5 auth.
> >
> > It's not a feature and pgBouncer could be made to not rely on this.
>
> Perhaps one of the requirements of a new auth method should be to allow
> middlemen such as connection poolers.  It's been over two years since I
> had a look, but IIRC pgbouncer had the very ugly requirement of its own
> copy of user/passwords in a file, and of course you had to update it
> separately if you changed the password in the server.  We need to make
> it possible for it not to require any such thing.

If we go this direction, we've got to be *very* careful that it's only
when the admin enables it.  man-in-the-middle attacks are quite real and
you're essentially asking that we support them intentionally.  I agree
that we want to support connection poolers but they have an inherent
MITM profile.

Note that this is also something which is up to the pooling system and
which we can't control.  A good example is Kerberos.  Kerberos has had a
way for authentication to be proxied for a long time (with some controls
to say which principals are allowed to be proxied, and which systems are
allowed to proxy on behalf of other principals), but pgbouncer doesn't
support that even though it'd eliminate the need for it to have a user /
password file.

Also, I don't expect we're going to remove md5 any time soon and,
frankly, people using pgbouncer probably aren't worried about the issues
which exist with that mechanism and care much more about performance, as
it doesn't even support TLS..
Thanks!
    Stephen

Stephen Frost wrote:
> Alvaro,
> 
> * Alvaro Herrera (alvherre@2ndquadrant.com) wrote:

> > Perhaps one of the requirements of a new auth method should be to allow
> > middlemen such as connection poolers.  It's been over two years since I
> > had a look, but IIRC pgbouncer had the very ugly requirement of its own
> > copy of user/passwords in a file, and of course you had to update it
> > separately if you changed the password in the server.  We need to make
> > it possible for it not to require any such thing.
> 
> If we go this direction, we've got to be *very* careful that it's only
> when the admin enables it.  man-in-the-middle attacks are quite real and
> you're essentially asking that we support them intentionally.  I agree
> that we want to support connection poolers but they have an inherent
> MITM profile.

Sure.  I was thinking we would have some mechanism to authenticate the
connection as coming from a pooler that has been previously authorized;
something simple as a new pg_hba.conf entry type for "poolers" that are
only authorized to connect to such-and-such databases, perhaps limit to
such-and-such users, etc.

> Note that this is also something which is up to the pooling system and
> which we can't control.  A good example is Kerberos.  Kerberos has had a
> way for authentication to be proxied for a long time (with some controls
> to say which principals are allowed to be proxied, and which systems are
> allowed to proxy on behalf of other principals), but pgbouncer doesn't
> support that even though it'd eliminate the need for it to have a user /
> password file.

True.

I think Kerberos implementations are uncommon, and the complexity of
getting the whole thing up and running is probably the major reason; or
at least there's the common belief that it's so.

My guess is that since there are few users, pgbouncer devs see little
reason to implement it also.  Chicken and egg, perhaps.

(Actually, is pgbouncer under active maintenance at all these days?)

> Also, I don't expect we're going to remove md5 any time soon and,
> frankly, people using pgbouncer probably aren't worried about the issues
> which exist with that mechanism and care much more about performance, as
> it doesn't even support TLS..

I think the accept the issues because they have no other choice, not
because they are really all that OK with them.

-- 
Álvaro Herrera                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

* Alvaro Herrera (alvherre@2ndquadrant.com) wrote:
> Stephen Frost wrote:
> > * Alvaro Herrera (alvherre@2ndquadrant.com) wrote:
> > > Perhaps one of the requirements of a new auth method should be to allow
> > > middlemen such as connection poolers.  It's been over two years since I
> > > had a look, but IIRC pgbouncer had the very ugly requirement of its own
> > > copy of user/passwords in a file, and of course you had to update it
> > > separately if you changed the password in the server.  We need to make
> > > it possible for it not to require any such thing.
> >
> > If we go this direction, we've got to be *very* careful that it's only
> > when the admin enables it.  man-in-the-middle attacks are quite real and
> > you're essentially asking that we support them intentionally.  I agree
> > that we want to support connection poolers but they have an inherent
> > MITM profile.
>
> Sure.  I was thinking we would have some mechanism to authenticate the
> connection as coming from a pooler that has been previously authorized;
> something simple as a new pg_hba.conf entry type for "poolers" that are
> only authorized to connect to such-and-such databases, perhaps limit to
> such-and-such users, etc.

Well, server-side, we already have that- have pgbouncer run on the
database server (something which I'm typically in favor of anyway) and
use 'peer'.  If it supported TLS then it could use certificates instead.
The question is what to do after the pooler has connected and that's
actually a generic issue which goes beyond poolers and into
applications, basically, "how can I re-authenticate this connection
using a different role."  We have SET ROLE, but that gives a lot of
power to the role the pooler logs in as.  It'd definitely be neat to
provide a way to use SCRAM or similar to do that re-authentication after
the initial connection.

> I think Kerberos implementations are uncommon, and the complexity of
> getting the whole thing up and running is probably the major reason; or
> at least there's the common belief that it's so.

Kerberos is *extremely* common- it's what Active Directory uses, after
all.  Where it isn't used are hosting/cloud providers and the like where
they want to support any and every device their client might want to use
to connect, or places which don't realize that AD uses Kerberos and that
it can be leveraged to provide auth to PG.

> My guess is that since there are few users, pgbouncer devs see little
> reason to implement it also.  Chicken and egg, perhaps.

pgbouncer isn't as necessary in the kinds of environments that use
Kerberos because you aren't having lots of connections/s from distinct
principals to a given server.  It's just not the profile that pgbouncer
is built for, but that's kind of my point here- pgbouncer is far more
concerned with performance than security because the assumption going in
is that you have a trusted server connecting to a trusted server.
That's an acceptable assumption for a lot of environments, though not
all.

> (Actually, is pgbouncer under active maintenance at all these days?)

I understand Andrew has been helping with it, but my guess is that's
more maintenance and less active development.

> > Also, I don't expect we're going to remove md5 any time soon and,
> > frankly, people using pgbouncer probably aren't worried about the issues
> > which exist with that mechanism and care much more about performance, as
> > it doesn't even support TLS..
>
> I think the accept the issues because they have no other choice, not
> because they are really all that OK with them.

I'd certainly be very happy to see someone interested enough in this
issue to dedicate resources (either human time or funding) to implement
TLS for pgbouncer...
Thanks!
    Stephen

On 03/06/2015 08:19 AM, Stephen Frost wrote:
> * Alvaro Herrera (alvherre@2ndquadrant.com) wrote:
>> Stephen Frost wrote:
>> Sure.  I was thinking we would have some mechanism to authenticate the
>> connection as coming from a pooler that has been previously authorized;
>> something simple as a new pg_hba.conf entry type for "poolers" that are
>> only authorized to connect to such-and-such databases, perhaps limit to
>> such-and-such users, etc.
> 
> Well, server-side, we already have that- have pgbouncer run on the
> database server (something which I'm typically in favor of anyway) and
> use 'peer'.  If it supported TLS then it could use certificates instead.
> The question is what to do after the pooler has connected and that's
> actually a generic issue which goes beyond poolers and into
> applications, basically, "how can I re-authenticate this connection
> using a different role."  We have SET ROLE, but that gives a lot of
> power to the role the pooler logs in as.  It'd definitely be neat to
> provide a way to use SCRAM or similar to do that re-authentication after
> the initial connection.

Using pgbouncer on the DB server is common, but less common that using
it on an intermediate server or even the app server itself.  So anything
we create needs to be implementable with all three configurations in
some way.

What I'd particularly like to see, of course, is some way for a
pgbouncer-like proxy to authenticate a client connection, then to use
those credentials to authenticate to the database server, without every
storing a reusable auth token (such as the current md5) on the pgbouncer
server.  And, of course, TLS support.

> pgbouncer isn't as necessary in the kinds of environments that use
> Kerberos because you aren't having lots of connections/s from distinct
> principals to a given server.  It's just not the profile that pgbouncer
> is built for, but that's kind of my point here- pgbouncer is far more
> concerned with performance than security because the assumption going in
> is that you have a trusted server connecting to a trusted server.
> That's an acceptable assumption for a lot of environments, though not
> all.

It's not that pgbouncer users don't want more secure connections; it's
that they can't have them.  I know users who are using stunnel to
connect to pgbouncer because that's the only way they can secure it.

>> (Actually, is pgbouncer under active maintenance at all these days?)
> 
> I understand Andrew has been helping with it, but my guess is that's
> more maintenance and less active development.

No, there's active development; look for some new pgbouncer features
over the next 6-9 months.

More importantly, pgbouncer is *used* by a large portion of our users --
somewhere between 20% and 50% based on my experience with our clients
and at conferences (our clients are actually around 70%
pgbouncer-using).  So if our md5-replacement solution isn't compatible
with pgbouncer, or doesn't arrive with a replacement for pgbouncer with
which it is compatible, will result in us supporting old-style md5 for a
long time or a lot of people using "password".

>>> Also, I don't expect we're going to remove md5 any time soon and,
>>> frankly, people using pgbouncer probably aren't worried about the issues
>>> which exist with that mechanism and care much more about performance, as
>>> it doesn't even support TLS..
>>
>> I think the accept the issues because they have no other choice, not
>> because they are really all that OK with them.
> 
> I'd certainly be very happy to see someone interested enough in this
> issue to dedicate resources (either human time or funding) to implement
> TLS for pgbouncer...

PGX would be happy to implement this if someone wanted to find funding.I'd expect that a couple other consulting
companieswould jump at it as
 
well.  It's just that so far nobody has wanted to foot the bill.

Kickstarter, maybe?

-- 
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Thu, Mar  5, 2015 at 11:15:55AM -0500, Stephen Frost wrote:
> * Bruce Momjian (bruce@momjian.us) wrote:
> > On Wed, Mar  4, 2015 at 05:56:25PM -0800, Josh Berkus wrote:
> > > So, are we more worried about attackers getting a copy of pg_authid, or
> > > sniffing the hash on the wire?
> > 
> > Both.  Stephen is more worried about pg_authid, but I am more worried
> > about sniffing.
> 
> I'm also worried about both, but if the admin is worried about sniffing
> in their environment, they're much more likely to use TLS than to set up
> client side certificates, kerberos, or some other strong auth mechanism,
> simply because TLS is pretty darn easy to get working and distros set it
> up for you by default.

I think your view might be skewed.  I think there many people who care
about password security who don't care to do TLS.

Also, my suggestion to use a counter for the session salt, to reduce
replay from 16k to 4 billion, has not received any comments, and it does
not break the wire protocol.  I feel that is an incremental improvement
we should consider.

I think you are minimizing the downsize of your idea using X challenges
instead of 16k challenges to get in.  Again, if my idea is valid, it
would be X challenges vs 4 billion challenges.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

On Fri, Mar  6, 2015 at 12:50:14PM -0800, Josh Berkus wrote:
> On 03/06/2015 08:19 AM, Stephen Frost wrote:
> > * Alvaro Herrera (alvherre@2ndquadrant.com) wrote:
> >> Stephen Frost wrote:
> >> Sure.  I was thinking we would have some mechanism to authenticate the
> >> connection as coming from a pooler that has been previously authorized;
> >> something simple as a new pg_hba.conf entry type for "poolers" that are
> >> only authorized to connect to such-and-such databases, perhaps limit to
> >> such-and-such users, etc.
> > 
> > Well, server-side, we already have that- have pgbouncer run on the
> > database server (something which I'm typically in favor of anyway) and
> > use 'peer'.  If it supported TLS then it could use certificates instead.
> > The question is what to do after the pooler has connected and that's
> > actually a generic issue which goes beyond poolers and into
> > applications, basically, "how can I re-authenticate this connection
> > using a different role."  We have SET ROLE, but that gives a lot of
> > power to the role the pooler logs in as.  It'd definitely be neat to
> > provide a way to use SCRAM or similar to do that re-authentication after
> > the initial connection.
> 
> Using pgbouncer on the DB server is common, but less common that using
> it on an intermediate server or even the app server itself.  So anything
> we create needs to be implementable with all three configurations in
> some way.

I think the best solution to this would be to introduce a per-cluster
salt that is used for every password hash.  That way, you could not
replay a pg_authid hash on another server _unless_ you had manually
assigned the same cluster salt to both servers, or connection pooler.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Bruce Momjian (bruce@momjian.us) wrote:
> On Thu, Mar  5, 2015 at 11:15:55AM -0500, Stephen Frost wrote:
> > * Bruce Momjian (bruce@momjian.us) wrote:
> > > On Wed, Mar  4, 2015 at 05:56:25PM -0800, Josh Berkus wrote:
> > > > So, are we more worried about attackers getting a copy of pg_authid, or
> > > > sniffing the hash on the wire?
> > >
> > > Both.  Stephen is more worried about pg_authid, but I am more worried
> > > about sniffing.
> >
> > I'm also worried about both, but if the admin is worried about sniffing
> > in their environment, they're much more likely to use TLS than to set up
> > client side certificates, kerberos, or some other strong auth mechanism,
> > simply because TLS is pretty darn easy to get working and distros set it
> > up for you by default.
>
> I think your view might be skewed.  I think there many people who care
> about password security who don't care to do TLS.

I'm not quite sure that I follow what you mean about caring for
"password security".

I'll try to clarify by suggesting a few things that I think you might
mean and will respond to them.  Please clarify if I've completely missed
what you're getting at here.

If the concern is database access due to an attacker who can sniff the
network data then the approach which I suggested would make things
materially worse for users who do not employ TLS.  Once the attacker has
sniffed the network for a little while, they'll have one and likely more
challenge/responses which they could use to attempt to log in with.  As
discussed, our existing challenge/response system is vulnerable to
network sniffing based replay attacks also.

If the concern is database access due to an attacker who can see the
on-disk data, then the current situation makes it trivial for the
attacker to log in, while the approach I've suggested would require the
attacker to reverse hash(salt+auth_token) (where auth_token here is
taken to represent what we currently store on disk; even with my
suggestion, the attacker would not need to reverse the
hash(username+password) to gain database access).

If the concern is about getting at the cleartext password, then I don't
believe things are materially worse with either approach assuming a
network-based sniff attack.  Both require that the attacker reverse
hash(salt+hash(username+password)) where the salt and password are not
known.

If the concern is about getting the cleartext password as it resides on
disk or in backups, we are not in a good position today.  While the
password is hash'd, the "salt" used is the username which the attacker
may know ahead of the compromise.  The approach I am suggesting improves
that situation because it would bring it up to the same level of
difficulty as that of the network-based sniff attack: the attacker would
have to reverse hash(salt+hash(username+password)).

> Also, my suggestion to use a counter for the session salt, to reduce
> replay from 16k to 4 billion, has not received any comments, and it does
> not break the wire protocol.  I feel that is an incremental improvement
> we should consider.

You are correct, that would improve the existing protocol regarding
database-access risk due to network-based sniffing attacks.
Unfortunately, it would not improve cleartext or database access
risk due to disk-based attacks.

> I think you are minimizing the downsize of your idea using X challenges
> instead of 16k challenges to get in.  Again, if my idea is valid, it
> would be X challenges vs 4 billion challenges.

The reason I have not been as excited by this approach is that we
already have a solution for network-based sniffing attacks.  As Josh
mentioned, there are users out there who even go to extraordinary
lengths to thwart network-based sniffing attacks by using stunnel with
pg_bouncer.  On the flip side, while there are ways to protect backups
through encryption, many other vectors exist for disk-based attacks
which result in either database access or finding the cleartext
password with much less difficulty.

Further, this only improves the authentication handling and doesn't
improve our risk to other network-based attacks, including connection
hijacking, sniffing during password set/reset, data compromise as it's
sent across the wire, etc.  Encouraging use of TLS addresses all of
those risks.  I don't recall any complaints about these other
network-based attacks and I do believe that's because TLS is available.
Combined with the approach I've suggested, we would reduce the risk of
disk-based attacks to the extent we're able to without breaking the
protocol.

For my part, doing this, or going with my suggestion, or doing nothing
with md5, really doesn't move us forward very much, which frustrates me
greatly.  I brought this suggestion to this list because it was
suggested to me as one change we could make that would reduce the risk
of disk-based attacks while trading that off for a higher risk on the
side of network-based attacks while not breaking the existing network
protocol.  To make it very clear- it is not a solution but rather a poor
bandaid.  What we really need is a new password based protocol which is
based on a future-proof, well designed protocol, such as SCRAM.
Thanks,
    Stephen

* Bruce Momjian (bruce@momjian.us) wrote:
> On Fri, Mar  6, 2015 at 12:50:14PM -0800, Josh Berkus wrote:
> > On 03/06/2015 08:19 AM, Stephen Frost wrote:
> > > Well, server-side, we already have that- have pgbouncer run on the
> > > database server (something which I'm typically in favor of anyway) and
> > > use 'peer'.  If it supported TLS then it could use certificates instead.
> > > The question is what to do after the pooler has connected and that's
> > > actually a generic issue which goes beyond poolers and into
> > > applications, basically, "how can I re-authenticate this connection
> > > using a different role."  We have SET ROLE, but that gives a lot of
> > > power to the role the pooler logs in as.  It'd definitely be neat to
> > > provide a way to use SCRAM or similar to do that re-authentication after
> > > the initial connection.
> >
> > Using pgbouncer on the DB server is common, but less common that using
> > it on an intermediate server or even the app server itself.  So anything
> > we create needs to be implementable with all three configurations in
> > some way.
>
> I think the best solution to this would be to introduce a per-cluster
> salt that is used for every password hash.  That way, you could not
> replay a pg_authid hash on another server _unless_ you had manually
> assigned the same cluster salt to both servers, or connection pooler.

Wouldn't that break the wireline protocol, unless you used a fixed set
of known challenges?  Perhaps I'm not following what you mean by a
cluster-wide salt here.
Thanks,
    Stephen

On Fri, Mar  6, 2015 at 07:02:36PM -0500, Stephen Frost wrote:
> * Bruce Momjian (bruce@momjian.us) wrote:
> > On Fri, Mar  6, 2015 at 12:50:14PM -0800, Josh Berkus wrote:
> > > On 03/06/2015 08:19 AM, Stephen Frost wrote:
> > > > Well, server-side, we already have that- have pgbouncer run on the
> > > > database server (something which I'm typically in favor of anyway) and
> > > > use 'peer'.  If it supported TLS then it could use certificates instead.
> > > > The question is what to do after the pooler has connected and that's
> > > > actually a generic issue which goes beyond poolers and into
> > > > applications, basically, "how can I re-authenticate this connection
> > > > using a different role."  We have SET ROLE, but that gives a lot of
> > > > power to the role the pooler logs in as.  It'd definitely be neat to
> > > > provide a way to use SCRAM or similar to do that re-authentication after
> > > > the initial connection.
> > > 
> > > Using pgbouncer on the DB server is common, but less common that using
> > > it on an intermediate server or even the app server itself.  So anything
> > > we create needs to be implementable with all three configurations in
> > > some way.
> > 
> > I think the best solution to this would be to introduce a per-cluster
> > salt that is used for every password hash.  That way, you could not
> > replay a pg_authid hash on another server _unless_ you had manually
> > assigned the same cluster salt to both servers, or connection pooler.
> 
> Wouldn't that break the wireline protocol, unless you used a fixed set
> of known challenges?  Perhaps I'm not following what you mean by a
> cluster-wide salt here.

Well, right now the server sends a random 32-bit number as session salt,
but due to the birthday problem, that can repeat in ~16k connection
attempts.  If we use an incremented counter for each session, we spread
the salt evenly over the entire 32-bit key space, making replays much
more difficult, e.g. 4 billion.

I don't think the client would ever know the number was different from 
the random number we used to send.

The big win for this idea is that it requires no client or admin
changes, while your idea of using a new salt does.  My personal opinion
is that the 32-bit counter idea improves MD5 replays, and that we are
better off going with an entirely new authentication method to fix the
pg_authid vulnerability.

I think your argument is that if users are using TLS, there is no replay
problem and you want to focus on the pg_authid problem.  I think fixing
the pg_authid problem inside MD5 is just too complex and we are better
off creating a new authentication method for that.  

The bottom line is we promised MD5 to prevent replay, but not pg_authid
stealing, and if we can improve on what we promised, we should do that
and not hijack MD5 to fix a different problem, particularly because
fixing MD5 for pg_authid requires admin action.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

On Fri, Mar  6, 2015 at 07:00:10PM -0500, Stephen Frost wrote:
> > > I'm also worried about both, but if the admin is worried about sniffing
> > > in their environment, they're much more likely to use TLS than to set up
> > > client side certificates, kerberos, or some other strong auth mechanism,
> > > simply because TLS is pretty darn easy to get working and distros set it
> > > up for you by default.
> > 
> > I think your view might be skewed.  I think there many people who care
> > about password security who don't care to do TLS.
> 
> I'm not quite sure that I follow what you mean about caring for
> "password security".
> 
> I'll try to clarify by suggesting a few things that I think you might
> mean and will respond to them.  Please clarify if I've completely missed
> what you're getting at here.
> 
> If the concern is database access due to an attacker who can sniff the
> network data then the approach which I suggested would make things
> materially worse for users who do not employ TLS.  Once the attacker has
> sniffed the network for a little while, they'll have one and likely more
> challenge/responses which they could use to attempt to log in with.  As
> discussed, our existing challenge/response system is vulnerable to
> network sniffing based replay attacks also.

Yes, I am worried about that attack vector.  We have always been open
that MD5 only prevents password sniffing, though the 16k reply idea has
put a dent into that promise.

See the email I just sent on how I think we should proceed, i.e. by
creating a new authentication method to fix pg_authid stealing, and use
a salt counter to improve MD5.

> > Also, my suggestion to use a counter for the session salt, to reduce
> > replay from 16k to 4 billion, has not received any comments, and it does
> > not break the wire protocol.  I feel that is an incremental improvement
> > we should consider.
> 
> You are correct, that would improve the existing protocol regarding
> database-access risk due to network-based sniffing attacks.
> Unfortunately, it would not improve cleartext or database access
> risk due to disk-based attacks.

Agreed.

> 
> > I think you are minimizing the downsize of your idea using X challenges
> > instead of 16k challenges to get in.  Again, if my idea is valid, it
> > would be X challenges vs 4 billion challenges.
> 
> The reason I have not been as excited by this approach is that we
> already have a solution for network-based sniffing attacks.  As Josh
> mentioned, there are users out there who even go to extraordinary
> lengths to thwart network-based sniffing attacks by using stunnel with
> pg_bouncer.  On the flip side, while there are ways to protect backups
> through encryption, many other vectors exist for disk-based attacks
> which result in either database access or finding the cleartext
> password with much less difficulty.
> 
> Further, this only improves the authentication handling and doesn't
> improve our risk to other network-based attacks, including connection
> hijacking, sniffing during password set/reset, data compromise as it's
> sent across the wire, etc.  Encouraging use of TLS addresses all of
> those risks.  I don't recall any complaints about these other
> network-based attacks and I do believe that's because TLS is available.
> Combined with the approach I've suggested, we would reduce the risk of
> disk-based attacks to the extent we're able to without breaking the
> protocol.

Agreed.  Again, TLS has its own value beyond simple authentication.  I
just don't think getting MD5 to try to fix the pg_authid problem is the
right approach.

> For my part, doing this, or going with my suggestion, or doing nothing
> with md5, really doesn't move us forward very much, which frustrates me
> greatly.  I brought this suggestion to this list because it was

Agreed.

> suggested to me as one change we could make that would reduce the risk
> of disk-based attacks while trading that off for a higher risk on the
> side of network-based attacks while not breaking the existing network
> protocol.  To make it very clear- it is not a solution but rather a poor
> bandaid.  What we really need is a new password based protocol which is
> based on a future-proof, well designed protocol, such as SCRAM.

Again, agreed.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Bruce Momjian (bruce@momjian.us) wrote:
> On Fri, Mar  6, 2015 at 07:02:36PM -0500, Stephen Frost wrote:
> > * Bruce Momjian (bruce@momjian.us) wrote:
> > > I think the best solution to this would be to introduce a per-cluster
> > > salt that is used for every password hash.  That way, you could not
> > > replay a pg_authid hash on another server _unless_ you had manually
> > > assigned the same cluster salt to both servers, or connection pooler.
> >
> > Wouldn't that break the wireline protocol, unless you used a fixed set
> > of known challenges?  Perhaps I'm not following what you mean by a
> > cluster-wide salt here.
>
> Well, right now the server sends a random 32-bit number as session salt,
> but due to the birthday problem, that can repeat in ~16k connection
> attempts.  If we use an incremented counter for each session, we spread
> the salt evenly over the entire 32-bit key space, making replays much
> more difficult, e.g. 4 billion.

Ok, this is the incremented counter approach you brought up previously.
Using the term 'cluster-wide salt' confused me as I thought you were
referring to changing the on-disk format somehow with this.

> I don't think the client would ever know the number was different from
> the random number we used to send.

Agreed.

> The big win for this idea is that it requires no client or admin
> changes, while your idea of using a new salt does.  My personal opinion
> is that the 32-bit counter idea improves MD5 replays, and that we are
> better off going with an entirely new authentication method to fix the
> pg_authid vulnerability.

There's apparently some confusion here as my approach does not require
any client or admin changes either.  If users are not using TLS today
then they will be slightly more susceptible to network-based sniffing
attacks than they are today due to the replay issue, but they are
already at risk to a variety of other (arguably worse) attacks in that
case.  Further, we can at least tell users about those risks and provide
a way to address them.

> I think your argument is that if users are using TLS, there is no replay
> problem and you want to focus on the pg_authid problem.  I think fixing
> the pg_authid problem inside MD5 is just too complex and we are better
> off creating a new authentication method for that.

There is no replay problem if users are using TLS, that's correct.  I
don't believe the approach I've outlined is particularly complex, but
that's clearly a biased viewpoint.

I certainly agree that we need to create a new authentication method to
address these issues properly and would love to discuss that further
rather than discuss the merits of these potential improvements to md5.

> The bottom line is we promised MD5 to prevent replay, but not pg_authid
> stealing, and if we can improve on what we promised, we should do that
> and not hijack MD5 to fix a different problem, particularly because
> fixing MD5 for pg_authid requires admin action.

Perhaps I'm missing it, but the documentation in 19.3.2 for 9.4 mentions
md5 being useful to address password "sniffing" risk but doesn't
mention anything about replay or the pg_authid-based risk.  Sniffing of
the cleartext password is addressed with the approach I've outlined, but
the replay risk is greater.

Further, we can provide a solution to the replay concern by encouraging
use of SSL/TLS.  We can not provide any solution to the pg_authid-based
risk with this approach (with the possible exception of recommending
password-based auth, though the poor salt used makes that less
effective than md5 with the suggestion I've outlined).

The incremental counter approach implies not using the approach I've
outlined, which is fine, but it doesn't change the pg_authid risk, nor
does it help at all for TLS-using environments, and for users who are
not using TLS, it doesn't make them particularly more secure to
cleartext-password loss, connection hijacking, data loss, or anything
except replay attacks.  When it comes to risks, for my part at least, I
don't feel like the replay risk is the largest concern to an operator
who is not using TLS.
Thanks,
    Stephen

* Bruce Momjian (bruce@momjian.us) wrote:
> On Fri, Mar  6, 2015 at 07:00:10PM -0500, Stephen Frost wrote:
> > suggested to me as one change we could make that would reduce the risk
> > of disk-based attacks while trading that off for a higher risk on the
> > side of network-based attacks while not breaking the existing network
> > protocol.  To make it very clear- it is not a solution but rather a poor
> > bandaid.  What we really need is a new password based protocol which is
> > based on a future-proof, well designed protocol, such as SCRAM.
>
> Again, agreed.

Great.

Have you had a chance to review the SCRAM RFC or do you have any
questions as it relates to how SCRAM works?  I'd love to start a proper
discussion about how we go about implementing it.
Thanks!
    Stephen

On Sat, Mar  7, 2015 at 12:52:15PM -0500, Stephen Frost wrote:
> * Bruce Momjian (bruce@momjian.us) wrote:
> > On Fri, Mar  6, 2015 at 07:00:10PM -0500, Stephen Frost wrote:
> > > suggested to me as one change we could make that would reduce the risk
> > > of disk-based attacks while trading that off for a higher risk on the
> > > side of network-based attacks while not breaking the existing network
> > > protocol.  To make it very clear- it is not a solution but rather a poor
> > > bandaid.  What we really need is a new password based protocol which is
> > > based on a future-proof, well designed protocol, such as SCRAM.
> > 
> > Again, agreed.
> 
> Great.
> 
> Have you had a chance to review the SCRAM RFC or do you have any
> questions as it relates to how SCRAM works?  I'd love to start a proper
> discussion about how we go about implementing it.

I am feeling we have to wait for 9.5 to settle first.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

On Sat, Mar  7, 2015 at 12:49:15PM -0500, Stephen Frost wrote:
> * Bruce Momjian (bruce@momjian.us) wrote:
> > On Fri, Mar  6, 2015 at 07:02:36PM -0500, Stephen Frost wrote:
> > > * Bruce Momjian (bruce@momjian.us) wrote:
> > > > I think the best solution to this would be to introduce a per-cluster
> > > > salt that is used for every password hash.  That way, you could not
> > > > replay a pg_authid hash on another server _unless_ you had manually
> > > > assigned the same cluster salt to both servers, or connection pooler.
> > > 
> > > Wouldn't that break the wireline protocol, unless you used a fixed set
> > > of known challenges?  Perhaps I'm not following what you mean by a
> > > cluster-wide salt here.
> > 
> > Well, right now the server sends a random 32-bit number as session salt,
> > but due to the birthday problem, that can repeat in ~16k connection
> > attempts.  If we use an incremented counter for each session, we spread
> > the salt evenly over the entire 32-bit key space, making replays much
> > more difficult, e.g. 4 billion.
> 
> Ok, this is the incremented counter approach you brought up previously.
> Using the term 'cluster-wide salt' confused me as I thought you were
> referring to changing the on-disk format somehow with this.

Yes, I used the term cluster-wide salt in two cases:  first,
cluster-wide counter for the MD5 session salt improvement, and second,
cluster-wide fixed salt to prevent pg_authid reuse, but to allow reuse
if the cluster-wide fixed salt was set to match on two clusters, e.g.
for pooling.

> > I don't think the client would ever know the number was different from 
> > the random number we used to send.
> 
> Agreed.
> 
> > The big win for this idea is that it requires no client or admin
> > changes, while your idea of using a new salt does.  My personal opinion
> > is that the 32-bit counter idea improves MD5 replays, and that we are
> > better off going with an entirely new authentication method to fix the
> > pg_authid vulnerability.
> 
> There's apparently some confusion here as my approach does not require
> any client or admin changes either.  If users are not using TLS today

Really?  From your previous email I see:

> this approach looks like this: pre-determine and store the values (on a
> per-user basis, so a new field in pg_authid or some hack on the existing
> field) which will be sent to the client in the AuthenticationMD5Password
> message.  Further, calculate a random salt to be used when storing data
> in pg_authid.  Then, for however many variations we feel are necessary,
> calculate and store, for each AuthenticationMD5Password value:

How do you generate these X versions of password hashes without admin
changes?  In fact, I am not even sure how the server would create these
unless it had the raw passwords.

> then they will be slightly more susceptible to network-based sniffing

Slightly?  X versions as stored in pg_authid vs 16k or 4 billion?

> attacks than they are today due to the replay issue, but they are
> already at risk to a variety of other (arguably worse) attacks in that
> case.  Further, we can at least tell users about those risks and provide
> a way to address them.

Right, but again, the user can choose to use TLS if they wish.  I think
you are saying MD5 replay security is worthless without TLS, but I can
assure you many users are happy with that.  The fact this issue rarely
comes up is a testament to that, and in fact, until we documented
exactly how MD5 worked, we got many more questions about MD5.  Perhaps
we should document the pg_authid reuse risk.

> > I think your argument is that if users are using TLS, there is no replay
> > problem and you want to focus on the pg_authid problem.  I think fixing
> > the pg_authid problem inside MD5 is just too complex and we are better
> > off creating a new authentication method for that.  
> 
> There is no replay problem if users are using TLS, that's correct.  I
> don't believe the approach I've outlined is particularly complex, but
> that's clearly a biased viewpoint.
> 
> I certainly agree that we need to create a new authentication method to
> address these issues properly and would love to discuss that further
> rather than discuss the merits of these potential improvements to md5.
> 
> > The bottom line is we promised MD5 to prevent replay, but not pg_authid
> > stealing, and if we can improve on what we promised, we should do that
> > and not hijack MD5 to fix a different problem, particularly because
> > fixing MD5 for pg_authid requires admin action.
> 
> Perhaps I'm missing it, but the documentation in 19.3.2 for 9.4 mentions
> md5 being useful to address password "sniffing" risk but doesn't
> mention anything about replay or the pg_authid-based risk.  Sniffing of
> the cleartext password is addressed with the approach I've outlined, but
> the replay risk is greater.

I assumed sniffing meant sniff to later replay, which is why we use the
random session salt.  We document how it works so users can decide.

> Further, we can provide a solution to the replay concern by encouraging
> use of SSL/TLS.  We can not provide any solution to the pg_authid-based
> risk with this approach (with the possible exception of recommending
> password-based auth, though the poor salt used makes that less
> effective than md5 with the suggestion I've outlined).
> 
> The incremental counter approach implies not using the approach I've
> outlined, which is fine, but it doesn't change the pg_authid risk, nor
> does it help at all for TLS-using environments, and for users who are
> not using TLS, it doesn't make them particularly more secure to
> cleartext-password loss, connection hijacking, data loss, or anything
> except replay attacks.  When it comes to risks, for my part at least, I
> don't feel like the replay risk is the largest concern to an operator
> who is not using TLS.

Well, users have a tool kit of options and they can choose what they
want.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Bruce Momjian (bruce@momjian.us) wrote:
> On Sat, Mar  7, 2015 at 12:49:15PM -0500, Stephen Frost wrote:
> > Ok, this is the incremented counter approach you brought up previously.
> > Using the term 'cluster-wide salt' confused me as I thought you were
> > referring to changing the on-disk format somehow with this.
>
> Yes, I used the term cluster-wide salt in two cases:  first,
> cluster-wide counter for the MD5 session salt improvement, and second,
> cluster-wide fixed salt to prevent pg_authid reuse, but to allow reuse
> if the cluster-wide fixed salt was set to match on two clusters, e.g.
> for pooling.

Ok, how, in the second case, is pg_authid reuse prevented unless we also
change the on-disk pg_authid format?  It doesn't matter if there's a
different counter used between different clusters, if the attacker has
what's in pg_authid then they can trivially add any salt we send them
during the challenge/response to the pg_authid value and send us the
response we expect.

> > > The big win for this idea is that it requires no client or admin
> > > changes, while your idea of using a new salt does.  My personal opinion
> > > is that the 32-bit counter idea improves MD5 replays, and that we are
> > > better off going with an entirely new authentication method to fix the
> > > pg_authid vulnerability.
> >
> > There's apparently some confusion here as my approach does not require
> > any client or admin changes either.  If users are not using TLS today
>
> Really?  From your previous email I see:
>
> > this approach looks like this: pre-determine and store the values (on a
> > per-user basis, so a new field in pg_authid or some hack on the existing
> > field) which will be sent to the client in the AuthenticationMD5Password
> > message.  Further, calculate a random salt to be used when storing data
> > in pg_authid.  Then, for however many variations we feel are necessary,
> > calculate and store, for each AuthenticationMD5Password value:
>
> How do you generate these X versions of password hashes without admin
> changes?  In fact, I am not even sure how the server would create these
> unless it had the raw passwords.

Ok, I've apparently not been clear enough with the proposal.  What we
are hashing is the *current value* of what's in pg_authid- which we've
already got on disk.  All we have to do is read the current on-disk
value, add a salt to it, and store it back on disk.  We'd want to store
more than one, as discussed, since otherwise the challenge/response is
utterly useless.

> > then they will be slightly more susceptible to network-based sniffing
>
> Slightly?  X versions as stored in pg_authid vs 16k or 4 billion?

Sadly, yes.  It's not a perfect test, but a simple:

time for a in `seq 1 1000`; do nc localhost 5432 < /dev/null; done

Gave me 9.15s, or ~0.00915s per connection on a single thread.  That
times 16k is 146s or about two and a half minutes.  Of course, I'm
comparing this against what we currently do since, well, that's what we
currently do.  Changing it to 4b would certainly improve that.  Of
course, using multiple threads, having multiple challenge/responses on
hand (due to listening for a while) or simply breaking the MD5 hash
(which we know isn't a terribly great hashing algorithm these days)
would change that.

> > attacks than they are today due to the replay issue, but they are
> > already at risk to a variety of other (arguably worse) attacks in that
> > case.  Further, we can at least tell users about those risks and provide
> > a way to address them.
>
> Right, but again, the user can choose to use TLS if they wish.  I think
> you are saying MD5 replay security is worthless without TLS, but I can
> assure you many users are happy with that.  The fact this issue rarely
> comes up is a testament to that, and in fact, until we documented
> exactly how MD5 worked, we got many more questions about MD5.  Perhaps
> we should document the pg_authid reuse risk.

We should certainly document the pg_authid reuse risk.  For my part, I
don't think it's that people are happy with that trade-off but rather
that they simply don't realize the risk is there because, basically, who
would ever do that?  I'm not aware of any other server application which
even offers an option to store the authentication token out on disk in a
format which can be trivially used to authenticate to the system
(excluding people who are storing cleartext passwords..).

I do feel that people who are worried about MD5 replay security who are
*not* using TLS have not considered their risks properly.  It is unclear
to me why anyone should feel safe from an attacker who is able to sniff
the network traffic thanks to our challenge/response protocol.

> > Further, we can provide a solution to the replay concern by encouraging
> > use of SSL/TLS.  We can not provide any solution to the pg_authid-based
> > risk with this approach (with the possible exception of recommending
> > password-based auth, though the poor salt used makes that less
> > effective than md5 with the suggestion I've outlined).
> >
> > The incremental counter approach implies not using the approach I've
> > outlined, which is fine, but it doesn't change the pg_authid risk, nor
> > does it help at all for TLS-using environments, and for users who are
> > not using TLS, it doesn't make them particularly more secure to
> > cleartext-password loss, connection hijacking, data loss, or anything
> > except replay attacks.  When it comes to risks, for my part at least, I
> > don't feel like the replay risk is the largest concern to an operator
> > who is not using TLS.
>
> Well, users have a tool kit of options and they can choose what they
> want.

Can they?

How are they able to prevent an attacker who has gained access to
pg_authid from logging in?  What if the attacker gained access to the
replica or an unencrypted backup?  I agree that a user can, and should,
do their best to secure the pg_authid file, but there are good reasons
why cleartext password or authentication tokens shouldn't be stored on
disk directly.
Thanks,
    Stephen

On Sat, Mar  7, 2015 at 01:56:51PM -0500, Stephen Frost wrote:
> * Bruce Momjian (bruce@momjian.us) wrote:
> > On Sat, Mar  7, 2015 at 12:49:15PM -0500, Stephen Frost wrote:
> > > Ok, this is the incremented counter approach you brought up previously.
> > > Using the term 'cluster-wide salt' confused me as I thought you were
> > > referring to changing the on-disk format somehow with this.
> > 
> > Yes, I used the term cluster-wide salt in two cases:  first,
> > cluster-wide counter for the MD5 session salt improvement, and second,
> > cluster-wide fixed salt to prevent pg_authid reuse, but to allow reuse
> > if the cluster-wide fixed salt was set to match on two clusters, e.g.
> > for pooling.
> 
> Ok, how, in the second case, is pg_authid reuse prevented unless we also
> change the on-disk pg_authid format?  It doesn't matter if there's a

Yes, the second use would be a new authentication method.

> different counter used between different clusters, if the attacker has
> what's in pg_authid then they can trivially add any salt we send them
> during the challenge/response to the pg_authid value and send us the
> response we expect.

It would be a server-fixed salt sent to the client and applied before
the session salt.  The pg_authid value would also store with this salt. 
Again, I am brainstorming about poolers.

> > > > The big win for this idea is that it requires no client or admin
> > > > changes, while your idea of using a new salt does.  My personal opinion
> > > > is that the 32-bit counter idea improves MD5 replays, and that we are
> > > > better off going with an entirely new authentication method to fix the
> > > > pg_authid vulnerability.
> > > 
> > > There's apparently some confusion here as my approach does not require
> > > any client or admin changes either.  If users are not using TLS today
> > 
> > Really?  From your previous email I see:
> > 
> > > this approach looks like this: pre-determine and store the values (on a
> > > per-user basis, so a new field in pg_authid or some hack on the existing
> > > field) which will be sent to the client in the AuthenticationMD5Password
> > > message.  Further, calculate a random salt to be used when storing data
> > > in pg_authid.  Then, for however many variations we feel are necessary,
> > > calculate and store, for each AuthenticationMD5Password value:
> > 
> > How do you generate these X versions of password hashes without admin
> > changes?  In fact, I am not even sure how the server would create these
> > unless it had the raw passwords.
> 
> Ok, I've apparently not been clear enough with the proposal.  What we
> are hashing is the *current value* of what's in pg_authid- which we've
> already got on disk.  All we have to do is read the current on-disk
> value, add a salt to it, and store it back on disk.  We'd want to store
> more than one, as discussed, since otherwise the challenge/response is
> utterly useless.

Oh, that is very interesting.  It seems like you are basically applying
my server-fixed salt idea, except you are doing it X times so sniffing
and then replay is less of a problem.   Hmmm.  I am very glad there is
no admin work ---  I did not realize that.  It does make the trade-off
of your idea more appealing, though I still think it weakens MD5 in an
unacceptable way.

> > > then they will be slightly more susceptible to network-based sniffing
> > 
> > Slightly?  X versions as stored in pg_authid vs 16k or 4 billion?
> 
> Sadly, yes.  It's not a perfect test, but a simple:
> 
> time for a in `seq 1 1000`; do nc localhost 5432 < /dev/null; done
> 
> Gave me 9.15s, or ~0.00915s per connection on a single thread.  That
> times 16k is 146s or about two and a half minutes.  Of course, I'm
> comparing this against what we currently do since, well, that's what we
> currently do.  Changing it to 4b would certainly improve that.  Of
> course, using multiple threads, having multiple challenge/responses on
> hand (due to listening for a while) or simply breaking the MD5 hash
> (which we know isn't a terribly great hashing algorithm these days)
> would change that.

Uh, my calculations show that as 434 days of trying.  (Not sure why you
didn't bother doing that calculation.)  I think anyone who is worried
about that level of attack would already be using MD5.  Again, MD5 is
mostly used in low-security settings where you just don't want the
password sent over the wire in cleartext.  Frankly, without TLS, you are
already sending your queries and data across in clear-text, and there
are other attack vectors.

> > > attacks than they are today due to the replay issue, but they are
> > > already at risk to a variety of other (arguably worse) attacks in that
> > > case.  Further, we can at least tell users about those risks and provide
> > > a way to address them.
> > 
> > Right, but again, the user can choose to use TLS if they wish.  I think
> > you are saying MD5 replay security is worthless without TLS, but I can
> > assure you many users are happy with that.  The fact this issue rarely
> > comes up is a testament to that, and in fact, until we documented
> > exactly how MD5 worked, we got many more questions about MD5.  Perhaps
> > we should document the pg_authid reuse risk.
> 
> We should certainly document the pg_authid reuse risk.  For my part, I
> don't think it's that people are happy with that trade-off but rather
> that they simply don't realize the risk is there because, basically, who
> would ever do that?  I'm not aware of any other server application which
> even offers an option to store the authentication token out on disk in a
> format which can be trivially used to authenticate to the system
> (excluding people who are storing cleartext passwords..).

Yes, good point.

> I do feel that people who are worried about MD5 replay security who are
> *not* using TLS have not considered their risks properly.  It is unclear
> to me why anyone should feel safe from an attacker who is able to sniff
> the network traffic thanks to our challenge/response protocol.
> 
> > > Further, we can provide a solution to the replay concern by encouraging
> > > use of SSL/TLS.  We can not provide any solution to the pg_authid-based
> > > risk with this approach (with the possible exception of recommending
> > > password-based auth, though the poor salt used makes that less
> > > effective than md5 with the suggestion I've outlined).
> > > 
> > > The incremental counter approach implies not using the approach I've
> > > outlined, which is fine, but it doesn't change the pg_authid risk, nor
> > > does it help at all for TLS-using environments, and for users who are
> > > not using TLS, it doesn't make them particularly more secure to
> > > cleartext-password loss, connection hijacking, data loss, or anything
> > > except replay attacks.  When it comes to risks, for my part at least, I
> > > don't feel like the replay risk is the largest concern to an operator
> > > who is not using TLS.
> > 
> > Well, users have a tool kit of options and they can choose what they
> > want.
> 
> Can they?
> 
> How are they able to prevent an attacker who has gained access to
> pg_authid from logging in?  What if the attacker gained access to the
> replica or an unencrypted backup?  I agree that a user can, and should,
> do their best to secure the pg_authid file, but there are good reasons
> why cleartext password or authentication tokens shouldn't be stored on
> disk directly.

Fine, but causing MD5 to be less secure doesn't warrant fixing it this
way.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Bruce Momjian (bruce@momjian.us) wrote:
> On Sat, Mar  7, 2015 at 01:56:51PM -0500, Stephen Frost wrote:
> > * Bruce Momjian (bruce@momjian.us) wrote:
> > > Yes, I used the term cluster-wide salt in two cases:  first,
> > > cluster-wide counter for the MD5 session salt improvement, and second,
> > > cluster-wide fixed salt to prevent pg_authid reuse, but to allow reuse
> > > if the cluster-wide fixed salt was set to match on two clusters, e.g.
> > > for pooling.
> >
> > Ok, how, in the second case, is pg_authid reuse prevented unless we also
> > change the on-disk pg_authid format?  It doesn't matter if there's a
>
> Yes, the second use would be a new authentication method.

Ok..  I don't think it's a good idea to try and base a new auth method
on what we're doing for md5, in any case.  To the extent that we have
options as it relates to SCRAM or another reviewed authentication
protocol, perhaps it'd make sense to consider a per-cluster salt or
similar, but I'm not sure we actually want or need to do so.

> > different counter used between different clusters, if the attacker has
> > what's in pg_authid then they can trivially add any salt we send them
> > during the challenge/response to the pg_authid value and send us the
> > response we expect.
>
> It would be a server-fixed salt sent to the client and applied before
> the session salt.  The pg_authid value would also store with this salt.
> Again, I am brainstorming about poolers.

When it comes to poolers, I'm thinking we should be looking at an
approach to do an after-connection re-authentication.  Essentially a
'SET ROLE WITH mypassword;' kind of approach, but also using a proper
protocol, etc.  That way, the pooler wouldn't really need to worry about
the actual authentication of the user.  This is also brainstorming, of
course, I don't have a fully formed idea about how this would work, but
I do know that some other RDBMS's offer a similar masquerade kind of
ability.

> > > How do you generate these X versions of password hashes without admin
> > > changes?  In fact, I am not even sure how the server would create these
> > > unless it had the raw passwords.
> >
> > Ok, I've apparently not been clear enough with the proposal.  What we
> > are hashing is the *current value* of what's in pg_authid- which we've
> > already got on disk.  All we have to do is read the current on-disk
> > value, add a salt to it, and store it back on disk.  We'd want to store
> > more than one, as discussed, since otherwise the challenge/response is
> > utterly useless.
>
> Oh, that is very interesting.  It seems like you are basically applying
> my server-fixed salt idea, except you are doing it X times so sniffing
> and then replay is less of a problem.   Hmmm.  I am very glad there is
> no admin work ---  I did not realize that.  It does make the trade-off
> of your idea more appealing, though I still think it weakens MD5 in an
> unacceptable way.

Well, that's where I come down on the side of "our existing MD5 approach
is pretty darn weak wrt replay".  I agree, we can fix that, but I was
comparing to what our MD5 approach currently provides.

> > > > then they will be slightly more susceptible to network-based sniffing
> > >
> > > Slightly?  X versions as stored in pg_authid vs 16k or 4 billion?
> >
> > Sadly, yes.  It's not a perfect test, but a simple:
> >
> > time for a in `seq 1 1000`; do nc localhost 5432 < /dev/null; done
> >
> > Gave me 9.15s, or ~0.00915s per connection on a single thread.  That
> > times 16k is 146s or about two and a half minutes.  Of course, I'm
> > comparing this against what we currently do since, well, that's what we
> > currently do.  Changing it to 4b would certainly improve that.  Of
> > course, using multiple threads, having multiple challenge/responses on
> > hand (due to listening for a while) or simply breaking the MD5 hash
> > (which we know isn't a terribly great hashing algorithm these days)
> > would change that.
>
> Uh, my calculations show that as 434 days of trying.  (Not sure why you
> didn't bother doing that calculation.)

I did.  I guess it wasn't clear but I was pointing out the difference
between my suggestion and the *current* state of things, where we have
the birthday problem.

> I think anyone who is worried
> about that level of attack would already be using MD5.  Again, MD5 is
> mostly used in low-security settings where you just don't want the
> password sent over the wire in cleartext.  Frankly, without TLS, you are
> already sending your queries and data across in clear-text, and there
> are other attack vectors.

This suggestion does not send the cleartext password over the wire.

> Fine, but causing MD5 to be less secure doesn't warrant fixing it this
> way.

What I was getting at is that it's not much less secure than our current
MD5 implementation when it comes to replay attacks.  Improving MD5 to be
more robust against replay attacks would be good, except that it doesn't
address the pg_authid-based risk.  I wish there was a solution which
allowed us to have both but I don't see one, without a wireline protocol
change.

I'm really not wedded to my suggestion (which isn't even mine, as I
tried to get at earlier- it's one approach which was suggested by
someone from Openwall) and I agree that simply changing the way we
create the salt on the server side would greatly improve our MD5
implementation against replay attacks.

I think we both have a better idea of the solutions being discussed and
what the trade-offs are.  I do feel that it'd be better to change MD5
and encourage TLS use than to improve on MD5 as is, but I can certainly
understand your viewpoint that it makes replay worse and therefore
doesn't address the concern for which the challenge/response was
implemented originally.

I guess I'm not quite sure where to go from here except to hope that
someone has a chance to work on a new authentication method soon.
Thanks,
    Stephen

On Sat, Mar  7, 2015 at 03:15:46PM -0500, Bruce Momjian wrote:
> > Gave me 9.15s, or ~0.00915s per connection on a single thread.  That
> > times 16k is 146s or about two and a half minutes.  Of course, I'm
> > comparing this against what we currently do since, well, that's what we
> > currently do.  Changing it to 4b would certainly improve that.  Of
> > course, using multiple threads, having multiple challenge/responses on
> > hand (due to listening for a while) or simply breaking the MD5 hash
> > (which we know isn't a terribly great hashing algorithm these days)
> > would change that.
> 
> Uh, my calculations show that as 434 days of trying.  (Not sure why you
> didn't bother doing that calculation.)  I think anyone who is worried
> about that level of attack would already be using MD5.  Again, MD5 is
> mostly used in low-security settings where you just don't want the
> password sent over the wire in cleartext.  Frankly, without TLS, you are
> already sending your queries and data across in clear-text, and there
> are other attack vectors.

Actually, with a counter, the bad guy just has to wait for the counter
to roll around, and then try to catch the counter on the values he has
recorded, meaning you wouldn't even be able to detect the hack attempts.
:-)

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + Everyone has their own god. +

* Bruce Momjian (bruce@momjian.us) wrote:
> On Sat, Mar  7, 2015 at 03:15:46PM -0500, Bruce Momjian wrote:
> > > Gave me 9.15s, or ~0.00915s per connection on a single thread.  That
> > > times 16k is 146s or about two and a half minutes.  Of course, I'm
> > > comparing this against what we currently do since, well, that's what we
> > > currently do.  Changing it to 4b would certainly improve that.  Of
> > > course, using multiple threads, having multiple challenge/responses on
> > > hand (due to listening for a while) or simply breaking the MD5 hash
> > > (which we know isn't a terribly great hashing algorithm these days)
> > > would change that.
> >
> > Uh, my calculations show that as 434 days of trying.  (Not sure why you
> > didn't bother doing that calculation.)  I think anyone who is worried
> > about that level of attack would already be using MD5.  Again, MD5 is
> > mostly used in low-security settings where you just don't want the
> > password sent over the wire in cleartext.  Frankly, without TLS, you are
> > already sending your queries and data across in clear-text, and there
> > are other attack vectors.
>
> Actually, with a counter, the bad guy just has to wait for the counter
> to roll around, and then try to catch the counter on the values he has
> recorded, meaning you wouldn't even be able to detect the hack attempts.
> :-)

That's true, if the counter is at an individual-level.  If it's cluster
wide then they aren't very likely to have the same counter for the same
individual after the wrap-around.  Then again, what individual is going
to be logging in 4 billion times?  There's a number of trade-offs here,
which is why we'd really be better off using an approach which security
folks have already vetted.
Thanks!
    Stephen

All,

Since SCRAM has been brought up a number of times here, I thought I'd
loop in the PostgreSQL contributor who is co-author of the SCRAM
standard to see if he has anything to say about implementing SCRAM as a
built-in auth method for Postgres.

Abhijit?

-- 
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

At 2015-03-08 12:48:44 -0700, josh@agliodbs.com wrote:
>
> Since SCRAM has been brought up a number of times here, I thought
> I'd loop in the PostgreSQL contributor who is co-author of the SCRAM
> standard to see if he has anything to say about implementing SCRAM as
> a built-in auth method for Postgres.

I think it's a good idea.

-- Abhijit

Hi Abhijit, I didn't realize you were involved in the IETF process on 
SCRAM :-).

On 03/09/2015 09:21 AM, Abhijit Menon-Sen wrote:
> At 2015-03-08 12:48:44 -0700, josh@agliodbs.com wrote:
>>
>> Since SCRAM has been brought up a number of times here, I thought
>> I'd loop in the PostgreSQL contributor who is co-author of the SCRAM
>> standard to see if he has anything to say about implementing SCRAM as
>> a built-in auth method for Postgres.
>
> I think it's a good idea.

Having done some googling, SCRAM seems like a good choice to me too. 
Another one is SRP. The important difference between SRP and SCRAM is 
that in SRP, an eavesdropper cannot capture information needed to 
brute-force the password. The class of protocols that have that property 
are called Password-authenticated key agreement protocols (PAKE) [1]. 
SRP seems to be the most common one of those, although there are others.

On the face of it, it seems like PAKE protocols are superior. There is 
an IETF draft for SRP as a SASL authentication mechanism [2], and even 
some implementations of that (e.g. Cyrus-SASL), but for some reason that 
draft never became a standard and expired. Do you have any insight on 
why the IETF working group didn't choose a PAKE protocol instead of or 
in addition to SCRAM, when SCRAM was standardized?

[1] https://en.wikipedia.org/wiki/Password-authenticated_key_agreement
[2] https://tools.ietf.org/html/draft-burdis-cat-srp-sasl-08

- Heikki

At 2015-03-09 13:52:10 +0200, hlinnaka@iki.fi wrote:
>
> Do you have any insight on why the IETF working group didn't choose a
> PAKE protocol instead of or in addition to SCRAM, when SCRAM was
> standardized?

Hi Heikki.

It was a long time ago, but I recall that SRP was patent-encumbered:

https://datatracker.ietf.org/ipr/search/?rfc=2945&submit=rfc

The Wikipedia page says the relevant patents expired in 2011 and 2013.
I haven't followed SRP development since then, maybe it's been revised.

When SCRAM was being discussed, I can't recall any other proposals for
PAKE protocols. Besides, as you may already know, anyone can submit an
internet-draft about anything. It needs to gain general support for an
extended period in order to advance through the standards process.

Could you please explain what exactly you mean about a SCRAM
eavesdropper gaining some advantage in being able to mount a
dictionary attack? I didn't follow that part.

-- Abhijit

On 03/09/2015 04:43 PM, Abhijit Menon-Sen wrote:
> At 2015-03-09 13:52:10 +0200, hlinnaka@iki.fi wrote:
>>
>> Do you have any insight on why the IETF working group didn't choose a
>> PAKE protocol instead of or in addition to SCRAM, when SCRAM was
>> standardized?
>
> Hi Heikki.
>
> It was a long time ago, but I recall that SRP was patent-encumbered:
>
> https://datatracker.ietf.org/ipr/search/?rfc=2945&submit=rfc
>
> The Wikipedia page says the relevant patents expired in 2011 and 2013.
> I haven't followed SRP development since then, maybe it's been revised.
>
> When SCRAM was being discussed, I can't recall any other proposals for
> PAKE protocols. Besides, as you may already know, anyone can submit an
> internet-draft about anything. It needs to gain general support for an
> extended period in order to advance through the standards process.

Ok, makes sense. Perhaps it would be time to restart the discussion on 
standardizing SRP as a SASL mechanism in IETF. Or we could just 
implement the draft as it is.

> Could you please explain what exactly you mean about a SCRAM
> eavesdropper gaining some advantage in being able to mount a
> dictionary attack? I didn't follow that part.

Assume that the connection is not encrypted, and Eve captures the SCRAM 
handshake between Alice and Bob. Using the captured handshake, she can 
try to guess the password, offline. With a PAKE protocol, she cannot do 
that.

- Heikki

At 2015-03-14 09:44:02 +0200, hlinnaka@iki.fi wrote:
>
> Perhaps it would be time to restart the discussion on standardizing
> SRP as a SASL mechanism in IETF.

I haven't seen much evidence that there's any interest in doing this; in
fact, I can't remember the author of the draft you pointed to being very
active in the discussions either.

> Assume that the connection is not encrypted, and Eve captures the
> SCRAM handshake between Alice and Bob. Using the captured handshake,
> she can try to guess the password, offline. With a PAKE protocol, she
> cannot do that.

OK. I agree that this is a nice property. SCRAM made the design decision
to hinder such attacks by using PBKDF2 rather than a zero-knowledge key
exchange mechanism as SRP does. This was partly due to the trend that I
mentioned of wanting to require TLS everywhere.

I'm obviously biased in this matter, but I think it's acceptable for the
potential attack to be frustrated by the use of PBKDF2 and defeated by
the use of TLS (which is already possible with Postgres); and that in
the balance, SCRAM is easier to implement securely than SRP.

Of course, if you want to use "x" as your password everywhere, then SRP
is preferable. ;-)

-- Abhijit

P.S. I don't know why the SRP code was removed from LibreSSL; nor am I
sure how seriously to take that. It's possible that it's only because
it's (still) rather obscure.

As a followup, I spoke to an IETF friend who's used and implemented both
SRP and SCRAM. He agrees that SRP is cryptographically solid, that it's
significantly more difficult to implement (and therefore has a bit of a
monoculture risk overall, though of course that wouldn't apply to us if
we were to write the code from scratch).

Apparently the patent status is still not entirely clear. Two of the
patents expired, but there are others that may be relevant. Stanford
claims a patent, but apparently grant a free license if you do meet
certain conditions. But he doesn't know of anyone having to go to
court over the use of SRP.

-- Abhijit

Abhijit Menon-Sen wrote:

> P.S. I don't know why the SRP code was removed from LibreSSL; nor am I
> sure how seriously to take that. It's possible that it's only because
> it's (still) rather obscure.

As I recall, the working principle of the LibreSSL guys is to remove
everything that can't be understood quickly, to reduce the code base to
the minimum required to support the basic features they want, and still
be sure that there are little or no security holes.  In a later stage
their intention is to re-add interesting features as they have time to
audit the code.

-- 
Álvaro Herrera                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

* Abhijit Menon-Sen (ams@2ndQuadrant.com) wrote:
> As a followup, I spoke to an IETF friend who's used and implemented both
> SRP and SCRAM. He agrees that SRP is cryptographically solid, that it's
> significantly more difficult to implement (and therefore has a bit of a
> monoculture risk overall, though of course that wouldn't apply to us if
> we were to write the code from scratch).

There is also 'JPAKE':

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

Which had been in OpenSSH and OpenSSL and is still in NSS and Firefox
Sync.
Thanks!
    Stephen