reducing our reliance on MD5

On Tue, Feb 10, 2015 at 4:21 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Although the patch was described as relatively easy to write, it never
went anywhere, because it *replaced* MD5 authentication with bcrypt,
which would be a big problem for existing clients. It seems clear
that we should add something new and not immediately kill off what
we've already got, so that people can transition smoothly. An idea I
just had today is to keep using basically the same system that we are
currently using for MD5, but with a stronger hash algorithm, like
SHA-1 or SHA-2 (which includes SHA-224, SHA-256, SHA-384, and
SHA-512). Those are slower, but my guess is that even SHA-512 is not
enough slower for anybody to care very much, and if they do, well
that's another reason to make use of the new stuff optional.

I believe that a big advantage of bcrypt for authentication is the
relatively high memory requirements. This frustrates GPU based
attacks.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Feb 10, 2015 at 10:32 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Tue, Feb 10, 2015 at 4:21 PM, Robert Haas <robertmhaas@gmail.com>
wrote:

Although the patch was described as relatively easy to write, it never
went anywhere, because it *replaced* MD5 authentication with bcrypt,
which would be a big problem for existing clients. It seems clear
that we should add something new and not immediately kill off what
we've already got, so that people can transition smoothly. An idea I
just had today is to keep using basically the same system that we are
currently using for MD5, but with a stronger hash algorithm, like
SHA-1 or SHA-2 (which includes SHA-224, SHA-256, SHA-384, and
SHA-512). Those are slower, but my guess is that even SHA-512 is not
enough slower for anybody to care very much, and if they do, well
that's another reason to make use of the new stuff optional.

I believe that a big advantage of bcrypt for authentication is the
relatively high memory requirements. This frustrates GPU based
attacks.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

There's also scrypt, which can be tuned for both memory and compute
requirements.

I don't think the "password storing best practices" apply to db connection
authentication. So SHA256 (or any other non terribly broken hash) is
probably fine for Pg.

On Tue, Feb 10, 2015 at 5:14 PM, Arthur Silva <arthurprs@gmail.com> wrote:

I don't think the "password storing best practices" apply to db connection
authentication.

Why not?

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Feb 10, 2015 at 11:19 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Tue, Feb 10, 2015 at 5:14 PM, Arthur Silva <arthurprs@gmail.com> wrote:

I don't think the "password storing best practices" apply to db

connection

authentication.

Why not?

--
Peter Geoghegan

I assume if the hacker can intercept the server unencrypted traffic and/or
has access to its hard-drive the database is compromised anyway.

I maybe missing something though.

On Tue, Feb 10, 2015 at 5:22 PM, Arthur Silva <arthurprs@gmail.com> wrote:

I assume if the hacker can intercept the server unencrypted traffic and/or
has access to its hard-drive the database is compromised anyway.

That sounds like an argument against hashing the passwords in general.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Feb 10, 2015 at 7:32 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Tue, Feb 10, 2015 at 4:21 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Although the patch was described as relatively easy to write, it never
went anywhere, because it *replaced* MD5 authentication with bcrypt,
which would be a big problem for existing clients. It seems clear
that we should add something new and not immediately kill off what
we've already got, so that people can transition smoothly. An idea I
just had today is to keep using basically the same system that we are
currently using for MD5, but with a stronger hash algorithm, like
SHA-1 or SHA-2 (which includes SHA-224, SHA-256, SHA-384, and
SHA-512). Those are slower, but my guess is that even SHA-512 is not
enough slower for anybody to care very much, and if they do, well
that's another reason to make use of the new stuff optional.

I believe that a big advantage of bcrypt for authentication is the
relatively high memory requirements. This frustrates GPU based
attacks.

I don't actually care which algorithm we use, and I dowannahafta care.
What I do want to do is provide a framework so that, when somebody
discovers that X is better than Y because Z, somebody who knows about
cryptography and not much about PostgreSQL ca add support for X in a
relatively small number of lines of code.

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2/10/15 8:28 PM, Robert Haas wrote:

