Thread: reducing our reliance on MD5

There have been a few previous attempts to wean PostgreSQL off of MD5.
Back in 2012, Heikki proposed using SCRAM for our next-generation
authentication mechanism:

http://www.postgresql.org/message-id/507550BD.2030401@vmware.com

That seems likely to be a good idea, but nobody's come up with a
patch.  Peter Bex *did* come up with a patch to replace MD5
authentication with "bcrypt", which I guess is based on Blowfish:

http://www.postgresql.org/message-id/20121227144638.GC610@frohike.homeunix.org

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.

Maybe we could make the authentication handshake pluggable:

typedef (*password_encryption_fn)(const char *passwd, const char
*salt, size_t salt_len, char *buf);  // like pg_md5_encrypt
extern void register_encrypted_authentication_type(char *name,
password_encryption_fn);

Then we could add a _PG_init() function to pgcrypto that would enable
the use of whatever pgcrypto has got to offer as authentication
handshake methods.  This has a couple of advantages.  First, we don't
have to suck pgcrypto into core, something we've been reluctant to do;
second, if MD5 or any successor algorithm is shown to be insecure,
users can just drop in a new one, either provided by us or one they
write themselves or something in an external library they have and can
integrate to.

There are a few complications:

1. Each encryption algorithm requires a wire-protocol constant to
identify it, and the client and the server have to agree on that
value.  So we'd have to define constants for whatever algorithms we
want to provide via the core distribution, and possibly either
maintain a registry of other values or at least set aside a space
(values > 1e6, maybe) that is reserved for use by extensions.

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.

Thoughts?

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

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

<div dir="ltr"><br /><div class="gmail_extra"><br /><div class="gmail_quote">On Tue, Feb 10, 2015 at 10:32 PM, Peter
Geoghegan<span dir="ltr"><<a href="mailto:pg@heroku.com" target="_blank">pg@heroku.com</a>></span> wrote:<br
/><blockquoteclass="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"><spanclass="">On Tue, Feb 10, 2015 at 4:21 PM, Robert Haas <<a
href="mailto:robertmhaas@gmail.com">robertmhaas@gmail.com</a>>wrote:<br /> > Although the patch was described as
relativelyeasy to write, it never<br /> > went anywhere, because it *replaced* MD5 authentication with bcrypt,<br />
>which would be a big problem for existing clients.  It seems clear<br /> > that we should add something new and
notimmediately kill off what<br /> > we've already got, so that people can transition smoothly.  An idea I<br />
>just had today is to keep using basically the same system that we are<br /> > currently using for MD5, but with
astronger hash algorithm, like<br /> > SHA-1 or SHA-2 (which includes SHA-224, SHA-256, SHA-384, and<br /> >
SHA-512). Those are slower, but my guess is that even SHA-512 is not<br /> > enough slower for anybody to care very
much,and if they do, well<br /> > that's another reason to make use of the new stuff optional.<br /><br /></span>I
believethat a big advantage of bcrypt for authentication is the<br /> relatively high memory requirements. This
frustratesGPU based<br /> attacks.<br /><span class=""><font color="#888888"><br /><br /> --<br /> Peter Geoghegan<br
/></font></span><divclass=""><div class="h5"><br /><br /> --<br /> Sent via pgsql-hackers mailing list (<a
href="mailto:pgsql-hackers@postgresql.org">pgsql-hackers@postgresql.org</a>)<br/> To make changes to your
subscription:<br/><a href="http://www.postgresql.org/mailpref/pgsql-hackers"
target="_blank">http://www.postgresql.org/mailpref/pgsql-hackers</a><br/></div></div></blockquote></div><br
/></div><divclass="gmail_extra">There's also scrypt, which can be tuned for both memory and compute requirements.<br
/><br/>I don't think the "password storing best practices" apply to db connection authentication. So SHA256 (or any
othernon terribly broken hash) is probably fine for Pg.<br /><br /></div></div> 

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

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

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

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

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

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

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

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

