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);