I don't actually care which algorithm we use, and I dowannahafta care.
What I do want to do is provide a framework so that, when somebody
discovers that X is better than Y because Z, somebody who knows about
cryptography and not much about PostgreSQL ca add support for X in a
relatively small number of lines of code.

sounds like SASL

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 02/10/2015 05:28 PM, Robert Haas wrote:

I don't actually care which algorithm we use, and I dowannahafta care.
What I do want to do is provide a framework so that, when somebody
discovers that X is better than Y because Z, somebody who knows about
cryptography and not much about PostgreSQL ca add support for X in a
relatively small number of lines of code.

+1

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Robert Haas <robertmhaas@gmail.com> writes:

Although the patch was described as relatively easy to write, it never
went anywhere, because it *replaced* MD5 authentication with bcrypt,
which would be a big problem for existing clients.

Right. The client end of it is the elephant in the room in any discussion
of improving the password hash algorithm.

2. We'd have to figure out how to get support for the new algorithms
into libpq. This actually seems a good bit harder than doing it on
the server-side, because I don't think libpq has any dynamic loading
facilities the way the server does.

If you think libpq is the only problem, or even the main problem,
on the client side then you have seriously misjudged the situation.
There are multiple clients that do not use libpq at all, JDBC being
the poster child here.

Another thing we need to keep in mind besides client compatibility
is dump/reload compatibility.

I think it would be wise to take two steps back and think about what
the threat model is here, and what we actually need to improve.
Offhand I can remember two distinct things we might wish to have more
protection against:

* scraping of passwords off the wire protocol (but is that still
a threat in an SSL world?). Better salting practice would do more
than replacing the algorithm as such for this, IMO.

* scraping of passwords directly from the pg_authid table or from
a pg_dump dump. In this case it's not so much that we are worried
about preventing the scraper from accessing the database (he's
evidently in already) as that we'd like to prevent him from recovering
the original cleartext, since the user might've used that same password
elsewhere. (Bad user, but nonetheless something we might try to
protect against.) Again, more salt seems like it might go a lot further
than just changing the algorithm.

Are there other goals?

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Peter Eisentraut <peter_e@gmx.net> writes:

On 2/10/15 8:28 PM, Robert Haas wrote:

I don't actually care which algorithm we use, and I dowannahafta care.
What I do want to do is provide a framework so that, when somebody
discovers that X is better than Y because Z, somebody who knows about
cryptography and not much about PostgreSQL ca add support for X in a
relatively small number of lines of code.

sounds like SASL