<div dir="ltr"><br /><div class="gmail_extra"><br /><div class="gmail_quote">On Tue, Feb 10, 2015 at 11:25 PM, Peter
Geoghegan<span dir="ltr"><<a href="mailto:pg@heroku.com" target="_blank">pg@heroku.com</a>></span> wrote:<br
/><blockquoteclass="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span
class="">OnTue, Feb 10, 2015 at 5:22 PM, Arthur Silva <<a
href="mailto:arthurprs@gmail.com">arthurprs@gmail.com</a>>wrote:<br /> > I assume if the hacker can intercept the
serverunencrypted traffic and/or<br /> > has access to its hard-drive the database is compromised anyway.<br /><br
/></span>Thatsounds like an argument against hashing the passwords in general.<br /><span class="HOEnZb"><font
color="#888888"><br/><br /> --<br /> Peter Geoghegan<br /></font></span></blockquote></div><br /></div><div
class="gmail_extra">Indeed.<br/><br /></div><div class="gmail_extra">In a perfect world SCRAM would be the my choice.
FWIWMongodb 3.0 also uses SCRAM as the preferred method for password based authentication.<br /></div></div> 

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

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.

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

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

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

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

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

On 11/02/15 02:30, Tom Lane wrote:
> [...]
>
>
> 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.
    mitm
    We might consider it our problem or not, but in general terms 
man-in-the-middle attacks, which are easy to implement in many 
scenarios, are a scraping problem. In particular, I have seen tons of 
developers turn off SSL validation during development and not turning 
back it on for production, leaving servers vulnerable to password 
scraping under mitm attacks. So I would always considering hashing anyway.
    SCRAM seems to be a good solution anyway.
    Regards,
    Álvaro

On Wed, Feb 11, 2015 at 8:02 AM, Heikki Linnakangas
<hlinnakangas@vmware.com> wrote:
> 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.

So are you thinking to integrate with the Cyrus SASL library, or do
you have another thought?

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

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.

All discussion seems to be about the protocol, which is also the harder problem, isn't it? 

ISTM that the more *important* thing to fix is the on-disk storage in pg_authid.

[snip]

