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.