Successor of MD5 authentication, let's use SCRAM

The security of MD5 authentication is brought up every now and then,
most recently here:
http://archives.postgresql.org/pgsql-hackers/2012-08/msg00586.php. The
NIST competition mentioned in that thread just finished. MD5 is still
resistent to preimage attacks, which is what matters for our MD5
authentication protocol, but I think we should start thinking about a
replacement, if only to avoid ringing the alarm bells in people's minds
thinking "MD5 = broken"

Perhaps the biggest weakness in the current scheme is that if an
attacker ever sees the contents of pg_shadow, it can use the stored
hashes to authenticate as any user. This might not seems like a big
deal, you have to be a superuser to read pg_shadow after all, but it
makes it a lot more dangerous to e.g leave old backups lying around.
Thers was some talk about avoiding that in this old thread:
http://archives.postgresql.org/pgsql-general/2002-06/msg00553.php.

It turns out that it's possible to do this without the kind of
commutative hash function discussed in that thread. There's a protocol
called Salted Challenge Response Authentication Mechanism (SCRAM) (see
RFC5802), that accomplishes the same with some clever use of a hash
function and XOR. I think we should adopt that.

Thoughts on that?

There are some other minor issues with current md5 authentication. SCRAM
would address these as well, but if we don't adopt SCRAM for some
reason, we should still address these somehow:

1. Salt length. Greg Stark calculated the odds of salt collisions here:
http://archives.postgresql.org/pgsql-hackers/2004-08/msg01540.php. It's
not too bad as it is, and as Greg pointed out, if you can eavesdrop it's
likely you can also hijack an already established connection.
Nevertheless I think we should make the salt longer, say, 16 bytes.

2. Make the calculation more expensive, to make dictionary attacks more
expensive. An eavesdropper can launch a brute-force or dictionary attack
using a captured hash and salt. Similar to the classic crypt(3)
function, it would be good for the calculation to be expensive, although
that naturally makes authentication more expensive too. For
future-proofing, it would be good to send the number of iterations the
hash is applied as part of the protocol, so that it can be configured in
the server or we can just raise the default/hardcoded number without
changing the protocol as computers becomes more powerful (SCRAM does this).

3. Instead of a straightforward hash of (password, salt), use a HMAC
construct to concatenate the password and salt (see RFC2104). This makes
it resistant to length-extension attacks. The current scheme isn't
vulnerable to that, but better safe than sorry.

- Heikki