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

Greetings,

There appears to be some deficiencies in both the documentation of the
'md5' authentication methology (in pg_hba.conf) and in the md5 hash
generation which is stored in pg_shadow.

The md5 hash which is generated for and stored in pg_shadow does not
use a random salt but instead uses the username which can generally be
determined ahead of time (especially for the 'postgres' superuser
account). This would allow for the pregeneration of the entire md5
keyspace using that 'salt' and then quick breakage of the hash once
it's retrieved by the attacker. Were a decent random salt of some
size used it would be difficult to guess and pregenerate the keyspace
for. Thus, keyspace generation would have to happen after pg_shadow
was compramised, giving the admin time to detect the compramise and
take corrective action.

A larger issue, which plays into the pg_shadow storage issue somewhat,
is the lack of proper documentation of the 'md5' method of
authentication available via pg_hba.conf. When using the 'md5' method
in pg_hba.conf this is what happens:

server sends a randomly generated 'seed' to the client
client performs md5(md5(password+username)+salt) using the salt from
the server and information provided by the user and sends the result
to the server
server performs md5(hash+salt) using the salt it sent to the client
and the hash which is stored in pg_shadow.

In so doing the server has effectively made the hash which is stored
in pg_shadow the key for authentication- the user's password is no
longer necessary to authenticate to the database, only the hash from
pg_shadow is required. It is not clear in the documentation that
using 'md5' in pg_hba.conf defeats 'with encrypted password' and the
hashing in pg_shadow. It is also not made clear that if you are
already handling transport-level security via SSL and/or IPSEC that
using md5 actually reduces security by not adding anything to the
transport-level security and defeating the on-disk security
effectivness of using md5 for pg_shadow.

It is true that while Postgres continues to use a known salt for hash
generation the effectiveness of md5 hashes in pg_shadow is reduced,
though not entirely defeated as not all have resources to generate
the keyspace for a username with a decent password (as the 'postgres'
superuser should have) or to generate the keyspace for any number of
user accounts which are the targetted accounts.

If password-based authentication is required (and other methods such
as Kerberos are unavailable), then, personally I would:

Discourage the use of 'md5' in pg_hba.conf and favor 'password'
Use good transport-level security via SSL and/or IPSEC
Change the hashing for what goes into pg_shadow to use a randomly
generated salt instead of the username (this would require
changing the protocol to allow for that randomly generated salt
to be provided to the client when 'md5' is being used in
pg_hba.conf); an alternative might be to use PAM in the meantime
Update the documetation accordingly to be clear on the issues
As soon as possible provide other hash algorithms such as sha1/2

I discussed this issue on IRC w/ some folks already though generally
they didn't appear to share my level of concern over this. My
biggest concern is that using 'md5' in pg_hba.conf reduces security
when another transport-level security mechanism is in place by a
significant amount, in my view, and this isn't clear in the
documentation.

Thanks for you time, happy to answer any questions/comments on my
analysis.

Stephen