It occurs to me that we could make this work if we had a hash algorithm
that was commutative, in the sense that
hash(hash(a, b), c) = hash(hash(a, c), b)
for all possible passwords a and salts b, c. Then the idea
would be:
1. The value stored in pg_shadow is secret = hash(password, username)
same as now (or we could use some random salt, but we'd have to store
that salt too, so the username is probably as good as anything).
2. During connection start, pick a random salt and send it to the
client. The client computes response = hash(password, salt) and
sends it to the postmaster. Then the postmaster computes
hash(response, username) and hash(secret, salt) and compares these.
Commutativity would ensure that the values come out equal if the correct
password is supplied.
An attacker could figure out the value hash(secret, salt) if he'd seen
pg_shadow --- but if the hash function is strong then this does him no
good, because he won't be able to compute a response that will hash to
that target value.
MD5 is not commutative in this sense, and it might be that any hash
algorithm that is could not be cryptographically strong. But we could
look around and see what's out there...
regards, tom lane