Seems the risk of someone either lifting pg_authid from disk or by hacking the system and being postgres, thereby accessing passwords stored somewhere else, is actually the bigger problem. But also one that should be reasonably easy (TM) to fix in a backwards compatible way? (just rewrite with a new hash whenever the password is changed, but keep reading md5 until they are all replaced.

On Wed, Feb 11, 2015 at 9:14 AM, Magnus Hagander <magnus@hagander.net> wrote:
> On Wed, Feb 11, 2015 at 3:10 PM, José Luis Tallón
> <jltallon@adv-solutions.net> wrote:
>>
>> On 02/11/2015 02:31 PM, Magnus Hagander 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.
>>
>>
>>
>> All discussion seems to be about the protocol, which is also the harder
>> problem, isn't it?
>>
>> ISTM that the more *important* thing to fix is the on-disk storage in
>> pg_authid.
>>
>>
>> At least, looks like it would be the most urgent (and with no need for
>> clients breaking in the process, AFAICT)
>>
>> [snip]
>> Seems the risk of someone either lifting pg_authid from disk or by hacking
>> the system and being postgres, thereby accessing passwords stored somewhere
>> else, is actually the bigger problem. But also one that should be reasonably
>> easy (TM) to fix in a backwards compatible way? (just rewrite with a new
>> hash whenever the password is changed, but keep reading md5 until they are
>> all replaced.
>>
>>
>> Adding a new system column with a text or enum representing the algorithm
>> that created the "hash" would go a lot towards fixing this situation.
>> When/If the column isn't there, just assume "md5". This would allow for
>> transparent pg_upgrade.
>
>
> The hash value in pg_authid already contains "md5" as a prefix. No need for
> another column.

How do we distinguish that from a password that actually starts with md5?

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

On Wed, Feb 11, 2015 at 10:31 AM, Magnus Hagander <magnus@hagander.net> wrote:
> On Wed, Feb 11, 2015 at 4:57 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>
>> 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.
>
>
>
> All discussion seems to be about the protocol, which is also the harder
> problem, isn't it?
>
> ISTM that the more *important* thing to fix is the on-disk storage in
> pg_authid.
>
> If you actually worry about someone sniffing your network and mounting an
> attack against a password, you can use SSL. That means we already have a way
> to deal with that, whereas we don't have a way to mitigate the pg_authid
> thing. And also, if you are actually worried about someone sniffing an
> MD5'ed password, shouldn't you also worry about that same person sniffing
> all the *contents* of your database, which the password is there to protect?
>
> (and in that regard, LDAP and such encryption algorithms send the password
> in clear text in that case....)
>
> Seems the risk of someone either lifting pg_authid from disk or by hacking
> the system and being postgres, thereby accessing passwords stored somewhere
> else, is actually the bigger problem. But also one that should be reasonably
> easy (TM) to fix in a backwards compatible way? (just rewrite with a new
> hash whenever the password is changed, but keep reading md5 until they are
> all replaced.

Problem with all challenge-response authentication protocols, is that
the hash you have stored has to match the hash you use on the wire
protocol.

It's not like you can store a SHA and provide MD5 authentication.

In essence, it makes making it pluggable or doing both changes
separately as two separate improvements more difficult.

On 02/11/2015 03:14 PM, Magnus Hagander wrote:
>
> [snip]
> The hash value in pg_authid already contains "md5" as a prefix. No 
> need for another column.

Yes, but for variable length mechanism names (i.e. not just 3 chars) it 
would become increasingly difficult to differentiate between the algo 
name and the stored credentials.... especially if we delegated the list 
of available mechanisms to an external library and/or in the case of 
upgrades.    (variable-length matching based on a table of available mechs and 
using strncmp isn't complicated, admittedly .... but why bother?)
    ... plus we have already added many new columns to store the new 
"capabilities" in, as opposed to a bitmask.

I might well be overlooking something else, of course.


Regards,
    / J.L.

On 02/11/2015 03:39 PM, Claudio Freire wrote:
> [snip]
> Seems the risk of someone either lifting pg_authid from disk or by hacking
> the system and being postgres, thereby accessing passwords stored somewhere
> else, is actually the bigger problem. But also one that should be reasonably
> easy (TM) to fix in a backwards compatible way? (just rewrite with a new
> hash whenever the password is changed, but keep reading md5 until they are
> all replaced.
> Problem with all challenge-response authentication protocols, is that
> the hash you have stored has to match the hash you use on the wire
> protocol.
>
> It's not like you can store a SHA and provide MD5 authentication.

Yes, except that you can do "fallback to plaintext" if the client 
requests (S)CRAM-SHA and you have (S)CRAM-MD5 instead, allowing for some 
interoperability and backwards compatibility in the process: pre-change 
libpq/JDBC could authenticate using password to a server with just 
SCRAM-SHA512 credentials.

In any case, just storing the "password BLOB"(text or base64 encoded) 
along with a mechanism identifier would go a long way towards making 
this part pluggable... just like we do with LDAP/RADIUS/Kerberos/PAM today.

    / J.L.

On Wed, Feb 11, 2015 at 11:48 AM, José Luis Tallón
<jltallon@adv-solutions.net> wrote:
> On 02/11/2015 03:39 PM, Claudio Freire wrote:
>>
>> [snip]
>> Seems the risk of someone either lifting pg_authid from disk or by hacking
>> the system and being postgres, thereby accessing passwords stored
>> somewhere
>> else, is actually the bigger problem. But also one that should be
>> reasonably
>> easy (TM) to fix in a backwards compatible way? (just rewrite with a new
>> hash whenever the password is changed, but keep reading md5 until they are
>> all replaced.
>> Problem with all challenge-response authentication protocols, is that
>> the hash you have stored has to match the hash you use on the wire
>> protocol.
>>
>> It's not like you can store a SHA and provide MD5 authentication.
>
>
> Yes, except that you can do "fallback to plaintext" if the client requests
> (S)CRAM-SHA and you have (S)CRAM-MD5 instead, allowing for some
> interoperability and backwards compatibility in the process: pre-change
> libpq/JDBC could authenticate using password to a server with just
> SCRAM-SHA512 credentials.
>
> In any case, just storing the "password BLOB"(text or base64 encoded) along
> with a mechanism identifier would go a long way towards making this part
> pluggable... just like we do with LDAP/RADIUS/Kerberos/PAM today.


Wait... you mean falling back to storing plaintext or falling back to
transmitting plaintext over the wire?

Both seem a step backwards IMO.

On 02/11/2015 03:55 PM, Claudio Freire wrote:
>> On 02/11/2015 03:39 PM, Claudio Freire wrote:
>>
>> [snip]
>> Seems the risk of someone either lifting pg_authid from disk or by hacking
>> the system and being postgres, thereby accessing passwords stored
>> somewhere
>> else, is actually the bigger problem. But also one that should be
>> reasonably
>> easy (TM) to fix in a backwards compatible way? (just rewrite with a new
>> hash whenever the password is changed, but keep reading md5 until they are
>> all replaced.
>> Problem with all challenge-response authentication protocols, is that
>> the hash you have stored has to match the hash you use on the wire
>> protocol.
>>
>> It's not like you can store a SHA and provide MD5 authentication.
>>
>> Yes, except that you can do "fallback to plaintext" if the client requests
>> (S)CRAM-SHA and you have (S)CRAM-MD5 instead, allowing for some
>> interoperability and backwards compatibility in the process: pre-change
>> libpq/JDBC could authenticate using password to a server with just
>> SCRAM-SHA512 credentials.
>>
>> In any case, just storing the "password BLOB"(text or base64 encoded) along
>> with a mechanism identifier would go a long way towards making this part
>> pluggable... just like we do with LDAP/RADIUS/Kerberos/PAM today.
>
> Wait... you mean falling back to storing plaintext or falling back to
> transmitting plaintext over the wire?

Fallback to authentication using plaintext ... if the client is old. And 
might as well require SSL before allowing that --- the sane solution, 
definitively.    But let us not forget that there exist environments where even 
non-SSL plaintext is acceptable when the network is secure/trusted. We 
should not prevent that usage if users need it (performance or 
management reasons) if at all possible, I think.

This would imply adding a fallback "or plaintext negotiation when 
possible" to the new mechanisms.
We could even restrict that behaviour to "hostssl" entries in pg_hba.conf

> Both seem a step backwards IMO.
Hmmm... as opposed to breaking applications innecesarily when simply 
enabling SSL/TLS would not make it insecure? or when users don't really 
need it?

There are many organizations out there happily using 3rd party 
applications that they can not modify easily and this change would break 
them gratuitously.    - New policy. Introduce new hashes, update credentials (when possible!)    - New applications can
benefitfrom the newer/better security 
 
immediately    - Client app that uses older libpq/JDBC. Doesn't understand the new 
mech    - ... and now the user is left with a broken app and no easy way back
    alternative: old app has to authenticate itself just as if 
pg_hba.conf said "password", possibly restricted to doing so over an 
SSL-secured connection.


Moreover, requiring everybody to change all passwords and clients *at 
once* seems like a very poor decision towards allowing for graceful 
upgrades and make rolling changes back possible, right?

Additionally, there are cases where passwords are not stored in 
plaintext anywhere (required to be able to generate new credentials) and 
updating all clients at once simply isn't possible.
Please note that, AFAICS, adding a second entry to pg_hba.conf with the 
fallback mechanism won't work.
    Now I come to think of it, the behaviour I just proposed would help 
users and maintainers of connection poolers to achieve seamless upgrades 
while increasing security (the pooler would negotiate using the newer 
mechanism with postgres using the client-provided password)



Thanks,
    J.L.

On Wed, Feb 11, 2015 at 12:20 PM, José Luis Tallón
<jltallon@adv-solutions.net> wrote:
>> Both seem a step backwards IMO.
>
> Hmmm... as opposed to breaking applications innecesarily when simply
> enabling SSL/TLS would not make it insecure? or when users don't really need
> it?

No, as opposed to cases where people are already using md5
authentication effectively.

> Moreover, requiring everybody to change all passwords and clients *at once*
> seems like a very poor decision towards allowing for graceful upgrades and
> make rolling changes back possible, right?

I wasn't advocating for what. I was just pointing out that
implementation of SCRAM was an all-encompassing endeavour, in that you
have to attack both password storage and the transmission protocol.

For instance, if you tell me I can do SCRAM, I'll be happy to enable
it if my lib has support for it. But if you add "oh... to use it, you
must store plaintext on pg_authid", I'd change my mind. Because you
cannot do SCRAM while storing md5.

And there lies the issue I'm pointing out. I'm not giving solutions.

Except, maybe, that if it were to be explicit for user creation:

CREATE ROLE someone WITH ENCRYPTED PASSWORD '1234' USING 'pbkdf2-hmac-sha1' ;

This would preclude authentication using md5, of course, but it would
be expectable and under admin control. And I myself would use it.

> Additionally, there are cases where passwords are not stored in plaintext
> anywhere (required to be able to generate new credentials) and updating all
> clients at once simply isn't possible.

I agree

José Luis Tallón <jltallon@adv-solutions.net> writes:
> In any case, just storing the "password BLOB"(text or base64 encoded) 
> along with a mechanism identifier would go a long way towards making 
> this part pluggable... just like we do with LDAP/RADIUS/Kerberos/PAM today.

That's exactly the direction we must NOT go.

Upgrading the security of stored passwords in pg_authid is at least as
important as upgrading the wire protocol security; very possibly more so.
Any solution that requires cleartext passwords to be kept by the server
is simply not going to be accepted.

Because of this constraint, I really suspect that we have zero chance of
achieving pluggability or farming out the problem to some third party
library.

Or in short: we've done that before, with LDAP/RADIUS/Kerberos/PAM,
and none of those solutions have proven very satisfactory; they certainly
have not replaced passwords to any measurable degree.  Expecting the next
external solution to do so is the definition of insanity.
        regards, tom lane

On 02/11/2015 04:40 PM, Tom Lane wrote:
> José Luis Tallón <jltallon@adv-solutions.net> writes:
>> In any case, just storing the "password BLOB"(text or base64 encoded)
>> along with a mechanism identifier would go a long way towards making
>> this part pluggable... just like we do with LDAP/RADIUS/Kerberos/PAM today.
> That's exactly the direction we must NOT go.
>
> Upgrading the security of stored passwords in pg_authid is at least as
> important as upgrading the wire protocol security; very possibly more so.
> Any solution that requires cleartext passwords to be kept by the server
> is simply not going to be accepted.

I definitively haven't explained myself properly.
I *never* suggested storing plaintext in pg_authid, but using plaintext 
authentication (which can always be matched against an on-disk hash, 
whatever the type) as a fallback to allow for seamless upgrades of security.    (once you are authenticated by using
theold credentials, the 
 
server can transparently store the new hash)

When I referred to a "text or base64 encoded" I never implied on-disk 
plaintext (unless the user specifically requires that, which they might).


To avoid ambiguities, my proposal closely mimicks Dovecot's 
implementation of password schemes and credential upgrades    http://wiki2.dovecot.org/Authentication/PasswordSchemes




Thanks,
    J.L.

On 02/11/2015 07:54 AM, José Luis Tallón wrote:
>
> On 02/11/2015 04:40 PM, Tom Lane wrote:
>> José Luis Tallón <jltallon@adv-solutions.net> writes:
>>> In any case, just storing the "password BLOB"(text or base64 encoded)
>>> along with a mechanism identifier would go a long way towards making
>>> this part pluggable... just like we do with LDAP/RADIUS/Kerberos/PAM
>>> today.
>> That's exactly the direction we must NOT go.
From a practitioners and one step at a time perspective, why don't we 
just offer SHA-2 as an alternative to MD5?

As a longer term approach, it seems something like key based auth (ala 
SSH) which proved popular when I brought it up before seems like a 
reasonable solution.

Sincerely,

Joshua D. Drake


-- 
Command Prompt, Inc. - http://www.commandprompt.com/  503-667-4564
PostgreSQL Support, Training, Professional Services and Development
High Availability, Oracle Conversion, @cmdpromptinc
"If we send our children to Caesar for their education, we should             not be surprised when they come back as
Romans."

On Tue, Feb 10, 2015 at 09:30:37PM -0500, Tom Lane wrote:
> 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.

Agreed.  In 2004 Greg Stark estimated that it would take only 64k
connection attempts to get a server-supplied reply of a salt already
seen that can be replayed:

http://www.postgresql.org/message-id/flat/200410071728.i97HS1a16128@candle.pha.pa.us#200410071728.i97HS1a16128@candle.pha.pa.us

If you have a few salts the number goes down further.  I think the
32-bit salt length is the greatest risk to our existing MD5
implementation.  While leaving MD5 has a theoretical benefit, using a
64-bit salt has a practical benefit.

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

All,

* Heikki Linnakangas (hlinnakangas@vmware.com) wrote:
> 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.

Agreed (with this and with the overall proposal from Heikki).

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

Note that Kerberos/GSSAPI can be implemented through SASL too, which
means we might be able to deprecate and eventually remove the code we
have for that (the only caveat to that is that some the options we
provide may not all be available through SASL; that said, some of the
options we provide shouldn't ever be used in production environments,
so..).
Thanks,
    Stephen

* Heikki Linnakangas (hlinnakangas@vmware.com) wrote:
> 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.

Agreed- let's do it properly.  This is definitely an area of interest
for me and if I can ever get out from under the current things going on,
I'd be happy to help also.
Thanks,
    Stephen

On 02/11/2015 05:34 PM, Claudio Freire wrote:
> On Wed, Feb 11, 2015 at 12:20 PM, José Luis Tallón
> <jltallon@adv-solutions.net> wrote:
>> Moreover, requiring everybody to change all passwords and clients *at once*
>> seems like a very poor decision towards allowing for graceful upgrades and
>> make rolling changes back possible, right?
>
> I wasn't advocating for what. I was just pointing out that
> implementation of SCRAM was an all-encompassing endeavour, in that you
> have to attack both password storage and the transmission protocol.
>
> For instance, if you tell me I can do SCRAM, I'll be happy to enable
> it if my lib has support for it. But if you add "oh... to use it, you
> must store plaintext on pg_authid", I'd change my mind. Because you
> cannot do SCRAM while storing md5.

You can't do plain SCRAM while storing md5, but you could implement a 
variant where the stored md5 hash is treated like the plaintext 
password. The client first calculates the MD5(plaintext password), and 
then proceeds with the SCRAM authentication with that. The MD5 doesn't 
add any extra security (nor reduce it AFAICS), but it would allow doing 
SCRAM, using the MD5 hashes already stored in pg_authid.

You'd still be just as vulnerable to someone stealing the MD5 hashes 
from pg_authid, of course. So if you don't want to continue supporting 
MD5 authentication for backwards-compatibility, you'd want to transform 
all the hashes to SCRAM stored keys.

- Heikki

On 02/11/2015 03:52 PM, Robert Haas wrote:
> On Wed, Feb 11, 2015 at 8:02 AM, Heikki Linnakangas
> <hlinnakangas@vmware.com> wrote:
>> 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.
>
> So are you thinking to integrate with the Cyrus SASL library, or do
> you have another thought?

I think we need to implement the primary MD5 replacement ourselves, so 
that it's always available without extra libraries. Otherwise it will 
not get much adoption, or the extra dependency will be a hassle anyway. 
It's not that complicated, after all.

We could also support using a library like that for additional 
authentication mechanisms, though, for those who really need them.

- Heikki

On 02/11/2015 06:35 AM, Claudio Freire wrote:
> 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.

To be precise: collision resistance is usually not important for hashes 
used in authentication handshakes. Not for our MD5 authentication method 
anyway; otherwise we'd be screwed. What you need is resistance to 
pre-image attacks.

See https://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties

- Heikki

On Wed, Feb 11, 2015 at 5:25 PM, Heikki Linnakangas
<hlinnakangas@vmware.com> wrote:
> On 02/11/2015 06:35 AM, Claudio Freire wrote:
>>
>> 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.
>
>
> To be precise: collision resistance is usually not important for hashes used
> in authentication handshakes. Not for our MD5 authentication method anyway;
> otherwise we'd be screwed. What you need is resistance to pre-image attacks.

AFAIK, if I find a colliding string to the MD5 stored in pg_authid, I
can specify that to libpq and get authenticated.

Am I missing something?

On Wed, Feb 11, 2015 at 6:30 PM, Claudio Freire <klaussfreire@gmail.com> wrote:
> On Wed, Feb 11, 2015 at 5:25 PM, Heikki Linnakangas
> <hlinnakangas@vmware.com> wrote:
>> On 02/11/2015 06:35 AM, Claudio Freire wrote:
>>>
>>> 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.
>>
>>
>> To be precise: collision resistance is usually not important for hashes used
>> in authentication handshakes. Not for our MD5 authentication method anyway;
>> otherwise we'd be screwed. What you need is resistance to pre-image attacks.
>
> AFAIK, if I find a colliding string to the MD5 stored in pg_authid, I
> can specify that to libpq and get authenticated.
>
> Am I missing something?

Oh, right, that's called pre-image.

Never mind then

On 02/11/2015 11:30 PM, Claudio Freire wrote:
> On Wed, Feb 11, 2015 at 5:25 PM, Heikki Linnakangas
> <hlinnakangas@vmware.com> wrote:
>> On 02/11/2015 06:35 AM, Claudio Freire wrote:
>>>
>>> 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.
>>
>> To be precise: collision resistance is usually not important for hashes used
>> in authentication handshakes. Not for our MD5 authentication method anyway;
>> otherwise we'd be screwed. What you need is resistance to pre-image attacks.
>
> AFAIK, if I find a colliding string to the MD5 stored in pg_authid, I
> can specify that to libpq and get authenticated.
>
> Am I missing something?

If you know the MD5 stored in pg_authid, you can use that directly to 
authenticate. No need to find the original password, or another 
colliding string, that hashes to the same MD5.

- Heikki

Heikki Linnakangas <hlinnakangas@vmware.com> writes:
> On 02/11/2015 03:52 PM, Robert Haas wrote:
>> So are you thinking to integrate with the Cyrus SASL library, or do
>> you have another thought?

> I think we need to implement the primary MD5 replacement ourselves, so 
> that it's always available without extra libraries. Otherwise it will 
> not get much adoption, or the extra dependency will be a hassle anyway. 

+1

> We could also support using a library like that for additional 
> authentication mechanisms, though, for those who really need them.

We've already got a sufficiency of external authentication mechanisms.
If people wanted to use non-built-in authentication, we'd not be having
this discussion.
        regards, tom lane

* Tom Lane (tgl@sss.pgh.pa.us) wrote:
> Heikki Linnakangas <hlinnakangas@vmware.com> writes:
> > We could also support using a library like that for additional
> > authentication mechanisms, though, for those who really need them.
>
> We've already got a sufficiency of external authentication mechanisms.
> If people wanted to use non-built-in authentication, we'd not be having
> this discussion.

Just to be clear- lots of people *do* use the external authentication
mechanisms we provide, particularly Kerberos/GSSAPI.  SASL would bring
us quite a few additional mechanisms (SQL-based, Berkley DB, one-time
passwords, RSA SecurID, etc..) and would mean we might be able to
eventually drop direct GSSAPI and LDAP support and have a better
alternative for those who want to use password-based auth.
Thanks,
    Stephen

Stephen Frost <sfrost@snowman.net> writes:
> * Tom Lane (tgl@sss.pgh.pa.us) wrote:
>> We've already got a sufficiency of external authentication mechanisms.
>> If people wanted to use non-built-in authentication, we'd not be having
>> this discussion.

> Just to be clear- lots of people *do* use the external authentication
> mechanisms we provide, particularly Kerberos/GSSAPI.  SASL would bring
> us quite a few additional mechanisms (SQL-based, Berkley DB, one-time
> passwords, RSA SecurID, etc..) and would mean we might be able to
> eventually drop direct GSSAPI and LDAP support and have a better
> alternative for those who want to use password-based auth.  

My point is that we already have got a lot of external authentication
mechanisms, and it's completely unclear (to me anyway) that there is
any demand for another one.  The unsatisfied demand is for a *built in*
mechanism, specifically one that people have more faith in than MD5.
Those who worry about that and don't mind having additional moving parts
have probably already migrated to one or another of the existing external
solutions.

While I won't stand in the way of somebody adding support for an external
SASL library, I think such work has got basically zero to do with the
actual problem.
        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:
> >> We've already got a sufficiency of external authentication mechanisms.
> >> If people wanted to use non-built-in authentication, we'd not be having
> >> this discussion.
>
> > Just to be clear- lots of people *do* use the external authentication
> > mechanisms we provide, particularly Kerberos/GSSAPI.  SASL would bring
> > us quite a few additional mechanisms (SQL-based, Berkley DB, one-time
> > passwords, RSA SecurID, etc..) and would mean we might be able to
> > eventually drop direct GSSAPI and LDAP support and have a better
> > alternative for those who want to use password-based auth.
>
> My point is that we already have got a lot of external authentication
> mechanisms, and it's completely unclear (to me anyway) that there is
> any demand for another one.

To this point, I have had requests for various things which SASL would
provide- ability to use the same password as the Unix host, SecurID
support, and SQL-based (with another PG database) all come to mind.
I agree that such isn't particularly relevant to this discussion though.

> The unsatisfied demand is for a *built in*
> mechanism, specifically one that people have more faith in than MD5.

I agree that there is demand for a new mechanism which isn't MD5.  I
don't think *built in* is at all a requirement however- *easy to use*
is.

> Those who worry about that and don't mind having additional moving parts
> have probably already migrated to one or another of the existing external
> solutions.

Certainly we'd want to make SASL-with-SCRAM easy for users to use.  To
the extent that the moving parts in that arrangement are hidden from
view, hopefully users will use it and we get comfortable enough with it
for distros to set it as the default.

I am catagorically *not* worried about non-libpq client libraries and
applications in this regard.  For starters, those aren't end users,
those are other developers who have a vested interest in supporting
whatever we do.  Further, Java certainly supports SASL, as do quite a
few other languages (Python, PHP, Ruby, there's a few examples in Go it
seems).

> While I won't stand in the way of somebody adding support for an external
> SASL library, I think such work has got basically zero to do with the
> actual problem.

I don't think that's accurate.  If we provide a better mechanism for
password-based authentication, even if it is through SASL, I feel pretty
confident that at least the Debian based distros (which universally
include SASL support for applications that support it) would support it
and might even switch to it for the default (once they were comfortable
with it and enough clients supported it), unless we told them not to.

That doesn't address existing installations, of course, and we'd have to
wait for non-libpq client to update, but things would certainly move
faster if we actually had something for things to move *to*, even if
that thing is SASL-based SCRAM, imv.
Thanks!
    Stephen

SASL was done by many of the same people who did GSSAPI. It's main practical advantages are that it supports
password-basedmechanisms (in addition to GSSAPI/krb5), and that it’s more explicitly pluggable than GSSAPI is.  

The password mechanism is simple enough that it's frequently implemented without a general library in e.g. older Jabber
clients.We could likewise provide that as a configure fallback if availability of client libraries turns out to be a
problem.

Cyrus SASL is bundled with a saslauthd and other utilities that handle the on-disk storage of hashed passwords.
SASLauthdcan be configured to use PAM, Kerberos 5, MySQL, custom plugin, or local BDB files for password
verification/storage.(Instead of our own, we can provide someone else’s gun to shoot yourself with! ;-)) 

For myself, I think getting rid of MD5 is a low priority. If its replaced with SASL, then that has the advantage (?) of
replacingGSSAPI as well, so the number of user options increases while the number of mechanisms in PG itself decreases. 

Personal email.  hbhotz@oxy.edu