Replace PostmasterRandom() with a stronger source, second attempt.

This adds a new routine, pg_strong_random() for generating random bytes,
for use in both frontend and backend. At the moment, it's only used in
the backend, but the upcoming SCRAM authentication patches need strong
random numbers in libpq as well.

pg_strong_random() is based on, and replaces, the existing implementation
in pgcrypto. It can acquire strong random numbers from a number of sources,
depending on what's available:

- OpenSSL RAND_bytes(), if built with OpenSSL
- On Windows, the native cryptographic functions are used
- /dev/urandom

Unlike the current pgcrypto function, the source is chosen by configure.
That makes it easier to test different implementations, and ensures that
we don't accidentally fall back to a less secure implementation, if the
primary source fails. All of those methods are quite reliable, it would be
pretty surprising for them to fail, so we'd rather find out by failing
hard.

If no strong random source is available, we fall back to using erand48(),
seeded from current timestamp, like PostmasterRandom() was. That isn't
cryptographically secure, but allows us to still work on platforms that
don't have any of the above stronger sources. Because it's not very secure,
the built-in implementation is only used if explicitly requested with
--disable-strong-random.

This replaces the more complicated Fortuna algorithm we used to have in
pgcrypto, which is unfortunate, but all modern platforms have /dev/urandom,
so it doesn't seem worth the maintenance effort to keep that. pgcrypto
functions that require strong random numbers will be disabled with
--disable-strong-random.

Original patch by Magnus Hagander, tons of further work by Michael Paquier
and me.

Discussion: https://www.postgresql.org/message-id/CAB7nPqRy3krN8quR9XujMVVHYtXJ0_60nqgVc6oUk8ygyVkZsA@mail.gmail.com
Discussion: https://www.postgresql.org/message-id/CAB7nPqRWkNYRRPJA7-cF+LfroYV10pvjdz6GNvxk-Eee9FypKA@mail.gmail.com

20 files changed, 506 insertions, 101 deletions

diff --git a/src/Makefile.global.in b/src/Makefile.global.in
index aa1fa658ed0..d39d6ca8670 100644
--- a/src/Makefile.global.in
+++ b/src/Makefile.global.in
@@ -197,6 +197,7 @@ enable_dtrace	= @enable_dtrace@
 enable_coverage	= @enable_coverage@
 enable_tap_tests	= @enable_tap_tests@
 enable_thread_safety	= @enable_thread_safety@
+enable_strong_random	= @enable_strong_random@
 
 python_includespec	= @python_includespec@
 python_libdir		= @python_libdir@
diff --git a/src/backend/libpq/auth.c b/src/backend/libpq/auth.c
index 0ba85301149..5d166db5744 100644
--- a/src/backend/libpq/auth.c
+++ b/src/backend/libpq/auth.c
@@ -33,6 +33,7 @@
 #include "miscadmin.h"
 #include "replication/walsender.h"
 #include "storage/ipc.h"
+#include "utils/backend_random.h"
 
 
 /*----------------------------------------------------------------
@@ -43,10 +44,22 @@ static void sendAuthRequest(Port *port, AuthRequest areq, char *extradata,
 				int extralen);
 static void auth_failed(Port *port, int status, char *logdetail);
 static char *recv_password_packet(Port *port);
-static int	recv_and_check_password_packet(Port *port, char **logdetail);
 
 
 /*----------------------------------------------------------------
+ * MD5 authentication
+ *----------------------------------------------------------------
+ */
+static int CheckMD5Auth(Port *port, char **logdetail);
+
+/*----------------------------------------------------------------
+ * Plaintext password authentication
+ *----------------------------------------------------------------
+ */
+
+static int CheckPasswordAuth(Port *port, char **logdetail);
+
+/*----------------------------------------------------------------
  * Ident authentication
  *----------------------------------------------------------------
  */
@@ -536,13 +549,11 @@ ClientAuthentication(Port *port)
 						(errcode(ERRCODE_INVALID_AUTHORIZATION_SPECIFICATION),
 						 errmsg("MD5 authentication is not supported when \"db_user_namespace\" is enabled")));
 			/* include the salt to use for computing the response */
-			sendAuthRequest(port, AUTH_REQ_MD5, port->md5Salt, 4);
-			status = recv_and_check_password_packet(port, &logdetail);
+			status = CheckMD5Auth(port, &logdetail);
 			break;
 
 		case uaPassword:
-			sendAuthRequest(port, AUTH_REQ_PASSWORD, NULL, 0);
-			status = recv_and_check_password_packet(port, &logdetail);
+			status = CheckPasswordAuth(port, &logdetail);
 			break;
 
 		case uaPAM:
@@ -696,23 +707,48 @@ recv_password_packet(Port *port)
  *----------------------------------------------------------------
  */
 
-/*
- * Called when we have sent an authorization request for a password.
- * Get the response and check it.
- * On error, optionally store a detail string at *logdetail.
+static int
+CheckMD5Auth(Port *port, char **logdetail)
+{
+	char		md5Salt[4];		/* Password salt */
+	char	   *passwd;
+	int			result;
+
+	pg_backend_random(md5Salt, 4);
+
+	sendAuthRequest(port, AUTH_REQ_MD5, md5Salt, 4);
+
+	passwd = recv_password_packet(port);
+
+	if (passwd == NULL)
+		return STATUS_EOF;		/* client wouldn't send password */
+
+	result = md5_crypt_verify(port, port->user_name, passwd, md5Salt, 4, logdetail);
+
+	pfree(passwd);
+
+	return result;
+}
+
+/*----------------------------------------------------------------
+ * Plaintext password authentication
+ *----------------------------------------------------------------
  */
+
 static int
-recv_and_check_password_packet(Port *port, char **logdetail)
+CheckPasswordAuth(Port *port, char **logdetail)
 {
 	char	   *passwd;
 	int			result;
 
+	sendAuthRequest(port, AUTH_REQ_PASSWORD, NULL, 0);
+
 	passwd = recv_password_packet(port);
 
 	if (passwd == NULL)
 		return STATUS_EOF;		/* client wouldn't send password */
 
-	result = md5_crypt_verify(port, port->user_name, passwd, logdetail);
+	result = md5_crypt_verify(port, port->user_name, passwd, NULL, 0, logdetail);
 
 	pfree(passwd);
 
@@ -920,7 +956,7 @@ pg_GSS_recvauth(Port *port)
 				 (unsigned int) port->gss->outbuf.length);
 
 			sendAuthRequest(port, AUTH_REQ_GSS_CONT,
-							port->gss->outbuf.value, port->gss->outbuf.length);
+						  port->gss->outbuf.value, port->gss->outbuf.length);
 
 			gss_release_buffer(&lmin_s, &port->gss->outbuf);
 		}
@@ -1166,7 +1202,7 @@ pg_SSPI_recvauth(Port *port)
 			port->gss->outbuf.value = outbuf.pBuffers[0].pvBuffer;
 
 			sendAuthRequest(port, AUTH_REQ_GSS_CONT,
-							port->gss->outbuf.value, port->gss->outbuf.length);
+						  port->gss->outbuf.value, port->gss->outbuf.length);
 
 			FreeContextBuffer(outbuf.pBuffers[0].pvBuffer);
 		}
diff --git a/src/backend/libpq/crypt.c b/src/backend/libpq/crypt.c
index d84a1803304..35b657adbbe 100644
--- a/src/backend/libpq/crypt.c
+++ b/src/backend/libpq/crypt.c
@@ -36,7 +36,7 @@
  */
 int
 md5_crypt_verify(const Port *port, const char *role, char *client_pass,
-				 char **logdetail)
+				 char *md5_salt, int md5_salt_len, char **logdetail)
 {
 	int			retval = STATUS_ERROR;
 	char	   *shadow_pass,
@@ -91,13 +91,14 @@ md5_crypt_verify(const Port *port, const char *role, char *client_pass,
 	switch (port->hba->auth_method)
 	{
 		case uaMD5:
+			Assert(md5_salt != NULL && md5_salt_len > 0);
 			crypt_pwd = palloc(MD5_PASSWD_LEN + 1);
 			if (isMD5(shadow_pass))
 			{
 				/* stored password already encrypted, only do salt */
 				if (!pg_md5_encrypt(shadow_pass + strlen("md5"),
-									port->md5Salt,
-									sizeof(port->md5Salt), crypt_pwd))
+									md5_salt, md5_salt_len,
+									crypt_pwd))
 				{
 					pfree(crypt_pwd);
 					return STATUS_ERROR;
@@ -118,8 +119,7 @@ md5_crypt_verify(const Port *port, const char *role, char *client_pass,
 					return STATUS_ERROR;
 				}
 				if (!pg_md5_encrypt(crypt_pwd2 + strlen("md5"),
-									port->md5Salt,
-									sizeof(port->md5Salt),
+									md5_salt, md5_salt_len,
 									crypt_pwd))
 				{
 					pfree(crypt_pwd);
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index 24add74512f..f0ed5233711 100644
--- a/src/backend/postmaster/postmaster.c
+++ b/src/backend/postmaster/postmaster.c
@@ -164,7 +164,7 @@
 typedef struct bkend
 {
 	pid_t		pid;			/* process id of backend */
-	long		cancel_key;		/* cancel key for cancels for this backend */
+	int32		cancel_key;		/* cancel key for cancels for this backend */
 	int			child_slot;		/* PMChildSlot for this backend, if any */
 
 	/*
@@ -358,13 +358,15 @@ static volatile bool avlauncher_needs_signal = false;
 static volatile bool StartWorkerNeeded = true;
 static volatile bool HaveCrashedWorker = false;
 
+#ifndef HAVE_STRONG_RANDOM
 /*
- * State for assigning random salts and cancel keys.
+ * State for assigning cancel keys.
  * Also, the global MyCancelKey passes the cancel key assigned to a given
  * backend from the postmaster to that backend (via fork).
  */
 static unsigned int random_seed = 0;
 static struct timeval random_start_time;
+#endif
 
 #ifdef USE_BONJOUR
 static DNSServiceRef bonjour_sdref = NULL;
@@ -403,8 +405,7 @@ static void processCancelRequest(Port *port, void *pkt);
 static int	initMasks(fd_set *rmask);
 static void report_fork_failure_to_client(Port *port, int errnum);
 static CAC_state canAcceptConnections(void);
-static long PostmasterRandom(void);
-static void RandomSalt(char *salt, int len);
+static bool RandomCancelKey(int32 *cancel_key);
 static void signal_child(pid_t pid, int signal);
 static bool SignalSomeChildren(int signal, int targets);
 static void TerminateChildren(int signal);
@@ -471,7 +472,7 @@ typedef struct
 	InheritableSocket portsocket;
 	char		DataDir[MAXPGPATH];
 	pgsocket	ListenSocket[MAXLISTEN];
-	long		MyCancelKey;
+	int32		MyCancelKey;
 	int			MyPMChildSlot;
 #ifndef WIN32
 	unsigned long UsedShmemSegID;
@@ -1292,8 +1293,10 @@ PostmasterMain(int argc, char *argv[])
 	 * Remember postmaster startup time
 	 */
 	PgStartTime = GetCurrentTimestamp();
-	/* PostmasterRandom wants its own copy */
+#ifndef HAVE_STRONG_RANDOM
+	/* RandomCancelKey wants its own copy */
 	gettimeofday(&random_start_time, NULL);
+#endif
 
 	/*
 	 * We're ready to rock and roll...
@@ -2345,15 +2348,6 @@ ConnCreate(int serverFd)
 	}
 
 	/*
-	 * Precompute password salt values to use for this connection. It's
-	 * slightly annoying to do this long in advance of knowing whether we'll
-	 * need 'em or not, but we must do the random() calls before we fork, not
-	 * after.  Else the postmaster's random sequence won't get advanced, and
-	 * all backends would end up using the same salt...
-	 */
-	RandomSalt(port->md5Salt, sizeof(port->md5Salt));
-
-	/*
 	 * Allocate GSSAPI specific state struct
 	 */
 #ifndef EXEC_BACKEND
@@ -3905,7 +3899,14 @@ BackendStartup(Port *port)
 	 * backend will have its own copy in the forked-off process' value of
 	 * MyCancelKey, so that it can transmit the key to the frontend.
 	 */
-	MyCancelKey = PostmasterRandom();
+	if (!RandomCancelKey(&MyCancelKey))
+	{
+		ereport(LOG,
+				(errcode(ERRCODE_OUT_OF_MEMORY),
+				 errmsg("could not acquire random number")));
+		return STATUS_ERROR;
+	}
+
 	bn->cancel_key = MyCancelKey;
 
 	/* Pass down canAcceptConnections state */
@@ -4218,8 +4219,10 @@ BackendRun(Port *port)
 	 * generator state.  We have to clobber the static random_seed *and* start
 	 * a new random sequence in the random() library function.
 	 */
+#ifndef HAVE_STRONG_RANDOM
 	random_seed = 0;
 	random_start_time.tv_usec = 0;
+#endif
 	/* slightly hacky way to convert timestamptz into integers */
 	TimestampDifference(0, port->SessionStartTime, &secs, &usecs);
 	srandom((unsigned int) (MyProcPid ^ (usecs << 12) ^ secs));
@@ -5068,63 +5071,42 @@ StartupPacketTimeoutHandler(void)
 
 
 /*
- * RandomSalt
+ * Generate a random cancel key.
  */
-static void
-RandomSalt(char *salt, int len)
+static bool
+RandomCancelKey(int32 *cancel_key)
 {
-	long		rand;
-	int			i;
-
+#ifdef HAVE_STRONG_RANDOM
+	return pg_strong_random((char *) cancel_key, sizeof(int32));
+#else
 	/*
-	 * We use % 255, sacrificing one possible byte value, so as to ensure that
-	 * all bits of the random() value participate in the result. While at it,
-	 * add one to avoid generating any null bytes.
+	 * If built with --disable-strong-random, use plain old erand48.
+	 *
+	 * We cannot use pg_backend_random() in postmaster, because it stores
+	 * its state in shared memory.
 	 */
-	for (i = 0; i < len; i++)
-	{
-		rand = PostmasterRandom();
-		salt[i] = (rand % 255) + 1;
-	}
-}
+	static unsigned short seed[3];
 
-/*
- * PostmasterRandom
- *
- * Caution: use this only for values needed during connection-request
- * processing.  Otherwise, the intended property of having an unpredictable
- * delay between random_start_time and random_stop_time will be broken.
- */
-static long
-PostmasterRandom(void)
-{
 	/*
 	 * Select a random seed at the time of first receiving a request.
 	 */
 	if (random_seed == 0)
 	{
-		do
-		{
-			struct timeval random_stop_time;
+		struct timeval random_stop_time;
 
-			gettimeofday(&random_stop_time, NULL);
+		gettimeofday(&random_stop_time, NULL);
 
-			/*
-			 * We are not sure how much precision is in tv_usec, so we swap
-			 * the high and low 16 bits of 'random_stop_time' and XOR them
-			 * with 'random_start_time'. On the off chance that the result is
-			 * 0, we loop until it isn't.
-			 */
-			random_seed = random_start_time.tv_usec ^
-				((random_stop_time.tv_usec << 16) |
-				 ((random_stop_time.tv_usec >> 16) & 0xffff));
-		}
-		while (random_seed == 0);
+		seed[0] = (unsigned short) random_start_time.tv_usec;
+		seed[1] = (unsigned short) (random_stop_time.tv_usec) ^ (random_start_time.tv_usec >> 16);
+		seed[2] = (unsigned short) (random_stop_time.tv_usec >> 16);
 
-		srandom(random_seed);
+		random_seed = 1;
 	}
 
-	return random();
+	*cancel_key = pg_jrand48(seed);
+
+	return true;
+#endif
 }
 
 /*
@@ -5295,16 +5277,23 @@ StartAutovacuumWorker(void)
 	 */
 	if (canAcceptConnections() == CAC_OK)
 	{
+		/*
+		 * Compute the cancel key that will be assigned to this session.
+		 * We probably don't need cancel keys for autovac workers, but
+		 * we'd better have something random in the field to prevent
+		 * unfriendly people from sending cancels to them.
+		 */
+		if (!RandomCancelKey(&MyCancelKey))
+		{
+			ereport(LOG,
+					(errcode(ERRCODE_INTERNAL_ERROR),
+					 errmsg("could not acquire random number")));
+			return;
+		}
+
 		bn = (Backend *) malloc(sizeof(Backend));
 		if (bn)
 		{
-			/*
-			 * Compute the cancel key that will be assigned to this session.
-			 * We probably don't need cancel keys for autovac workers, but
-			 * we'd better have something random in the field to prevent
-			 * unfriendly people from sending cancels to them.
-			 */
-			MyCancelKey = PostmasterRandom();
 			bn->cancel_key = MyCancelKey;
 
 			/* Autovac workers are not dead_end and need a child slot */
@@ -5592,8 +5581,25 @@ bgworker_should_start_now(BgWorkerStartTime start_time)
 static bool
 assign_backendlist_entry(RegisteredBgWorker *rw)
 {
-	Backend    *bn = malloc(sizeof(Backend));
+	Backend    *bn;
 
+	/*
+	 * Compute the cancel key that will be assigned to this session. We
+	 * probably don't need cancel keys for background workers, but we'd better
+	 * have something random in the field to prevent unfriendly people from
+	 * sending cancels to them.
+	 */
+	if (!RandomCancelKey(&MyCancelKey))
+	{
+		ereport(LOG,
+				(errcode(ERRCODE_INTERNAL_ERROR),
+				 errmsg("could not acquire random number")));
+
+		rw->rw_crashed_at = GetCurrentTimestamp();
+		return false;
+	}
+
+	bn = malloc(sizeof(Backend));
 	if (bn == NULL)
 	{
 		ereport(LOG,
@@ -5610,15 +5616,7 @@ assign_backendlist_entry(RegisteredBgWorker *rw)
 		return false;
 	}
 
-	/*
-	 * Compute the cancel key that will be assigned to this session. We
-	 * probably don't need cancel keys for background workers, but we'd better
-	 * have something random in the field to prevent unfriendly people from
-	 * sending cancels to them.
-	 */
-	MyCancelKey = PostmasterRandom();
 	bn->cancel_key = MyCancelKey;
-
 	bn->child_slot = MyPMChildSlot = AssignPostmasterChildSlot();
 	bn->bkend_type = BACKEND_TYPE_BGWORKER;
 	bn->dead_end = false;
diff --git a/src/backend/storage/ipc/ipci.c b/src/backend/storage/ipc/ipci.c
index c04b17fa8ea..01bddcea16c 100644
--- a/src/backend/storage/ipc/ipci.c
+++ b/src/backend/storage/ipc/ipci.c
@@ -43,6 +43,7 @@
 #include "storage/procsignal.h"
 #include "storage/sinvaladt.h"
 #include "storage/spin.h"
+#include "utils/backend_random.h"
 #include "utils/snapmgr.h"
 
 
@@ -141,6 +142,7 @@ CreateSharedMemoryAndSemaphores(bool makePrivate, int port)
 		size = add_size(size, BTreeShmemSize());
 		size = add_size(size, SyncScanShmemSize());
 		size = add_size(size, AsyncShmemSize());
+		size = add_size(size, BackendRandomShmemSize());
 #ifdef EXEC_BACKEND
 		size = add_size(size, ShmemBackendArraySize());
 #endif
@@ -253,6 +255,7 @@ CreateSharedMemoryAndSemaphores(bool makePrivate, int port)
 	BTreeShmemInit();
 	SyncScanShmemInit();
 	AsyncShmemInit();
+	BackendRandomShmemInit();
 
 #ifdef EXEC_BACKEND
 
diff --git a/src/backend/storage/lmgr/lwlocknames.txt b/src/backend/storage/lmgr/lwlocknames.txt
index f8996cd21a5..0dcf7effd41 100644
--- a/src/backend/storage/lmgr/lwlocknames.txt
+++ b/src/backend/storage/lmgr/lwlocknames.txt
@@ -47,3 +47,4 @@ CommitTsLock						39
 ReplicationOriginLock				40
 MultiXactTruncationLock				41
 OldSnapshotTimeMapLock				42
+BackendRandomLock				43
diff --git a/src/backend/utils/init/globals.c b/src/backend/utils/init/globals.c
index c564ae396da..6ab03cea170 100644
--- a/src/backend/utils/init/globals.c
+++ b/src/backend/utils/init/globals.c
@@ -38,7 +38,7 @@ volatile uint32 CritSectionCount = 0;
 int			MyProcPid;
 pg_time_t	MyStartTime;
 struct Port *MyProcPort;
-long		MyCancelKey;
+int32		MyCancelKey;
 int			MyPMChildSlot;
 
 /*
diff --git a/src/backend/utils/misc/Makefile b/src/backend/utils/misc/Makefile
index a5b487d0b64..0ad1b8b5954 100644
--- a/src/backend/utils/misc/Makefile
+++ b/src/backend/utils/misc/Makefile
@@ -14,8 +14,9 @@ include $(top_builddir)/src/Makefile.global
 
 override CPPFLAGS := -I. -I$(srcdir) $(CPPFLAGS)
 
-OBJS = guc.o help_config.o pg_config.o pg_controldata.o pg_rusage.o \
-       ps_status.o rls.o sampling.o superuser.o timeout.o tzparser.o
+OBJS = backend_random.o guc.o help_config.o pg_config.o pg_controldata.o \
+       pg_rusage.o ps_status.o rls.o sampling.o superuser.o timeout.o \
+       tzparser.o
 
 # This location might depend on the installation directories. Therefore
 # we can't subsitute it into pg_config.h.
diff --git a/src/backend/utils/misc/backend_random.c b/src/backend/utils/misc/backend_random.c
new file mode 100644
index 00000000000..1bc239d1ddc
--- /dev/null
+++ b/src/backend/utils/misc/backend_random.c
@@ -0,0 +1,158 @@
+/*-------------------------------------------------------------------------
+ *
+ * backend_random.c
+ *	  Backend random number generation routine.
+ *
+ * pg_backend_random() function fills a buffer with random bytes. Normally,
+ * it is just a thin wrapper around pg_strong_random(), but when compiled
+ * with --disable-strong-random, we provide a built-in implementation.
+ *
+ * This function is used for generating nonces in authentication, and for
+ * random salt generation in pgcrypto. The built-in implementation is not
+ * cryptographically strong, but if the user asked for it, we'll go ahead
+ * and use it anyway.
+ *
+ * The built-in implementation uses the standard erand48 algorithm, with
+ * a seed shared between all backends.
+ *
+ * Portions Copyright (c) 1996-2016, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  src/backend/utils/misc/backend_random.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include <sys/time.h>
+
+#include "miscadmin.h"
+#include "storage/lwlock.h"
+#include "storage/shmem.h"
+#include "utils/backend_random.h"
+#include "utils/timestamp.h"
+
+#ifdef HAVE_STRONG_RANDOM
+
+Size
+BackendRandomShmemSize(void)
+{
+	return 0;
+}
+
+void
+BackendRandomShmemInit(void)
+{
+	/* do nothing */
+}
+
+bool
+pg_backend_random(char *dst, int len)
+{
+	/* should not be called in postmaster */
+	Assert (IsUnderPostmaster || !IsPostmasterEnvironment);
+
+	return pg_strong_random(dst, len);
+}
+
+#else
+
+/*
+ * Seed for the PRNG, stored in shared memory.
+ *
+ * Protected by BackendRandomLock.
+ */
+typedef struct
+{
+	bool		initialized;
+	unsigned short seed[3];
+} BackendRandomShmemStruct;
+
+static BackendRandomShmemStruct *BackendRandomShmem;
+
+Size
+BackendRandomShmemSize(void)
+{
+	return sizeof(BackendRandomShmemStruct);
+}
+
+void
+BackendRandomShmemInit(void)
+{
+	bool		found;
+
+	BackendRandomShmem = (BackendRandomShmemStruct *)
+		ShmemInitStruct("Backend PRNG state",
+						BackendRandomShmemSize(),
+						&found);
+
+	if (!IsUnderPostmaster)
+	{
+		Assert(!found);
+
+		BackendRandomShmem->initialized = false;
+	}
+	else
+		Assert(found);
+}
+
+bool
+pg_backend_random(char *dst, int len)
+{
+	int			i;
+	char	   *end = dst + len;
+
+	/* should not be called in postmaster */
+	Assert (IsUnderPostmaster || !IsPostmasterEnvironment);
+
+	LWLockAcquire(BackendRandomLock, LW_EXCLUSIVE);
+
+	/*
+	 * Seed the PRNG on the first use.
+	 */
+	if (!BackendRandomShmem->initialized)
+	{
+		struct timeval now;
+
+		gettimeofday(&now, NULL);
+
+		BackendRandomShmem->seed[0] = now.tv_sec;
+		BackendRandomShmem->seed[1] = (unsigned short) (now.tv_usec);
+		BackendRandomShmem->seed[2] = (unsigned short) (now.tv_usec >> 16);
+
+		/*
+		 * Mix in the cancel key, generated by the postmaster. This adds
+		 * what little entropy the postmaster had to the seed.
+		 */
+		BackendRandomShmem->seed[0] ^= (MyCancelKey);
+		BackendRandomShmem->seed[1] ^= (MyCancelKey >> 16);
+
+		BackendRandomShmem->initialized = true;
+	}
+
+	for (i = 0; dst < end; i++)
+	{
+		uint32		r;
+		int			j;
+
+		/*
+		 * pg_jrand48 returns a 32-bit integer. Fill the next 4 bytes from it.
+		 */
+		r  = (uint32) pg_jrand48(BackendRandomShmem->seed);
+
+		for (j = 0; j < 4 && dst < end; j++)
+		{
+			*(dst++) = (char) (r & 0xFF);
+			r >>= 8;
+		}
+	}
+	LWLockRelease(BackendRandomLock);
+
+	return true;
+}
+
+
+#endif /* HAVE_STRONG_RANDOM */
diff --git a/src/include/libpq/crypt.h b/src/include/libpq/crypt.h
index 5725bb409e8..f51e0fd46b6 100644
--- a/src/include/libpq/crypt.h
+++ b/src/include/libpq/crypt.h
@@ -16,6 +16,6 @@
 #include "libpq/libpq-be.h"
 
 extern int md5_crypt_verify(const Port *port, const char *role,
-				 char *client_pass, char **logdetail);
+				 char *client_pass, char *md5_salt, int md5_salt_len, char **logdetail);
 
 #endif
diff --git a/src/include/libpq/libpq-be.h b/src/include/libpq/libpq-be.h
index b91eca5b2c1..66647ad0032 100644
--- a/src/include/libpq/libpq-be.h
+++ b/src/include/libpq/libpq-be.h
@@ -144,7 +144,6 @@ typedef struct Port
 	 * Information that needs to be held during the authentication cycle.
 	 */
 	HbaLine    *hba;
-	char		md5Salt[4];		/* Password salt */
 
 	/*
 	 * Information that really has no business at all being in struct Port,
diff --git a/src/include/miscadmin.h b/src/include/miscadmin.h
index d06eca54b46..999440fdec1 100644
--- a/src/include/miscadmin.h
+++ b/src/include/miscadmin.h
@@ -163,7 +163,7 @@ extern PGDLLIMPORT int MyProcPid;
 extern PGDLLIMPORT pg_time_t MyStartTime;
 extern PGDLLIMPORT struct Port *MyProcPort;
 extern PGDLLIMPORT struct Latch *MyLatch;
-extern long MyCancelKey;
+extern int32 MyCancelKey;
 extern int	MyPMChildSlot;
 
 extern char OutputFileName[];
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 7dbfa90bf49..42a3fc862e9 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -497,6 +497,9 @@
 /* Define to 1 if you have the `strlcpy' function. */
 #undef HAVE_STRLCPY
 
+/* Define to use have a strong random number source */
+#undef HAVE_STRONG_RANDOM
+
 /* Define to 1 if you have the `strtoll' function. */
 #undef HAVE_STRTOLL
 
@@ -814,6 +817,9 @@
 /* Define to 1 to build with BSD Authentication support. (--with-bsd-auth) */
 #undef USE_BSD_AUTH
 
+/* Define to use /dev/urandom for random number generation */
+#undef USE_DEV_URANDOM
+
 /* Define to 1 if you want float4 values to be passed by value.
    (--enable-float4-byval) */
 #undef USE_FLOAT4_BYVAL
@@ -842,6 +848,9 @@
 /* Define to build with OpenSSL support. (--with-openssl) */
 #undef USE_OPENSSL
 
+/* Define to use OpenSSL for random number generation */
+#undef USE_OPENSSL_RANDOM
+
 /* Define to 1 to build with PAM support. (--with-pam) */
 #undef USE_PAM
 
@@ -869,6 +878,9 @@
 /* Define to select unnamed POSIX semaphores. */
 #undef USE_UNNAMED_POSIX_SEMAPHORES
 
+/* Define to use native Windows API for random number generation */
+#undef USE_WIN32_RANDOM
+
 /* Define to select Win32-style semaphores. */
 #undef USE_WIN32_SEMAPHORES
 
diff --git a/src/include/pg_config.h.win32 b/src/include/pg_config.h.win32
index 8892c3cb4fa..ceb8b7956ee 100644
--- a/src/include/pg_config.h.win32
+++ b/src/include/pg_config.h.win32
@@ -348,6 +348,9 @@
 /* Define to 1 if you have the <string.h> header file. */
 #define HAVE_STRING_H 1
 
+/* Define to use have a strong random number source */
+#define HAVE_STRONG_RANDOM 1
+
 /* Define to 1 if you have the `strtoll' function. */
 //#define HAVE_STRTOLL 1
 
@@ -616,6 +619,9 @@
 /* Define to 1 to build with BSD Authentication support. (--with-bsd-auth) */
 /* #undef USE_BSD_AUTH */
 
+/* Define to use /dev/urandom for random number generation */
+/* #undef USE_DEV_URANDOM */
+
 /* Define to 1 if you want 64-bit integer timestamp and interval support.
    (--enable-integer-datetimes) */
 /* #undef USE_INTEGER_DATETIMES */
@@ -629,6 +635,9 @@
 /* Define to build with OpenSSL support. (--with-openssl) */
 /* #undef USE_OPENSSL */
 
+/* Define to use OpenSSL for random number generation */
+/* #undef USE_OPENSSL_RANDOM */
+
 /* Define to 1 to build with PAM support. (--with-pam) */
 /* #undef USE_PAM */
 
@@ -657,6 +666,9 @@
 /* Define to select unnamed POSIX semaphores. */
 /* #undef USE_UNNAMED_POSIX_SEMAPHORES */
 
+/* Define to use native Windows API for random number generation */
+#define USE_WIN32_RANDOM 1
+
 /* Define to select Win32-style semaphores. */
 #define USE_WIN32_SEMAPHORES 1
 
diff --git a/src/include/port.h b/src/include/port.h
index 8a63958535b..f2b9882b7b7 100644
--- a/src/include/port.h
+++ b/src/include/port.h
@@ -361,6 +361,7 @@ extern off_t ftello(FILE *stream);
 
 extern double pg_erand48(unsigned short xseed[3]);
 extern long pg_lrand48(void);
+extern long pg_jrand48(unsigned short xseed[3]);
 extern void pg_srand48(long seed);
 
 #ifndef HAVE_FLS
@@ -454,6 +455,11 @@ extern int	pg_codepage_to_encoding(UINT cp);
 extern char *inet_net_ntop(int af, const void *src, int bits,
 			  char *dst, size_t size);
 
+/* port/pg_strong_random.c */
+#ifdef HAVE_STRONG_RANDOM
+extern bool pg_strong_random(void *buf, size_t len);
+#endif
+
 /* port/pgcheckdir.c */
 extern int	pg_check_dir(const char *dir);
 
diff --git a/src/include/utils/backend_random.h b/src/include/utils/backend_random.h
new file mode 100644
index 00000000000..16a6a26523d
--- /dev/null
+++ b/src/include/utils/backend_random.h
@@ -0,0 +1,19 @@
+/*-------------------------------------------------------------------------
+ *
+ * backend_random.h
+ *		Declarations for backend random number generation
+ *
+ * Portions Copyright (c) 1996-2016, PostgreSQL Global Development Group
+ *
+ *	  src/include/utils/backend_random.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef BACKEND_RANDOM_H
+#define BACKEND_RANDOM_H
+
+extern Size BackendRandomShmemSize(void);
+extern void BackendRandomShmemInit(void);
+extern bool pg_backend_random(char *dst, int len);
+
+#endif   /* BACKEND_RANDOM_H */
diff --git a/src/port/Makefile b/src/port/Makefile
index bc9b63add04..81f01b25bbc 100644
--- a/src/port/Makefile
+++ b/src/port/Makefile
@@ -35,6 +35,10 @@ OBJS = $(LIBOBJS) $(PG_CRC32C_OBJS) chklocale.o erand48.o inet_net_ntop.o \
 	pgstrcasecmp.o pqsignal.o \
 	qsort.o qsort_arg.o quotes.o sprompt.o tar.o thread.o
 
+ifeq ($(enable_strong_random), yes)
+OBJS += pg_strong_random.o
+endif
+
 # foo_srv.o and foo.o are both built from foo.c, but only foo.o has -DFRONTEND
 OBJS_SRV = $(OBJS:%.o=%_srv.o)
 
diff --git a/src/port/erand48.c b/src/port/erand48.c
index 9d471197c35..716816bc361 100644
--- a/src/port/erand48.c
+++ b/src/port/erand48.c
@@ -91,6 +91,13 @@ pg_lrand48(void)
 	return ((long) _rand48_seed[2] << 15) + ((long) _rand48_seed[1] >> 1);
 }
 
+long
+pg_jrand48(unsigned short xseed[3])
+{
+	_dorand48(xseed);
+	return ((long) xseed[2] << 16) + ((long) xseed[1]);
+}
+
 void
 pg_srand48(long seed)
 {
diff --git a/src/port/pg_strong_random.c b/src/port/pg_strong_random.c
new file mode 100644
index 00000000000..6d3aa38efdd
--- /dev/null
+++ b/src/port/pg_strong_random.c
@@ -0,0 +1,149 @@
+/*-------------------------------------------------------------------------
+ *
+ * pg_strong_random.c
+ *	  generate a cryptographically secure random number
+ *
+ * Our definition of "strong" is that it's suitable for generating random
+ * salts and query cancellation keys, during authentication.
+ *
+ * Copyright (c) 1996-2016, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/port/pg_strong_random.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#ifndef FRONTEND
+#include "postgres.h"
+#else
+#include "postgres_fe.h"
+#endif
+
+#include <fcntl.h>
+#include <unistd.h>
+#include <sys/time.h>
+
+#ifdef USE_OPENSSL
+#include <openssl/rand.h>
+#endif
+#ifdef WIN32
+#include <Wincrypt.h>
+#endif
+
+#ifdef WIN32
+/*
+ * Cache a global crypto provider that only gets freed when the process
+ * exits, in case we need random numbers more than once.
+ */
+static HCRYPTPROV hProvider = 0;
+#endif
+
+#if defined(USE_DEV_URANDOM)
+/*
+ * Read (random) bytes from a file.
+ */
+static bool
+random_from_file(char *filename, void *buf, size_t len)
+{
+	int			f;
+	char	   *p = buf;
+	ssize_t		res;
+
+	f = open(filename, O_RDONLY, 0);
+	if (f == -1)
+		return false;
+
+	while (len)
+	{
+		res = read(f, p, len);
+		if (res <= 0)
+		{
+			if (errno == EINTR)
+				continue;		/* interrupted by signal, just retry */
+
+			close(f);
+			return false;
+		}
+
+		p += res;
+		len -= res;
+	}
+
+	close(f);
+	return true;
+}
+#endif
+
+/*
+ * pg_strong_random
+ *
+ * Generate requested number of random bytes. The returned bytes are
+ * cryptographically secure, suitable for use e.g. in authentication.
+ *
+ * We rely on system facilities for actually generating the numbers.
+ * We support a number of sources:
+ *
+ * 1. OpenSSL's RAND_bytes()
+ * 2. Windows' CryptGenRandom() function
+ * 3. /dev/urandom
+ *
+ * The configure script will choose which one to use, and set
+ * a USE_*_RANDOM flag accordingly.
+ *
+ * Returns true on success, and false if none of the sources
+ * were available. NB: It is important to check the return value!
+ * Proceeding with key generation when no random data was available
+ * would lead to predictable keys and security issues.
+ */
+bool
+pg_strong_random(void *buf, size_t len)
+{
+	/*
+	 * When built with OpenSSL, use OpenSSL's RAND_bytes function.
+	 */
+#if defined(USE_OPENSSL_RANDOM)
+	if (RAND_bytes(buf, len) == 1)
+		return true;
+	return false;
+
+	/*
+	 * Windows has CryptoAPI for strong cryptographic numbers.
+	 */
+#elif defined(USE_WIN32_RANDOM)
+	if (hProvider == 0)
+	{
+		if (!CryptAcquireContext(&hProvider,
+								 NULL,
+								 MS_DEF_PROV,
+								 PROV_RSA_FULL,
+								 CRYPT_VERIFYCONTEXT | CRYPT_SILENT))
+		{
+			/*
+			 * On failure, set back to 0 in case the value was for some reason
+			 * modified.
+			 */
+			hProvider = 0;
+		}
+	}
+	/* Re-check in case we just retrieved the provider */
+	if (hProvider != 0)
+	{
+		if (CryptGenRandom(hProvider, len, buf))
+			return true;
+	}
+	return false;
+
+	/*
+	 * Read /dev/urandom ourselves.
+	 */
+#elif defined(USE_DEV_URANDOM)
+	if (random_from_file("/dev/urandom", buf, len))
+		return true;
+	return false;
+
+#else
+	/* The autoconf script should not have allowed this */
+#error no source of random numbers configured
+#endif
+}
diff --git a/src/tools/msvc/Mkvcbuild.pm b/src/tools/msvc/Mkvcbuild.pm
index de764dd4d44..db566f9c88c 100644
--- a/src/tools/msvc/Mkvcbuild.pm
+++ b/src/tools/msvc/Mkvcbuild.pm
@@ -91,8 +91,8 @@ sub mkvcbuild
 	  chklocale.c crypt.c fls.c fseeko.c getrusage.c inet_aton.c random.c
 	  srandom.c getaddrinfo.c gettimeofday.c inet_net_ntop.c kill.c open.c
 	  erand48.c snprintf.c strlcat.c strlcpy.c dirmod.c noblock.c path.c
-	  pgcheckdir.c pgmkdirp.c pgsleep.c pgstrcasecmp.c pqsignal.c
-	  mkdtemp.c qsort.c qsort_arg.c quotes.c system.c
+	  pg_strong_random.c pgcheckdir.c pgmkdirp.c pgsleep.c pgstrcasecmp.c
+	  pqsignal.c mkdtemp.c qsort.c qsort_arg.c quotes.c system.c
 	  sprompt.c tar.c thread.c getopt.c getopt_long.c dirent.c
 	  win32env.c win32error.c win32security.c win32setlocale.c);
 
@@ -425,7 +425,6 @@ sub mkvcbuild
 			'sha1.c',             'sha2.c',
 			'internal.c',         'internal-sha2.c',
 			'blf.c',              'rijndael.c',
-			'fortuna.c',          'random.c',
 			'pgp-mpi-internal.c', 'imath.c');
 	}
 	$pgcrypto->AddReference($postgres);