Sounds like pie in the sky really :-(. We could make the server turn on
a dime perhaps, but the client-side population will not come along nearly
that quickly, nor with small effort. Stored passwords won't migrate to a
new scheme transparently either.

I think it's probably reasonable to think about a more modern password
auth method, but not to imagine that it will be pluggable or that the
adoption time for any revision will be less than years long.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Feb 10, 2015 at 9:30 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

2. We'd have to figure out how to get support for the new algorithms
into libpq. This actually seems a good bit harder than doing it on
the server-side, because I don't think libpq has any dynamic loading
facilities the way the server does.

If you think libpq is the only problem, or even the main problem,
on the client side then you have seriously misjudged the situation.
There are multiple clients that do not use libpq at all, JDBC being
the poster child here.

We don't want to make things unnecessarily difficult for clients that
implement the wire protocol from scratch, but I don't think it's our
job to tell the owners of other connectors if, or when, they want to
support new authentication methods. They certainly won't support them
*before* we have server-side support; we can hope that if we add
server-side support, they will follow along.

Another thing we need to keep in mind besides client compatibility
is dump/reload compatibility.

I don't think there's an issue with dump/reload compatibility as far
as what I proposed, since it only has to do with the authentication
procedure, not what gets stored in pg_authid. We might have reasons
for moving that away from MD5 as well, but it's a separate project.

I think it would be wise to take two steps back and think about what
the threat model is here, and what we actually need to improve.
Offhand I can remember two distinct things we might wish to have more
protection against:

* scraping of passwords off the wire protocol (but is that still
a threat in an SSL world?). Better salting practice would do more
than replacing the algorithm as such for this, IMO.

* scraping of passwords directly from the pg_authid table or from
a pg_dump dump. In this case it's not so much that we are worried
about preventing the scraper from accessing the database (he's
evidently in already) as that we'd like to prevent him from recovering
the original cleartext, since the user might've used that same password
elsewhere. (Bad user, but nonetheless something we might try to
protect against.) Again, more salt seems like it might go a lot further
than just changing the algorithm.

Are there other goals?

I think the goal is "stop using MD5, or at least have an option to not
use MD5, because people think that's insecure". Whether those people
are right or not is probably extremely arguable - indeed, I can
imagine your opening salvo here giving rise to vigorous debate about
whether MD5, in the particular way we are using it, is or is not
secure. The problem is that MD5 has enough weaknesses that, even if
it is actually secure in the way we are using it, some people are not
going to believe that, and are going to think we're bad people for
using it in any way whatsoever. I'd like to keep those people as
users, whoever is right about the security issues. The second problem
is that, even if we could convince all of the people who might be
worried about MD5 that their fears are unfounded, a new attack can be
discovered at any time that weakens it still further and renders what
we're doing unsafe. We shouldn't wait until then to start the
years-long process of weaning ourselves off of it.

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Feb 10, 2015 at 11:25 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Tue, Feb 10, 2015 at 5:22 PM, Arthur Silva <arthurprs@gmail.com> wrote:

I assume if the hacker can intercept the server unencrypted traffic

and/or

has access to its hard-drive the database is compromised anyway.

That sounds like an argument against hashing the passwords in general.

--
Peter Geoghegan

Indeed.

In a perfect world SCRAM would be the my choice. FWIW Mongodb 3.0 also uses
SCRAM as the preferred method for password based authentication.

Robert Haas <robertmhaas@gmail.com> writes:

On Tue, Feb 10, 2015 at 9:30 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Another thing we need to keep in mind besides client compatibility
is dump/reload compatibility.

I don't think there's an issue with dump/reload compatibility as far
as what I proposed, since it only has to do with the authentication
procedure, not what gets stored in pg_authid. We might have reasons
for moving that away from MD5 as well, but it's a separate project.

Hm, well, that doesn't really square with your other expressed opinion:

Are there other goals?

I think the goal is "stop using MD5, or at least have an option to not
use MD5, because people think that's insecure".

As you say, it's quite debatable whether MD5 is or isn't secure enough
given the way we use it, but what's not debatable is that the optics of it
are not very good anymore. However, if we want to shut up the peanut
gallery on this point, we have to get rid of MD5 usage in pg_authid not
just the on-the-wire protocol --- I seriously doubt that the knee jerk
MD5-is-insecure crowd will make any distinction there. So I'm not
following how you're satisfied with a proposal for just the latter.

In any case, my larger point was that given the pain that we're going to
incur here, and the certainly years-long transition interval involved,
it would be foolish to think only about replacing the MD5 algorithm and
not about reconsidering the context we use it in. Stuff like unreasonably
short salt values should be dealt with at the same time.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Tue, Feb 10, 2015 at 10:19 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Tue, Feb 10, 2015 at 5:14 PM, Arthur Silva <arthurprs@gmail.com> wrote:

I don't think the "password storing best practices" apply to db connection
authentication.

Why not?

Usually because handshakes use a random salt on both sides. Not sure
about pg's though, but in general collision strength is required but
not slowness, they're not bruteforceable.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2/10/15 6:32 PM, Peter Geoghegan wrote:

On Tue, Feb 10, 2015 at 4:21 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Although the patch was described as relatively easy to write, it never
went anywhere, because it *replaced* MD5 authentication with bcrypt,
which would be a big problem for existing clients. It seems clear
that we should add something new and not immediately kill off what
we've already got, so that people can transition smoothly. An idea I
just had today is to keep using basically the same system that we are
currently using for MD5, but with a stronger hash algorithm, like
SHA-1 or SHA-2 (which includes SHA-224, SHA-256, SHA-384, and
SHA-512). Those are slower, but my guess is that even SHA-512 is not
enough slower for anybody to care very much, and if they do, well
that's another reason to make use of the new stuff optional.

I believe that a big advantage of bcrypt for authentication is the
relatively high memory requirements. This frustrates GPU based
attacks.

This is especially critical if things like bitcoin ASIC rigs could be
put to use generating generic SHA256 hashes. A few grand will buy you
hardware that can generate trillions of hash values per second. AFAIK
there's no specialized hardware for scrypt though (even though it's used
for other cryptocurrencies), in part because it's not cost effective to
put enough memory in place.
--
Jim Nasby, Data Architect, Blue Treble Consulting
Data in Trouble? Get it in Treble! http://BlueTreble.com

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 02/11/2015 04:38 AM, Tom Lane wrote:

Peter Eisentraut <peter_e@gmx.net> writes:

On 2/10/15 8:28 PM, Robert Haas wrote:

I don't actually care which algorithm we use, and I dowannahafta care.
What I do want to do is provide a framework so that, when somebody
discovers that X is better than Y because Z, somebody who knows about
cryptography and not much about PostgreSQL ca add support for X in a
relatively small number of lines of code.

sounds like SASL

Sounds like pie in the sky really :-(.

SASL won't automatically solve any of ourproblems. We still have to
write the support for all the authentication mechanisms we wanted to
support. The nice thing about SASL is there is a list of well-understood
and documented mechanisms that go with it, with canonical names like
"SCRAM-SHA-1". If we use those, it's well-defined what the mechanism is,
with less design work for us. And who knows, it just might make it
easier to add client-support, if there's an existing SASL library for
language X.

So +1 for implementing SASL. It's simple to implement, and AFAICS isn't
any more difficult than rolling our own.

We could make the server turn on
a dime perhaps, but the client-side population will not come along nearly
that quickly, nor with small effort. Stored passwords won't migrate to a
new scheme transparently either.

Yep.

I think it's probably reasonable to think about a more modern password
auth method, but not to imagine that it will be pluggable or that the
adoption time for any revision will be less than years long.

It makes sense to make it pluggable if it's simple, but in reality most
drivers will support only a few most common mechanisms. That's OK. We
need to design the protocol so that multiple mechanisms can be used
side-by-side for years.

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 02/11/2015 05:57 AM, Tom Lane wrote:

In any case, my larger point was that given the pain that we're going to
incur here, and the certainly years-long transition interval involved,
it would be foolish to think only about replacing the MD5 algorithm and
not about reconsidering the context we use it in. Stuff like unreasonably
short salt values should be dealt with at the same time.

+1. We should pick a well-documented mechanism with well-understood
properties, rather than roll our own again.

Apart from the weaknesses in the MD5 authentication method itself, our
protocol doesn't make it easy to add new methods and still support old
clients gracefully. We should address that too.

For the first cut, I propose:

1. Implement SASL. The server sends a new AuthenticationSASLRequest
message, to which the client responds with AuthenticationSASLResponse
message. These messages carry the SASL challenge/response messages,
until AuthenticationOK is received. Similar to our GSSAPI
implementation. (Note that this doesn't require the use of any 3rd party
libraries or such. The specification for SASL itself is very short and
high-level.)

2. Add a way for the client and server to negotiate which authentication
mechanism to use. Currently, the server dictates it to the client, and
if it doesn't support that mechanism, it has to disconnect. To make it
possible to add new mechanisms gracefully, with a long transition
period, we need a way to negotiate. The server should send a list of
allowed authentication methods in the first AuthenticationSASLRequest
message, and the client picks one.

3. To support old clients that don't understand the new
AuthenticationSASLRequest message, the client tells that it supports it
before the authentication begins. It does that by tacking a special
option "protocol.extensions=sasl" in the startup packet (more extensions
could be added there in the future, as a comma-separated list). With 9.2
and above servers, the server will ignore unrecognized options
containing a dot. 9.1 and earlier will throw an error, but the client
can then retry without the option, like libpq does for application_name.

4. Implement the SASL mechanism "SCRAM". That's a challenge/response
password scheme, similar to the current MD5 authentication, but with
better salt and more expensive computation (= more resistance to
dictionary attacks).

5. Modify/add syntax to ALTER USER SET PASSWORD to allow storing the new
SCRAM, and other, authentication information in pg_authid.

That's it for starters. The SCRAM mechanism is a fairly straightforward
replacement for MD5. This scheme makes it possible to add more
mechanisms later, without requiring all clients to immediately support them.

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Feb 11, 2015 at 4:13 AM, Heikki Linnakangas
<hlinnakangas@vmware.com> wrote:

For the first cut, I propose:

1. Implement SASL. The server sends a new AuthenticationSASLRequest message,
to which the client responds with AuthenticationSASLResponse message. These
messages carry the SASL challenge/response messages, until AuthenticationOK
is received. Similar to our GSSAPI implementation. (Note that this doesn't
require the use of any 3rd party libraries or such. The specification for
SASL itself is very short and high-level.)

2. Add a way for the client and server to negotiate which authentication
mechanism to use. Currently, the server dictates it to the client, and if it
doesn't support that mechanism, it has to disconnect. To make it possible to
add new mechanisms gracefully, with a long transition period, we need a way
to negotiate. The server should send a list of allowed authentication
methods in the first AuthenticationSASLRequest message, and the client picks
one.

3. To support old clients that don't understand the new
AuthenticationSASLRequest message, the client tells that it supports it
before the authentication begins. It does that by tacking a special option
"protocol.extensions=sasl" in the startup packet (more extensions could be
added there in the future, as a comma-separated list). With 9.2 and above
servers, the server will ignore unrecognized options containing a dot. 9.1
and earlier will throw an error, but the client can then retry without the
option, like libpq does for application_name.

4. Implement the SASL mechanism "SCRAM". That's a challenge/response
password scheme, similar to the current MD5 authentication, but with better
salt and more expensive computation (= more resistance to dictionary
attacks).

5. Modify/add syntax to ALTER USER SET PASSWORD to allow storing the new
SCRAM, and other, authentication information in pg_authid.

That's it for starters. The SCRAM mechanism is a fairly straightforward
replacement for MD5. This scheme makes it possible to add more mechanisms
later, without requiring all clients to immediately support them.

So, this all sounds fairly nice if somebody's willing to do the work,
but I can't help noticing that you originally proposed adopting SCRAM
in 2012, and it's 2015 now. So I wonder if anyone's really going to
do all this work, and if not, whether we should go for something
simpler. Just plugging something else in for MD5 would be a lot less
work for us to implement and for clients to support, even if it is (as
it unarguably is) less elegant.

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

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 02/11/2015 02:49 PM, Robert Haas wrote:

So, this all sounds fairly nice if somebody's willing to do the work,
but I can't help noticing that you originally proposed adopting SCRAM
in 2012, and it's 2015 now. So I wonder if anyone's really going to
do all this work, and if not, whether we should go for something
simpler. Just plugging something else in for MD5 would be a lot less
work for us to implement and for clients to support, even if it is (as
it unarguably is) less elegant.

"Just plugging something else in for MD5" would still be a fair amount
of work. Not that much less than the full program I proposed.

Well, I guess it's easier if you immediately stop supporting MD5, have a
"flag day" in all clients to implement the replacement, and break
pg_dump/restore of passwords in existing databases. That sounds
horrible. Let's do this properly. I can help with that, although I don't
know if I'll find the time and enthusiasm to do all of it alone.

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers