Random number generation, take two

Started by Heikki Linnakangasabout 9 years ago12 messages

hlinnaka@iki.fi

about 9 years ago

1 attachment(s)

Ok, here's my second attempt at refactoring random number generation.
Previous attempt crashed and burned, see
/messages/by-id/E1bw3g3-0003st-6M@gemulon.postgresql.org.
This addresses the issues pointed out in that thread.

The goals are:

* Have a pg_strong_random() function available in both frontend and
backend. (Frontend support needed by upcoming SCRAM patches)

* Use a stronger generator for query cancel keys and MD5 salts than
PostmasterRandom() that's used today.

* Still work on platforms that don't have a supported random source.

Autoconf
--------

* Configure chooses the implementation to use: OpenSSL, Windows native,
or /dev/urandom, in that order. You can also force it, by specifying
USE_OPENSSL_RANDOM=1, USE_WIN32_RANDOM=1 or USE_DEV_URANDOM=1 on the
configure command line. That's useful for testing.

This is better than trying all the options at runtime, because it's
better to fail early, at configure. Also, if e.g. OpenSSL's RAND_bytes()
for some reason fails at runtime, you don't want to silently fall back
to reading /dev/urandom. It really shouldn't fail in the first place, so
we'd rather fail visibly so that the admin or developer can investigate.

The auto-detection will not work when cross-compiling, because checking
for the presence of /dev/urandom on the build host doesn't tell us
whether it will be present in the target. autoconf will give an error,
but you can override that with USE_DEV_URANDOM=1.

* On platforms that don't have OpenSSL nor /dev/urandom (Tom's HP-UX
box, pademelon), configure will error out. But you can use
--disable-strong-random to fall back to a less-secure built-in
implementation. This is not done automatically, to avoid falling back to
a less secure implementation by accident.

* When building with --disable-strong-random, the pg_strong_random()
function is not available at all. Callers need to use #ifdef
HAVE_STRONG_RANDOM blocks if they want to use a fallback. This is again
to make sure that no extension, or built-in code either for that matter,
will accidentally fall back to the less secure implementation.

* Remove the support for /dev/random (only support /dev/urandom). I
don't think we have any platforms where /dev/urandom is not present, but
/dev/random is. If we do, the buildfarm will tell us, but until then
let's keep it simple.

Fallback implementation (with --disable-strong-random)
-----------

In postmaster, the algorithm is similar to the existing
PostmasterRandom() function. It's based on the built-in PRNG, seeded by
postmaster and first backend start time. It's been rewritten to fit the
rest of the code better, however.

In backends, there is a new function, pg_backend_random(). It also uses
the built-in PRNG, but the seed is shared between all backends, in
shared memory. (Otherwise all backends would inherit the same seed from
postmaster.)

pgcrypto
--------

pgcrypto doesn't have the same requirements for "strongness" as cancel
keys and MD5 salts have. pgcrypto uses random numbers for generating
salts, too, which I think has similar requirements. But it also uses
random numbers for generating encryption keys, which I believe ought to
be harder to predict. If you compile with --disable-strong-random, do we
want the encryption key generation routines to fail, or to return
known-weak keys?

This patch removes the Fortuna algorithm, that was used to generate
fairly strong random numbers, if OpenSSL was not present. One option
would be to keep that code as a fallback. I wanted to get rid of that,
since it's only used on a few old platforms, but OTOH it's been around
for a long time with little issues.

As this patch stands, it removes Fortuna, and returns known-weak keys,
but there's a good argument to be made for throwing an error instead.

Phew, this has been way more complicated than it seemed at first. Thoughts?

- Heikki

Attachments:

0001-Replace-PostmasterRandom-with-a-stronger-source-seco.patchapplication/x-download; name=0001-Replace-PostmasterRandom-with-a-stronger-source-seco.patchDownload

From 41e3a8367144ac49c0629d9764a82c4191ef2844 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Tue, 29 Nov 2016 13:36:40 +0200
Subject: [PATCH 1/1] 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.

This also includes a simple built-in implementation based on erand48(),
which isn't really 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 implementatio 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.

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

Discussion: <CAB7nPqRy3krN8quR9XujMVVHYtXJ0_60nqgVc6oUk8ygyVkZsA@mail.gmail.com>
---
 configure                                | 109 ++++++++
 configure.in                             |  52 ++++
 contrib/pgcrypto/Makefile                |   2 +-
 contrib/pgcrypto/fortuna.c               | 463 -------------------------------
 contrib/pgcrypto/fortuna.h               |  38 ---
 contrib/pgcrypto/internal.c              |  63 -----
 contrib/pgcrypto/openssl.c               |  46 ---
 contrib/pgcrypto/pgcrypto.c              |  13 +-
 contrib/pgcrypto/pgp-encrypt.c           |  14 +-
 contrib/pgcrypto/pgp-mpi-internal.c      |   8 +-
 contrib/pgcrypto/pgp-pgsql.c             |  69 -----
 contrib/pgcrypto/pgp-pubenc.c            |  15 +-
 contrib/pgcrypto/pgp-s2k.c               |  15 +-
 contrib/pgcrypto/px-crypt.c              |   7 +-
 contrib/pgcrypto/px.h                    |   5 -
 src/Makefile.global.in                   |   1 +
 src/backend/libpq/auth.c                 |  62 ++++-
 src/backend/libpq/crypt.c                |  10 +-
 src/backend/postmaster/postmaster.c      | 145 +++++-----
 src/backend/storage/ipc/ipci.c           |   3 +
 src/backend/storage/lmgr/lwlocknames.txt |   1 +
 src/backend/utils/init/globals.c         |   2 +-
 src/backend/utils/misc/Makefile          |   5 +-
 src/backend/utils/misc/backend_random.c  | 158 +++++++++++
 src/include/libpq/crypt.h                |   2 +-
 src/include/libpq/libpq-be.h             |   1 -
 src/include/miscadmin.h                  |   2 +-
 src/include/pg_config.h.in               |  12 +
 src/include/port.h                       |   6 +
 src/include/utils/backend_random.h       |  19 ++
 src/port/Makefile                        |   4 +
 src/port/erand48.c                       |   7 +
 src/port/pg_strong_random.c              | 149 ++++++++++
 33 files changed, 688 insertions(+), 820 deletions(-)
 delete mode 100644 contrib/pgcrypto/fortuna.c
 delete mode 100644 contrib/pgcrypto/fortuna.h
 create mode 100644 src/backend/utils/misc/backend_random.c
 create mode 100644 src/include/utils/backend_random.h
 create mode 100644 src/port/pg_strong_random.c

diff --git a/configure b/configure
index f4f2f8b..7f0c5ac 100755
--- a/configure
+++ b/configure
@@ -739,6 +739,7 @@ GENHTML
 LCOV
 GCOV
 enable_debug
+enable_strong_random
 enable_rpath
 default_port
 WANTED_LANGUAGES
@@ -806,6 +807,7 @@ with_pgport
 enable_rpath
 enable_spinlocks
 enable_atomics
+enable_strong_random
 enable_debug
 enable_profiling
 enable_coverage
@@ -1478,6 +1480,7 @@ Optional Features:
                           executables
   --disable-spinlocks     do not use spinlocks
   --disable-atomics       do not use atomic operations
+  --disable-strong-random do not use a strong random number source
   --enable-debug          build with debugging symbols (-g)
   --enable-profiling      build with profiling enabled
   --enable-coverage       build with coverage testing instrumentation
@@ -3193,6 +3196,34 @@ fi
 
 
 #
+# Random number generation
+#
+
+
+# Check whether --enable-strong-random was given.
+if test "${enable_strong_random+set}" = set; then :
+  enableval=$enable_strong_random;
+  case $enableval in
+    yes)
+      :
+      ;;
+    no)
+      :
+      ;;
+    *)
+      as_fn_error $? "no argument expected for --enable-strong-random option" "$LINENO" 5
+      ;;
+  esac
+
+else
+  enable_strong_random=yes
+
+fi
+
+
+
+
+#
 # --enable-debug adds -g to compiler flags
 #
 
@@ -14982,6 +15013,84 @@ $as_echo "#define USE_WIN32_SHARED_MEMORY 1" >>confdefs.h
   SHMEM_IMPLEMENTATION="src/backend/port/win32_shmem.c"
 fi
 
+# Select random number source
+#
+# You can override this logic by setting the appropriate USE_*RANDOM flag to 1
+# in the template or configure command line.
+
+# If not selected manually, try to select a source automatically.
+if test "$enable_strong_random" = "yes" && test x"$USE_OPENSSL_RANDOM" = x"" && test x"$USE_WIN32_RANDOM" = x"" && test x"$USE_DEV_URANDOM" = x"" ; then
+  if test x"$with_openssl" = x"yes" ; then
+    USE_OPENSSL_RANDOM=1
+  elif test "$PORTNAME" = x"win32" ; then
+    USE_WIN32_RANDOM=1
+  else
+    { $as_echo "$as_me:${as_lineno-$LINENO}: checking for /dev/urandom" >&5
+$as_echo_n "checking for /dev/urandom... " >&6; }
+if ${ac_cv_file__dev_urandom+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  test "$cross_compiling" = yes &&
+  as_fn_error $? "cannot check for file existence when cross compiling" "$LINENO" 5
+if test -r "/dev/urandom"; then
+  ac_cv_file__dev_urandom=yes
+else
+  ac_cv_file__dev_urandom=no
+fi
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $ac_cv_file__dev_urandom" >&5
+$as_echo "$ac_cv_file__dev_urandom" >&6; }
+if test "x$ac_cv_file__dev_urandom" = xyes; then :
+
+fi
+
+
+    if test x"$ac_cv_file__dev_urandom" = x"yes" ; then
+      USE_DEV_URANDOM=1
+    fi
+  fi
+fi
+
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking which random number source to use" >&5
+$as_echo_n "checking which random number source to use... " >&6; }
+if test "$enable_strong_random" = yes ; then
+  if test x"$USE_OPENSSL_RANDOM" = x"1" ; then
+
+$as_echo "#define USE_OPENSSL_RANDOM 1" >>confdefs.h
+
+    { $as_echo "$as_me:${as_lineno-$LINENO}: result: OpenSSL" >&5
+$as_echo "OpenSSL" >&6; }
+  elif test x"$USE_WIN32_RANDOM" = x"1" ; then
+
+$as_echo "#define USE_WIN32_RANDOM 1" >>confdefs.h
+
+    { $as_echo "$as_me:${as_lineno-$LINENO}: result: Windows native" >&5
+$as_echo "Windows native" >&6; }
+  elif test x"$USE_DEV_URANDOM" = x"1" ; then
+
+$as_echo "#define USE_DEV_URANDOM 1" >>confdefs.h
+
+    { $as_echo "$as_me:${as_lineno-$LINENO}: result: /dev/urandom" >&5
+$as_echo "/dev/urandom" >&6; }
+  else
+    as_fn_error $? "
+no source of strong random numbers was found
+PostgreSQL can use OpenSSL or /dev/urandom as a source of random numbers,
+for authentication protocols. You can use --disable-strong-random to use of a built-in
+pseudo random number generator, but that may be insecure." "$LINENO" 5
+  fi
+
+$as_echo "#define HAVE_STRONG_RANDOM 1" >>confdefs.h
+
+else
+    { $as_echo "$as_me:${as_lineno-$LINENO}: result: weak builtin PRNG" >&5
+$as_echo "weak builtin PRNG" >&6; }
+    { $as_echo "$as_me:${as_lineno-$LINENO}: WARNING:
+*** Using weak builtin PRNG is not secure." >&5
+$as_echo "$as_me: WARNING:
+*** Using weak builtin PRNG is not secure." >&2;}
+fi
+
 # If not set in template file, set bytes to use libc memset()
 if test x"$MEMSET_LOOP_LIMIT" = x"" ; then
   MEMSET_LOOP_LIMIT=1024
diff --git a/configure.in b/configure.in
index 9f7611c..595e047 100644
--- a/configure.in
+++ b/configure.in
@@ -194,6 +194,13 @@ PGAC_ARG_BOOL(enable, atomics, yes,
               [do not use atomic operations])
 
 #
+# Random number generation
+#
+PGAC_ARG_BOOL(enable, strong-random, yes,
+              [do not use a strong random number source])
+AC_SUBST(enable_strong_random)
+
+#
 # --enable-debug adds -g to compiler flags
 #
 PGAC_ARG_BOOL(enable, debug, no,
@@ -1965,6 +1972,51 @@ else
   SHMEM_IMPLEMENTATION="src/backend/port/win32_shmem.c"
 fi
 
+# Select random number source
+#
+# You can override this logic by setting the appropriate USE_*RANDOM flag to 1
+# in the template or configure command line.
+
+# If not selected manually, try to select a source automatically.
+if test "$enable_strong_random" = "yes" && test x"$USE_OPENSSL_RANDOM" = x"" && test x"$USE_WIN32_RANDOM" = x"" && test x"$USE_DEV_URANDOM" = x"" ; then
+  if test x"$with_openssl" = x"yes" ; then
+    USE_OPENSSL_RANDOM=1
+  elif test "$PORTNAME" = x"win32" ; then
+    USE_WIN32_RANDOM=1
+  else
+    AC_CHECK_FILE([/dev/urandom], [], [])
+
+    if test x"$ac_cv_file__dev_urandom" = x"yes" ; then
+      USE_DEV_URANDOM=1
+    fi
+  fi
+fi
+
+AC_MSG_CHECKING([which random number source to use])
+if test "$enable_strong_random" = yes ; then
+  if test x"$USE_OPENSSL_RANDOM" = x"1" ; then
+    AC_DEFINE(USE_OPENSSL_RANDOM, 1, [Define to use OpenSSL for random number generation])
+    AC_MSG_RESULT([OpenSSL])
+  elif test x"$USE_WIN32_RANDOM" = x"1" ; then
+    AC_DEFINE(USE_WIN32_RANDOM, 1, [Define to use native Windows API for random number generation])
+    AC_MSG_RESULT([Windows native])
+  elif test x"$USE_DEV_URANDOM" = x"1" ; then
+    AC_DEFINE(USE_DEV_URANDOM, 1, [Define to use /dev/urandom for random number generation])
+    AC_MSG_RESULT([/dev/urandom])
+  else
+    AC_MSG_ERROR([
+no source of strong random numbers was found
+PostgreSQL can use OpenSSL or /dev/urandom as a source of random numbers,
+for authentication protocols. You can use --disable-strong-random to use of a built-in
+pseudo random number generator, but that may be insecure.])
+  fi
+  AC_DEFINE(HAVE_STRONG_RANDOM, 1, [Define to use have a strong random number source])
+else
+    AC_MSG_RESULT([weak builtin PRNG])
+    AC_MSG_WARN([
+*** Not using a strong random number source may be insecure.])
+fi
+
 # If not set in template file, set bytes to use libc memset()
 if test x"$MEMSET_LOOP_LIMIT" = x"" ; then
   MEMSET_LOOP_LIMIT=1024
diff --git a/contrib/pgcrypto/Makefile b/contrib/pgcrypto/Makefile
index 805db76..f65d84d 100644
--- a/contrib/pgcrypto/Makefile
+++ b/contrib/pgcrypto/Makefile
@@ -1,7 +1,7 @@
 # contrib/pgcrypto/Makefile
 
 INT_SRCS = md5.c sha1.c sha2.c internal.c internal-sha2.c blf.c rijndael.c \
-		fortuna.c random.c pgp-mpi-internal.c imath.c
+		pgp-mpi-internal.c imath.c
 INT_TESTS = sha2
 
 OSSL_SRCS = openssl.c pgp-mpi-openssl.c
diff --git a/contrib/pgcrypto/fortuna.c b/contrib/pgcrypto/fortuna.c
deleted file mode 100644
index 5028203..0000000
--- a/contrib/pgcrypto/fortuna.c
+++ /dev/null
@@ -1,463 +0,0 @@
-/*
- * fortuna.c
- *		Fortuna-like PRNG.
- *
- * Copyright (c) 2005 Marko Kreen
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *	  notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *	  notice, this list of conditions and the following disclaimer in the
- *	  documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * contrib/pgcrypto/fortuna.c
- */
-
-#include "postgres.h"
-
-#include <sys/time.h>
-#include <time.h>
-
-#include "px.h"
-#include "rijndael.h"
-#include "sha2.h"
-#include "fortuna.h"
-
-
-/*
- * Why Fortuna-like: There does not seem to be any definitive reference
- * on Fortuna in the net.  Instead this implementation is based on
- * following references:
- *
- * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
- *	 - Wikipedia article
- * http://jlcooke.ca/random/
- *	 - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
- */
-
-/*
- * There is some confusion about whether and how to carry forward
- * the state of the pools.  Seems like original Fortuna does not
- * do it, resetting hash after each request.  I guess expecting
- * feeding to happen more often that requesting.   This is absolutely
- * unsuitable for pgcrypto, as nothing asynchronous happens here.
- *
- * J.L. Cooke fixed this by feeding previous hash to new re-initialized
- * hash context.
- *
- * Fortuna predecessor Yarrow requires ability to query intermediate
- * 'final result' from hash, without affecting it.
- *
- * This implementation uses the Yarrow method - asking intermediate
- * results, but continuing with old state.
- */
-
-
-/*
- * Algorithm parameters
- */
-
-/*
- * How many pools.
- *
- * Original Fortuna uses 32 pools, that means 32'th pool is
- * used not earlier than in 13th year.  This is a waste in
- * pgcrypto, as we have very low-frequancy seeding.  Here
- * is preferable to have all entropy usable in reasonable time.
- *
- * With 23 pools, 23th pool is used after 9 days which seems
- * more sane.
- *
- * In our case the minimal cycle time would be bit longer
- * than the system-randomness feeding frequency.
- */
-#define NUM_POOLS		23
-
-/* in microseconds */
-#define RESEED_INTERVAL 100000	/* 0.1 sec */
-
-/* for one big request, reseed after this many bytes */
-#define RESEED_BYTES	(1024*1024)
-
-/*
- * Skip reseed if pool 0 has less than this many
- * bytes added since last reseed.
- */
-#define POOL0_FILL		(256/8)
-
-/*
- * Algorithm constants
- */
-
-/* Both cipher key size and hash result size */
-#define BLOCK			32
-
-/* cipher block size */
-#define CIPH_BLOCK		16
-
-/* for internal wrappers */
-#define MD_CTX			SHA256_CTX
-#define CIPH_CTX		rijndael_ctx
-
-struct fortuna_state
-{
-	uint8		counter[CIPH_BLOCK];
-	uint8		result[CIPH_BLOCK];
-	uint8		key[BLOCK];
-	MD_CTX		pool[NUM_POOLS];
-	CIPH_CTX	ciph;
-	unsigned	reseed_count;
-	struct timeval last_reseed_time;
-	unsigned	pool0_bytes;
-	unsigned	rnd_pos;
-	int			tricks_done;
-};
-typedef struct fortuna_state FState;
-
-
-/*
- * Use our own wrappers here.
- * - Need to get intermediate result from digest, without affecting it.
- * - Need re-set key on a cipher context.
- * - Algorithms are guaranteed to exist.
- * - No memory allocations.
- */
-
-static void
-ciph_init(CIPH_CTX * ctx, const uint8 *key, int klen)
-{
-	rijndael_set_key(ctx, (const uint32 *) key, klen, 1);
-}
-
-static void
-ciph_encrypt(CIPH_CTX * ctx, const uint8 *in, uint8 *out)
-{
-	rijndael_encrypt(ctx, (const uint32 *) in, (uint32 *) out);
-}
-
-static void
-md_init(MD_CTX * ctx)
-{
-	SHA256_Init(ctx);
-}
-
-static void
-md_update(MD_CTX * ctx, const uint8 *data, int len)
-{
-	SHA256_Update(ctx, data, len);
-}
-
-static void
-md_result(MD_CTX * ctx, uint8 *dst)
-{
-	SHA256_CTX	tmp;
-
-	memcpy(&tmp, ctx, sizeof(*ctx));
-	SHA256_Final(dst, &tmp);
-	px_memset(&tmp, 0, sizeof(tmp));
-}
-
-/*
- * initialize state
- */
-static void
-init_state(FState *st)
-{
-	int			i;
-
-	memset(st, 0, sizeof(*st));
-	for (i = 0; i < NUM_POOLS; i++)
-		md_init(&st->pool[i]);
-}
-
-/*
- * Endianess does not matter.
- * It just needs to change without repeating.
- */
-static void
-inc_counter(FState *st)
-{
-	uint32	   *val = (uint32 *) st->counter;
-
-	if (++val[0])
-		return;
-	if (++val[1])
-		return;
-	if (++val[2])
-		return;
-	++val[3];
-}
-
-/*
- * This is called 'cipher in counter mode'.
- */
-static void
-encrypt_counter(FState *st, uint8 *dst)
-{
-	ciph_encrypt(&st->ciph, st->counter, dst);
-	inc_counter(st);
-}
-
-
-/*
- * The time between reseed must be at least RESEED_INTERVAL
- * microseconds.
- */
-static int
-enough_time_passed(FState *st)
-{
-	int			ok;
-	struct timeval tv;
-	struct timeval *last = &st->last_reseed_time;
-
-	gettimeofday(&tv, NULL);
-
-	/* check how much time has passed */
-	ok = 0;
-	if (tv.tv_sec > last->tv_sec + 1)
-		ok = 1;
-	else if (tv.tv_sec == last->tv_sec + 1)
-	{
-		if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
-			ok = 1;
-	}
-	else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
-		ok = 1;
-
-	/* reseed will happen, update last_reseed_time */
-	if (ok)
-		memcpy(last, &tv, sizeof(tv));
-
-	px_memset(&tv, 0, sizeof(tv));
-
-	return ok;
-}
-
-/*
- * generate new key from all the pools
- */
-static void
-reseed(FState *st)
-{
-	unsigned	k;
-	unsigned	n;
-	MD_CTX		key_md;
-	uint8		buf[BLOCK];
-
-	/* set pool as empty */
-	st->pool0_bytes = 0;
-
-	/*
-	 * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
-	 */
-	n = ++st->reseed_count;
-
-	/*
-	 * The goal: use k-th pool only 1/(2^k) of the time.
-	 */
-	md_init(&key_md);
-	for (k = 0; k < NUM_POOLS; k++)
-	{
-		md_result(&st->pool[k], buf);
-		md_update(&key_md, buf, BLOCK);
-
-		if (n & 1 || !n)
-			break;
-		n >>= 1;
-	}
-
-	/* add old key into mix too */
-	md_update(&key_md, st->key, BLOCK);
-
-	/* now we have new key */
-	md_result(&key_md, st->key);
-
-	/* use new key */
-	ciph_init(&st->ciph, st->key, BLOCK);
-
-	px_memset(&key_md, 0, sizeof(key_md));
-	px_memset(buf, 0, BLOCK);
-}
-
-/*
- * Pick a random pool.  This uses key bytes as random source.
- */
-static unsigned
-get_rand_pool(FState *st)
-{
-	unsigned	rnd;
-
-	/*
-	 * This slightly prefers lower pools - that is OK.
-	 */
-	rnd = st->key[st->rnd_pos] % NUM_POOLS;
-
-	st->rnd_pos++;
-	if (st->rnd_pos >= BLOCK)
-		st->rnd_pos = 0;
-
-	return rnd;
-}
-
-/*
- * update pools
- */
-static void
-add_entropy(FState *st, const uint8 *data, unsigned len)
-{
-	unsigned	pos;
-	uint8		hash[BLOCK];
-	MD_CTX		md;
-
-	/* hash given data */
-	md_init(&md);
-	md_update(&md, data, len);
-	md_result(&md, hash);
-
-	/*
-	 * Make sure the pool 0 is initialized, then update randomly.
-	 */
-	if (st->reseed_count == 0)
-		pos = 0;
-	else
-		pos = get_rand_pool(st);
-	md_update(&st->pool[pos], hash, BLOCK);
-
-	if (pos == 0)
-		st->pool0_bytes += len;
-
-	px_memset(hash, 0, BLOCK);
-	px_memset(&md, 0, sizeof(md));
-}
-
-/*
- * Just take 2 next blocks as new key
- */
-static void
-rekey(FState *st)
-{
-	encrypt_counter(st, st->key);
-	encrypt_counter(st, st->key + CIPH_BLOCK);
-	ciph_init(&st->ciph, st->key, BLOCK);
-}
-
-/*
- * Hide public constants. (counter, pools > 0)
- *
- * This can also be viewed as spreading the startup
- * entropy over all of the components.
- */
-static void
-startup_tricks(FState *st)
-{
-	int			i;
-	uint8		buf[BLOCK];
-
-	/* Use next block as counter. */
-	encrypt_counter(st, st->counter);
-
-	/* Now shuffle pools, excluding #0 */
-	for (i = 1; i < NUM_POOLS; i++)
-	{
-		encrypt_counter(st, buf);
-		encrypt_counter(st, buf + CIPH_BLOCK);
-		md_update(&st->pool[i], buf, BLOCK);
-	}
-	px_memset(buf, 0, BLOCK);
-
-	/* Hide the key. */
-	rekey(st);
-
-	/* This can be done only once. */
-	st->tricks_done = 1;
-}
-
-static void
-extract_data(FState *st, unsigned count, uint8 *dst)
-{
-	unsigned	n;
-	unsigned	block_nr = 0;
-
-	/* Should we reseed? */
-	if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0)
-		if (enough_time_passed(st))
-			reseed(st);
-
-	/* Do some randomization on first call */
-	if (!st->tricks_done)
-		startup_tricks(st);
-
-	while (count > 0)
-	{
-		/* produce bytes */
-		encrypt_counter(st, st->result);
-
-		/* copy result */
-		if (count > CIPH_BLOCK)
-			n = CIPH_BLOCK;
-		else
-			n = count;
-		memcpy(dst, st->result, n);
-		dst += n;
-		count -= n;
-
-		/* must not give out too many bytes with one key */
-		block_nr++;
-		if (block_nr > (RESEED_BYTES / CIPH_BLOCK))
-		{
-			rekey(st);
-			block_nr = 0;
-		}
-	}
-	/* Set new key for next request. */
-	rekey(st);
-}
-
-/*
- * public interface
- */
-
-static FState main_state;
-static int	init_done = 0;
-
-void
-fortuna_add_entropy(const uint8 *data, unsigned len)
-{
-	if (!init_done)
-	{
-		init_state(&main_state);
-		init_done = 1;
-	}
-	if (!data || !len)
-		return;
-	add_entropy(&main_state, data, len);
-}
-
-void
-fortuna_get_bytes(unsigned len, uint8 *dst)
-{
-	if (!init_done)
-	{
-		init_state(&main_state);
-		init_done = 1;
-	}
-	if (!dst || !len)
-		return;
-	extract_data(&main_state, len, dst);
-}
diff --git a/contrib/pgcrypto/fortuna.h b/contrib/pgcrypto/fortuna.h
deleted file mode 100644
index bf9f476..0000000
--- a/contrib/pgcrypto/fortuna.h
+++ /dev/null
@@ -1,38 +0,0 @@
-/*
- * fortuna.c
- *		Fortuna PRNG.
- *
- * Copyright (c) 2005 Marko Kreen
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *	  notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *	  notice, this list of conditions and the following disclaimer in the
- *	  documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * contrib/pgcrypto/fortuna.h
- */
-
-#ifndef __FORTUNA_H
-#define __FORTUNA_H
-
-void		fortuna_get_bytes(unsigned len, uint8 *dst);
-void		fortuna_add_entropy(const uint8 *data, unsigned len);
-
-#endif
diff --git a/contrib/pgcrypto/internal.c b/contrib/pgcrypto/internal.c
index 02ff976..2516092 100644
--- a/contrib/pgcrypto/internal.c
+++ b/contrib/pgcrypto/internal.c
@@ -38,7 +38,6 @@
 #include "sha1.h"
 #include "blf.h"
 #include "rijndael.h"
-#include "fortuna.h"
 
 /*
  * System reseeds should be separated at least this much.
@@ -615,65 +614,3 @@ px_find_cipher(const char *name, PX_Cipher **res)
 	*res = c;
 	return 0;
 }
-
-/*
- * Randomness provider
- */
-
-static time_t seed_time = 0;
-static time_t check_time = 0;
-
-static void
-system_reseed(void)
-{
-	uint8		buf[1024];
-	int			n;
-	time_t		t;
-	int			skip = 1;
-
-	t = time(NULL);
-
-	if (seed_time == 0)
-		skip = 0;
-	else if ((t - seed_time) < SYSTEM_RESEED_MIN)
-		skip = 1;
-	else if ((t - seed_time) > SYSTEM_RESEED_MAX)
-		skip = 0;
-	else if (check_time == 0 ||
-			 (t - check_time) > SYSTEM_RESEED_CHECK_TIME)
-	{
-		check_time = t;
-
-		/* roll dice */
-		px_get_random_bytes(buf, 1);
-		skip = buf[0] >= SYSTEM_RESEED_CHANCE;
-	}
-	/* clear 1 byte */
-	px_memset(buf, 0, sizeof(buf));
-
-	if (skip)
-		return;
-
-	n = px_acquire_system_randomness(buf);
-	if (n > 0)
-		fortuna_add_entropy(buf, n);
-
-	seed_time = t;
-	px_memset(buf, 0, sizeof(buf));
-}
-
-int
-px_get_random_bytes(uint8 *dst, unsigned count)
-{
-	system_reseed();
-	fortuna_get_bytes(count, dst);
-	return 0;
-}
-
-int
-px_add_entropy(const uint8 *data, unsigned count)
-{
-	system_reseed();
-	fortuna_add_entropy(data, count);
-	return 0;
-}
diff --git a/contrib/pgcrypto/openssl.c b/contrib/pgcrypto/openssl.c
index f3e3a92..1d3e58d 100644
--- a/contrib/pgcrypto/openssl.c
+++ b/contrib/pgcrypto/openssl.c
@@ -712,49 +712,3 @@ px_find_cipher(const char *name, PX_Cipher **res)
 	*res = c;
 	return 0;
 }
-
-
-static int	openssl_random_init = 0;
-
-/*
- * OpenSSL random should re-feeded occasionally. From /dev/urandom
- * preferably.
- */
-static void
-init_openssl_rand(void)
-{
-	if (RAND_get_rand_method() == NULL)
-	{
-#ifdef HAVE_RAND_OPENSSL
-		RAND_set_rand_method(RAND_OpenSSL());
-#else
-		RAND_set_rand_method(RAND_SSLeay());
-#endif
-	}
-	openssl_random_init = 1;
-}
-
-int
-px_get_random_bytes(uint8 *dst, unsigned count)
-{
-	int			res;
-
-	if (!openssl_random_init)
-		init_openssl_rand();
-
-	res = RAND_bytes(dst, count);
-	if (res == 1)
-		return count;
-
-	return PXE_OSSL_RAND_ERROR;
-}
-
-int
-px_add_entropy(const uint8 *data, unsigned count)
-{
-	/*
-	 * estimate 0 bits
-	 */
-	RAND_add(data, count, 0);
-	return 0;
-}
diff --git a/contrib/pgcrypto/pgcrypto.c b/contrib/pgcrypto/pgcrypto.c
index 27b96c7..f2bfff6 100644
--- a/contrib/pgcrypto/pgcrypto.c
+++ b/contrib/pgcrypto/pgcrypto.c
@@ -34,6 +34,7 @@
 #include <ctype.h>
 
 #include "parser/scansup.h"
+#include "utils/backend_random.h"
 #include "utils/builtins.h"
 #include "utils/uuid.h"
 
@@ -422,7 +423,6 @@ PG_FUNCTION_INFO_V1(pg_random_bytes);
 Datum
 pg_random_bytes(PG_FUNCTION_ARGS)
 {
-	int			err;
 	int			len = PG_GETARG_INT32(0);
 	bytea	   *res;
 
@@ -435,11 +435,10 @@ pg_random_bytes(PG_FUNCTION_ARGS)
 	SET_VARSIZE(res, VARHDRSZ + len);
 
 	/* generate result */
-	err = px_get_random_bytes((uint8 *) VARDATA(res), len);
-	if (err < 0)
+	if (!pg_backend_random(VARDATA(res), len))
 		ereport(ERROR,
 				(errcode(ERRCODE_EXTERNAL_ROUTINE_INVOCATION_EXCEPTION),
-				 errmsg("Random generator error: %s", px_strerror(err))));
+				 errmsg("random generator error")));
 
 	PG_RETURN_BYTEA_P(res);
 }
@@ -451,14 +450,12 @@ Datum
 pg_random_uuid(PG_FUNCTION_ARGS)
 {
 	uint8	   *buf = (uint8 *) palloc(UUID_LEN);
-	int			err;
 
 	/* generate random bits */
-	err = px_get_random_bytes(buf, UUID_LEN);
-	if (err < 0)
+	if (!pg_backend_random((char *) buf, UUID_LEN))
 		ereport(ERROR,
 				(errcode(ERRCODE_EXTERNAL_ROUTINE_INVOCATION_EXCEPTION),
-				 errmsg("Random generator error: %s", px_strerror(err))));
+				 errmsg("random generator error")));
 
 	/*
 	 * Set magic numbers for a "version 4" (pseudorandom) UUID, see
diff --git a/contrib/pgcrypto/pgp-encrypt.c b/contrib/pgcrypto/pgp-encrypt.c
index c9148fd..6d63198 100644
--- a/contrib/pgcrypto/pgp-encrypt.c
+++ b/contrib/pgcrypto/pgp-encrypt.c
@@ -37,6 +37,8 @@
 #include "px.h"
 #include "pgp.h"
 
+#include "utils/backend_random.h"
+
 
 #define MDC_DIGEST_LEN 20
 #define STREAM_ID 0xE0
@@ -482,9 +484,8 @@ write_prefix(PGP_Context *ctx, PushFilter *dst)
 				bs;
 
 	bs = pgp_get_cipher_block_size(ctx->cipher_algo);
-	res = px_get_random_bytes(prefix, bs);
-	if (res < 0)
-		return res;
+	if (!pg_backend_random((char *) prefix, bs))
+		return PXE_NO_RANDOM;
 
 	prefix[bs + 0] = prefix[bs - 2];
 	prefix[bs + 1] = prefix[bs - 1];
@@ -578,14 +579,11 @@ init_s2k_key(PGP_Context *ctx)
 static int
 init_sess_key(PGP_Context *ctx)
 {
-	int			res;
-
 	if (ctx->use_sess_key || ctx->pub_key)
 	{
 		ctx->sess_key_len = pgp_get_cipher_key_size(ctx->cipher_algo);
-		res = px_get_random_bytes(ctx->sess_key, ctx->sess_key_len);
-		if (res < 0)
-			return res;
+		if (!pg_backend_random((char *) ctx->sess_key, ctx->sess_key_len))
+			return PXE_NO_RANDOM;
 	}
 	else
 	{
diff --git a/contrib/pgcrypto/pgp-mpi-internal.c b/contrib/pgcrypto/pgp-mpi-internal.c
index be95f2d..5c9e82e 100644
--- a/contrib/pgcrypto/pgp-mpi-internal.c
+++ b/contrib/pgcrypto/pgp-mpi-internal.c
@@ -35,6 +35,8 @@
 #include "px.h"
 #include "pgp.h"
 
+#include "utils/backend_random.h"
+
 static mpz_t *
 mp_new()
 {
@@ -57,17 +59,15 @@ mp_clear_free(mpz_t *a)
 static int
 mp_px_rand(uint32 bits, mpz_t *res)
 {
-	int			err;
 	unsigned	bytes = (bits + 7) / 8;
 	int			last_bits = bits & 7;
 	uint8	   *buf;
 
 	buf = px_alloc(bytes);
-	err = px_get_random_bytes(buf, bytes);
-	if (err < 0)
+	if (!pg_backend_random((char *) buf, bytes))
 	{
 		px_free(buf);
-		return err;
+		return PXE_NO_RANDOM;
 	}
 
 	/* clear unnecessary bits and set last bit to one */
diff --git a/contrib/pgcrypto/pgp-pgsql.c b/contrib/pgcrypto/pgp-pgsql.c
index 1f65b66..1174b63 100644
--- a/contrib/pgcrypto/pgp-pgsql.c
+++ b/contrib/pgcrypto/pgp-pgsql.c
@@ -62,65 +62,6 @@ PG_FUNCTION_INFO_V1(pg_dearmor);
 PG_FUNCTION_INFO_V1(pgp_armor_headers);
 
 /*
- * Mix a block of data into RNG.
- */
-static void
-add_block_entropy(PX_MD *md, text *data)
-{
-	uint8		sha1[20];
-
-	px_md_reset(md);
-	px_md_update(md, (uint8 *) VARDATA(data), VARSIZE(data) - VARHDRSZ);
-	px_md_finish(md, sha1);
-
-	px_add_entropy(sha1, 20);
-
-	px_memset(sha1, 0, 20);
-}
-
-/*
- * Mix user data into RNG.  It is for user own interests to have
- * RNG state shuffled.
- */
-static void
-add_entropy(text *data1, text *data2, text *data3)
-{
-	PX_MD	   *md;
-	uint8		rnd[3];
-
-	if (!data1 && !data2 && !data3)
-		return;
-
-	if (px_get_random_bytes(rnd, 3) < 0)
-		return;
-
-	if (px_find_digest("sha1", &md) < 0)
-		return;
-
-	/*
-	 * Try to make the feeding unpredictable.
-	 *
-	 * Prefer data over keys, as it's rather likely that key is same in
-	 * several calls.
-	 */
-
-	/* chance: 7/8 */
-	if (data1 && rnd[0] >= 32)
-		add_block_entropy(md, data1);
-
-	/* chance: 5/8 */
-	if (data2 && rnd[1] >= 160)
-		add_block_entropy(md, data2);
-
-	/* chance: 5/8 */
-	if (data3 && rnd[2] >= 160)
-		add_block_entropy(md, data3);
-
-	px_md_free(md);
-	px_memset(rnd, 0, sizeof(rnd));
-}
-
-/*
  * returns src in case of no conversion or error
  */
 static text *
@@ -459,11 +400,6 @@ encrypt_internal(int is_pubenc, int is_text,
 	struct debug_expect ex;
 	text	   *tmp_data = NULL;
 
-	/*
-	 * Add data and key info RNG.
-	 */
-	add_entropy(data, key, NULL);
-
 	init_work(&ctx, is_text, args, &ex);
 
 	if (is_text && pgp_get_unicode_mode(ctx))
@@ -629,11 +565,6 @@ decrypt_internal(int is_pubenc, int need_text, text *data,
 	}
 	px_set_debug_handler(NULL);
 
-	/*
-	 * add successful decryptions also into RNG
-	 */
-	add_entropy(res, key, keypsw);
-
 	return res;
 }
 
diff --git a/contrib/pgcrypto/pgp-pubenc.c b/contrib/pgcrypto/pgp-pubenc.c
index 3b43bb6..3360bfc 100644
--- a/contrib/pgcrypto/pgp-pubenc.c
+++ b/contrib/pgcrypto/pgp-pubenc.c
@@ -33,6 +33,8 @@
 #include "px.h"
 #include "pgp.h"
 
+#include "utils/backend_random.h"
+
 /*
  * padded msg: 02 || non-zero pad bytes || 00 || msg
  */
@@ -49,11 +51,10 @@ pad_eme_pkcs1_v15(uint8 *data, int data_len, int res_len, uint8 **res_p)
 
 	buf = px_alloc(res_len);
 	buf[0] = 0x02;
-	res = px_get_random_bytes(buf + 1, pad_len);
-	if (res < 0)
+	if (!pg_backend_random((char *) buf + 1, pad_len))
 	{
 		px_free(buf);
-		return res;
+		return PXE_NO_RANDOM;
 	}
 
 	/* pad must not contain zero bytes */
@@ -62,9 +63,11 @@ pad_eme_pkcs1_v15(uint8 *data, int data_len, int res_len, uint8 **res_p)
 	{
 		if (*p == 0)
 		{
-			res = px_get_random_bytes(p, 1);
-			if (res < 0)
-				break;
+			if (!pg_backend_random((char *) p, 1))
+			{
+				px_free(buf);
+				return PXE_NO_RANDOM;
+			}
 		}
 		if (*p != 0)
 			p++;
diff --git a/contrib/pgcrypto/pgp-s2k.c b/contrib/pgcrypto/pgp-s2k.c
index 3551d44..a0fd896 100644
--- a/contrib/pgcrypto/pgp-s2k.c
+++ b/contrib/pgcrypto/pgp-s2k.c
@@ -34,6 +34,8 @@
 #include "px.h"
 #include "pgp.h"
 
+#include "utils/backend_random.h"
+
 static int
 calc_s2k_simple(PGP_S2K *s2k, PX_MD *md, const uint8 *key,
 				unsigned key_len)
@@ -233,15 +235,14 @@ pgp_s2k_fill(PGP_S2K *s2k, int mode, int digest_algo, int count)
 		case PGP_S2K_SIMPLE:
 			break;
 		case PGP_S2K_SALTED:
-			res = px_get_random_bytes(s2k->salt, PGP_S2K_SALT);
+			if (!pg_backend_random((char *) s2k->salt, PGP_S2K_SALT))
+				return PXE_NO_RANDOM;
 			break;
 		case PGP_S2K_ISALTED:
-			res = px_get_random_bytes(s2k->salt, PGP_S2K_SALT);
-			if (res < 0)
-				break;
-			res = px_get_random_bytes(&tmp, 1);
-			if (res < 0)
-				break;
+			if (!pg_backend_random((char *) s2k->salt, PGP_S2K_SALT))
+				return PXE_NO_RANDOM;
+			if (!pg_backend_random((char *) &tmp, 1))
+				return PXE_NO_RANDOM;
 			s2k->iter = decide_s2k_iter(tmp, count);
 			break;
 		default:
diff --git a/contrib/pgcrypto/px-crypt.c b/contrib/pgcrypto/px-crypt.c
index 3d42393..6c72c4a 100644
--- a/contrib/pgcrypto/px-crypt.c
+++ b/contrib/pgcrypto/px-crypt.c
@@ -34,6 +34,7 @@
 #include "px.h"
 #include "px-crypt.h"
 
+#include "utils/backend_random.h"
 
 static char *
 run_crypt_des(const char *psw, const char *salt,
@@ -132,7 +133,6 @@ static struct generator gen_list[] = {
 int
 px_gen_salt(const char *salt_type, char *buf, int rounds)
 {
-	int			res;
 	struct generator *g;
 	char	   *p;
 	char		rbuf[16];
@@ -153,9 +153,8 @@ px_gen_salt(const char *salt_type, char *buf, int rounds)
 			return PXE_BAD_SALT_ROUNDS;
 	}
 
-	res = px_get_random_bytes((uint8 *) rbuf, g->input_len);
-	if (res < 0)
-		return res;
+	if (!pg_backend_random(rbuf, g->input_len))
+		return PXE_NO_RANDOM;
 
 	p = g->gen(rounds, rbuf, g->input_len, buf, PX_MAX_SALT_LEN);
 	px_memset(rbuf, 0, sizeof(rbuf));
diff --git a/contrib/pgcrypto/px.h b/contrib/pgcrypto/px.h
index 9174e13..553110b 100644
--- a/contrib/pgcrypto/px.h
+++ b/contrib/pgcrypto/px.h
@@ -189,11 +189,6 @@ int			px_find_hmac(const char *name, PX_HMAC **res);
 int			px_find_cipher(const char *name, PX_Cipher **res);
 int			px_find_combo(const char *name, PX_Combo **res);
 
-int			px_get_random_bytes(uint8 *dst, unsigned count);
-int			px_add_entropy(const uint8 *data, unsigned count);
-
-unsigned	px_acquire_system_randomness(uint8 *dst);
-
 const char *px_strerror(int err);
 
 const char *px_resolve_alias(const PX_Alias *aliases, const char *name);
diff --git a/src/Makefile.global.in b/src/Makefile.global.in
index aa1fa65..d39d6ca 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 0ba8530..5d166db 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 d84a180..35b657a 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 24add74..5f016b7 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,41 @@ 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;
-
+#ifndef HAVE_STRONG_RANDOM
 	/*
-	 * 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.
+	 * We cannot use pg_backend_random() in postmaster, because it stores
+	 * its state in shared memory. So if built with --disable-strong-random,
+	 * use plain old erand48.
 	 */
-	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;
+#else
+	return pg_strong_random((char *) cancel_key, sizeof(int32));
+#endif
 }
 
 /*
@@ -5295,16 +5276,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 +5580,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 +5615,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 c04b17f..01bddce 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 f8996cd..0dcf7ef 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 f232083..7c88adc 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 a5b487d..0ad1b8b 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 0000000..10170b0
--- /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
+ * key and 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 5725bb4..f51e0fd 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 b91eca5..66647ad 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 78c9954..a3f2de5 100644
--- a/src/include/miscadmin.h
+++ b/src/include/miscadmin.h
@@ -162,7 +162,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 7dbfa90..42a3fc8 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/port.h b/src/include/port.h
index 8a63958..9dc9e39 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 */
+#ifndef USE_WEAK_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 0000000..16a6a26
--- /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 bc9b63a..81f01b2 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 9d47119..716816b 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 0000000..6d3aa38
--- /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
+}
-- 
2.10.2

Michael Paquier

michael.paquier@gmail.com

about 9 years ago

In reply to: Heikki Linnakangas (#1)

1 attachment(s)

Re: Random number generation, take two

On Tue, Nov 29, 2016 at 10:02 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

Ok, here's my second attempt at refactoring random number generation.
Previous attempt crashed and burned, see
/messages/by-id/E1bw3g3-0003st-6M@gemulon.postgresql.org.
This addresses the issues pointed out in that thread.

Yeah. (Nit: I want this badly)

Autoconf
--------

* Configure chooses the implementation to use: OpenSSL, Windows native, or
/dev/urandom, in that order. You can also force it, by specifying
USE_OPENSSL_RANDOM=1, USE_WIN32_RANDOM=1 or USE_DEV_URANDOM=1 on the
configure command line. That's useful for testing.

It's that or a configure option able to take an optional argument but
that conflicts with --with-openssl so your way looks better.

* Remove the support for /dev/random (only support /dev/urandom). I don't
think we have any platforms where /dev/urandom is not present, but
/dev/random is. If we do, the buildfarm will tell us, but until then let's
keep it simple.

Yes, I don't recall of a modern platform without urandom if random is
there, recalling when researching on the matter a couple of weeks back
or even now. Even newest HP/UX boxes have it!

Fallback implementation (with --disable-strong-random)
-----------

In postmaster, the algorithm is similar to the existing PostmasterRandom()
function. It's based on the built-in PRNG, seeded by postmaster and first
backend start time. It's been rewritten to fit the rest of the code better,
however.

In backends, there is a new function, pg_backend_random(). It also uses the
built-in PRNG, but the seed is shared between all backends, in shared
memory. (Otherwise all backends would inherit the same seed from
postmaster.)

Sounds fine for me.

Phew, this has been way more complicated than it seemed at first. Thoughts?

One of the goals of this patch is to be able to have a strong random
function as well for the frontend, which is fine. But any build where
--disable-strong-random is used is not going to have a random function
to rely on. Disabling SCRAM for such builds is a possibility, because
we assume that any build using --disable-strong-random is aware of
security risks, still that's not really appealing in terms of
portability. Another possibility would be to have an extra routine
like pg_frontend_random(), wrapping pg_strong_backend() and using a
combination of getpid + gettimeofday to generate a seed with just a
random() call? That's what we were fighting against previously, so my
mind is telling me that just returning an error when the code paths of
the SCRAM client code is used when built with --disable-strong-random
is the way to go, because we want SCRAM to be fundamentally safe to
use. What do you think?

pgcrypto
--------

pgcrypto doesn't have the same requirements for "strongness" as cancel keys
and MD5 salts have. pgcrypto uses random numbers for generating salts, too,
which I think has similar requirements. But it also uses random numbers for
generating encryption keys, which I believe ought to be harder to predict.
If you compile with --disable-strong-random, do we want the encryption key
generation routines to fail, or to return known-weak keys?

This patch removes the Fortuna algorithm, that was used to generate fairly
strong random numbers, if OpenSSL was not present. One option would be to
keep that code as a fallback. I wanted to get rid of that, since it's only
used on a few old platforms, but OTOH it's been around for a long time with
little issues.

As this patch stands, it removes Fortuna, and returns known-weak keys, but
there's a good argument to be made for throwing an error instead.

IMO, leading to an error would make the users aware of them playing
with the fire... Now pademelon's owner may likely have a different
opinion on the matter :p

This patch needs to initialize the variable "res" in
pad_eme_pkcs1_v15(), creating compilation warnings.

Documentation for --disable-strong-random needs to be added.

Cancel keys are not broken.

+ int32 MyCancelKey;
Those would be better as unsigned?

+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);
Shouldn't an exclusive lock be taken only when the initialization
phase is called? When reading the value a shared lock would be fine.

Attached is a patch for MSVC to apply on top of yours to enable the
build for strong and weak random functions. Feel free to hack it as
needs be, this base implementation works for the current
implementation.
--
Michael

Attachments:

strong_random_msvc.patchinvalid/octet-stream; name=strong_random_msvc.patchDownload

diff --git a/src/tools/msvc/Mkvcbuild.pm b/src/tools/msvc/Mkvcbuild.pm
index de764dd..4c81adc 100644
--- a/src/tools/msvc/Mkvcbuild.pm
+++ b/src/tools/msvc/Mkvcbuild.pm
@@ -97,6 +97,7 @@ sub mkvcbuild
 	  win32env.c win32error.c win32security.c win32setlocale.c);
 
 	push(@pgportfiles, 'rint.c') if ($vsVersion < '12.00');
+	push(@pgportfiles, 'pg_strong_random.c') if ($solution->{options}->{strandom});
 
 	if ($vsVersion >= '9.00')
 	{
@@ -425,8 +426,8 @@ 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');
+			'random.c',           'pgp-mpi-internal.c',
+			'imath.c');
 	}
 	$pgcrypto->AddReference($postgres);
 	$pgcrypto->AddLibrary('ws2_32.lib');
diff --git a/src/tools/msvc/Solution.pm b/src/tools/msvc/Solution.pm
index 8217d06..a3efafc 100644
--- a/src/tools/msvc/Solution.pm
+++ b/src/tools/msvc/Solution.pm
@@ -174,8 +174,9 @@ s{PG_VERSION_STR "[^"]+"}{__STRINGIFY(x) #x\n#define __STRINGIFY2(z) __STRINGIFY
 		print O "#define USE_LDAP 1\n"    if ($self->{options}->{ldap});
 		print O "#define HAVE_LIBZ 1\n"   if ($self->{options}->{zlib});
 		print O "#define USE_OPENSSL 1\n" if ($self->{options}->{openssl});
+		print O "#define USE_OPENSSL 1\n" if ($self->{options}->{openssl});
 		print O "#define ENABLE_NLS 1\n"  if ($self->{options}->{nls});
-
+		print O "#define HAVE_STRONG_RANDOM 1\n"  if ($self->{options}->{strandom});
 		print O "#define BLCKSZ ", 1024 * $self->{options}->{blocksize}, "\n";
 		print O "#define RELSEG_SIZE ",
 		  (1024 / $self->{options}->{blocksize}) *
@@ -186,6 +187,18 @@ s{PG_VERSION_STR "[^"]+"}{__STRINGIFY(x) #x\n#define __STRINGIFY2(z) __STRINGIFY
 		print O "#define XLOG_SEG_SIZE (", $self->{options}->{wal_segsize},
 		  " * 1024 * 1024)\n";
 
+		if ($self->{options}->{strandom})
+		{
+			if ($self->{options}->{openssl})
+			{
+				print O "#define USE_OPENSSL_RANDOM 1\n";
+			}
+			else
+			{
+				print O "#define USE_WIN32_RANDOM 1\n";
+			}
+		}
+
 		if ($self->{options}->{float4byval})
 		{
 			print O "#define USE_FLOAT4_BYVAL 1\n";
diff --git a/src/tools/msvc/config_default.pl b/src/tools/msvc/config_default.pl
index f046687..8d5f9a4 100644
--- a/src/tools/msvc/config_default.pl
+++ b/src/tools/msvc/config_default.pl
@@ -14,6 +14,7 @@ our $config = {
 	# wal_blocksize => 8,     # --with-wal-blocksize, 8kB by default
 	# wal_segsize => 16,      # --with-wal-segsize, 16MB by default
 	ldap      => 1,        # --with-ldap
+	strandom  => 1,        # --enable-strong-random
 	extraver  => undef,    # --with-extra-version=<string>
 	gss       => undef,    # --with-gssapi=<path>
 	nls       => undef,    # --enable-nls=<path>

Heikki Linnakangas

hlinnaka@iki.fi

about 9 years ago

In reply to: Michael Paquier (#2)

2 attachment(s)

Re: Random number generation, take two

On 11/30/2016 09:01 AM, Michael Paquier wrote:

On Tue, Nov 29, 2016 at 10:02 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

Phew, this has been way more complicated than it seemed at first. Thoughts?

One of the goals of this patch is to be able to have a strong random
function as well for the frontend, which is fine. But any build where
--disable-strong-random is used is not going to have a random function
to rely on. Disabling SCRAM for such builds is a possibility, because
we assume that any build using --disable-strong-random is aware of
security risks, still that's not really appealing in terms of
portability. Another possibility would be to have an extra routine
like pg_frontend_random(), wrapping pg_strong_backend() and using a
combination of getpid + gettimeofday to generate a seed with just a
random() call? That's what we were fighting against previously, so my
mind is telling me that just returning an error when the code paths of
the SCRAM client code is used when built with --disable-strong-random
is the way to go, because we want SCRAM to be fundamentally safe to
use. What do you think?

I was thinking that with --disable-strong-random, we'd use plain
random() in libpq as well. I believe SCRAM is analogous to the MD5 salt
generation in the backend, in its requirement for randomness. The SCRAM
spec (RFC5802) says:

It is important that this value [nonce] be different for each
authentication (see [RFC4086] for more details on how to achieve
this)

So the nonces need to be different for each session, to avoid replay
attacks. But they don't necessarily need to be unpredictable, they are
transmitted in plaintext during the authentication, anyway. If an
attacker can calculate them in advance, it only buys him more time, but
doesn't give any new information.

If we were 100% confident on that point, we could just always use
current timestamp and a counter for the nonces. But I'm not that
confident, certainly feels better to use a stronger random number when
available. The quote above points at RFC4086, which actually talks about
cryptographically strong random numbers, rather than just generating a
unique nonce. So I'm not sure if the authors of SCRAM considered that
point in any detail, seems like they just assumed that you might as well
use a strong random source because everyone's got one.

pgcrypto
--------

pgcrypto doesn't have the same requirements for "strongness" as cancel keys
and MD5 salts have. pgcrypto uses random numbers for generating salts, too,
which I think has similar requirements. But it also uses random numbers for
generating encryption keys, which I believe ought to be harder to predict.
If you compile with --disable-strong-random, do we want the encryption key
generation routines to fail, or to return known-weak keys?

This patch removes the Fortuna algorithm, that was used to generate fairly
strong random numbers, if OpenSSL was not present. One option would be to
keep that code as a fallback. I wanted to get rid of that, since it's only
used on a few old platforms, but OTOH it's been around for a long time with
little issues.

As this patch stands, it removes Fortuna, and returns known-weak keys, but
there's a good argument to be made for throwing an error instead.

IMO, leading to an error would make the users aware of them playing
with the fire... Now pademelon's owner may likely have a different
opinion on the matter :p

Ok, I bit the bullet and modified those pgcrypto functions that truly
need cryptographically strong random numbers to throw an error with
--disable-strong-random. Notably, the pgp encrypt functions mostly fail now.

Documentation for --disable-strong-random needs to be added.

Ah, I didn't remember we have a section in the user manual for these. Added.

+ int32 MyCancelKey;
Those would be better as unsigned?

Perhaps, but it's historically been signed, I'm afraid of changing it..

+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);
Shouldn't an exclusive lock be taken only when the initialization
phase is called? When reading the value a shared lock would be fine.

No, it needs to be exclusive. Each pg_jrand48() call updates the state,
aka seed.

Attached is a patch for MSVC to apply on top of yours to enable the
build for strong and weak random functions. Feel free to hack it as
needs be, this base implementation works for the current
implementation.

Great, thanks! I wonder if this is overly complicated, though. For
comparison, we haven't bothered to expose --disable-spinlocks in
config_default.pl either. Perhaps we should just always use the Windows
native function on MSVC, whether or not configured with OpenSSL, and
just put USE_WIN32_RANDOM in pg_config.h.win32? See 2nd attached patch
(untested).

- Heikki

Attachments:

0001-Replace-PostmasterRandom-with-a-stronger-source-seco.patch.gzapplication/gzip; name=0001-Replace-PostmasterRandom-with-a-stronger-source-seco.patch.gzDownload

0002-Fix-MSVC-build.patchapplication/x-download; name=0002-Fix-MSVC-build.patchDownload

From 0e6f28fd49d84c44d7602a6036a0358a865bfaef Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Wed, 30 Nov 2016 13:28:49 +0200
Subject: [PATCH 2/2] Fix MSVC build

---
 src/include/pg_config.h.win32 | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/src/include/pg_config.h.win32 b/src/include/pg_config.h.win32
index 8892c3c..ceb8b79 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
 
-- 
2.10.2

Michael Paquier

michael.paquier@gmail.com

about 9 years ago

In reply to: Heikki Linnakangas (#3)

Re: Random number generation, take two

On Wed, Nov 30, 2016 at 8:51 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

On 11/30/2016 09:01 AM, Michael Paquier wrote:
I was thinking that with --disable-strong-random, we'd use plain random() in
libpq as well. I believe SCRAM is analogous to the MD5 salt generation in
the backend, in its requirement for randomness.

OK. That's fine by me to do so.

As this patch stands, it removes Fortuna, and returns known-weak keys,
but
there's a good argument to be made for throwing an error instead.

IMO, leading to an error would make the users aware of them playing
with the fire... Now pademelon's owner may likely have a different
opinion on the matter :p

Ok, I bit the bullet and modified those pgcrypto functions that truly need
cryptographically strong random numbers to throw an error with
--disable-strong-random. Notably, the pgp encrypt functions mostly fail now.

The alternate output looks good to me.

+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);
Shouldn't an exclusive lock be taken only when the initialization
phase is called? When reading the value a shared lock would be fine.

No, it needs to be exclusive. Each pg_jrand48() call updates the state, aka
seed.

Do we need to worry about performance in the case of application doing
small transactions and creating new connections for each transaction?
This would become a contention point when calculating cancel keys for
newly-forked backends. It could be rather easy to measure a
concurrency impact with for example pgbench -C with many concurrent
transactions running something as light as SELECT 1.

Attached is a patch for MSVC to apply on top of yours to enable the
build for strong and weak random functions. Feel free to hack it as
needs be, this base implementation works for the current
implementation.

Great, thanks! I wonder if this is overly complicated, though. For
comparison, we haven't bothered to expose --disable-spinlocks in
config_default.pl either. Perhaps we should just always use the Windows
native function on MSVC, whether or not configured with OpenSSL, and just
put USE_WIN32_RANDOM in pg_config.h.win32? See 2nd attached patch
(untested).

I could live with that. Your patch is not complete though, you need to
add pg_strong_random.c into the array @pgportfiles in Mkvcbuild.pm.
You also need to remove fortuna.c and random.c from the list of files
in $pgcrypto->AddFiles(). After doing so the code is able to compile
properly.

+               (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+                errmsg("pg_random_bytes() is not supported by this build"),
+                errdetail("This functionality requires a source of
strong random numbers"),
+                errhint("You need to rebuild PostgreSQL using
--enable-strong-random")));
Perhaps this should say "You need to rebuild PostgreSQL without
--disable-strong-random", the docs do not mention
--enable-strong-random nor does ./configure --help.

+/* port/pg_strong_random.c */
+#ifndef USE_WEAK_RANDOM
+extern bool pg_strong_random(void *buf, size_t len);
+#endif
This should be HAVE_STRONG_RANDOM.
-- 
Michael

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Alvaro Herrera

alvherre@2ndquadrant.com

about 9 years ago

In reply to: Heikki Linnakangas (#3)

Re: Random number generation, take two

Heikki Linnakangas wrote:

On 11/30/2016 09:01 AM, Michael Paquier wrote:

It is important that this value [nonce] be different for each
authentication (see [RFC4086] for more details on how to achieve
this)

So the nonces need to be different for each session, to avoid replay
attacks. But they don't necessarily need to be unpredictable, they are
transmitted in plaintext during the authentication, anyway. If an attacker
can calculate them in advance, it only buys him more time, but doesn't give
any new information.

If we were 100% confident on that point, we could just always use current
timestamp and a counter for the nonces. But I'm not that confident,
certainly feels better to use a stronger random number when available.

Hmm, if enough internal server state leaks through the nonce (PID
generation rate), since the generating algorithm is known, isn't it
feasible for an attacker to predict future nonces? That would make
brute-force attacks practical. Perhaps it's enough to have a #define to
enable a weak RNG to be used for nonces when --disable-strong-random.
That way you're protected by default because the auth mechanism doesn't
even work if you don't have a strong RNG, but you can enable it
knowingly if you so desire.

--
ï¿½lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Heikki Linnakangas

hlinnaka@iki.fi

about 9 years ago

In reply to: Alvaro Herrera (#5)

Re: Random number generation, take two

On 11/30/2016 09:05 PM, Alvaro Herrera wrote:

Heikki Linnakangas wrote:

On 11/30/2016 09:01 AM, Michael Paquier wrote:

It is important that this value [nonce] be different for each
authentication (see [RFC4086] for more details on how to achieve
this)

So the nonces need to be different for each session, to avoid replay
attacks. But they don't necessarily need to be unpredictable, they are
transmitted in plaintext during the authentication, anyway. If an attacker
can calculate them in advance, it only buys him more time, but doesn't give
any new information.

If we were 100% confident on that point, we could just always use current
timestamp and a counter for the nonces. But I'm not that confident,
certainly feels better to use a stronger random number when available.

Hmm, if enough internal server state leaks through the nonce (PID
generation rate), since the generating algorithm is known, isn't it
feasible for an attacker to predict future nonces?

Yes.

That would make brute-force attacks practical.

For SCRAM, you still need to reverse the SHA-256 hash that's used in the
protocol. That's not practical even if you have plenty of time.

Reversing the MD5 hash used in MD5 authentication, on the other hand...
But note that this patch makes the situation better for platforms that
do have a strong random source. Currently, we always rely on random(),
but with this patch, we'll use a strong source.

Perhaps it's enough to have a #define to enable a weak RNG to be used
for nonces when --disable-strong-random. That way you're protected by
default because the auth mechanism doesn't even work if you don't
have a strong RNG, but you can enable it knowingly if you so desire.

That's overdoing it, IMHO. Any modern system will have a source of
randomness, we're in practice only talking about pademelon and similar
ancient or super-exotic systems. And --disable-strong-random is the
escape hatch for that: you can use it if you don't care, but it makes it
an explicit decision.

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Michael Paquier

michael.paquier@gmail.com

about 9 years ago

In reply to: Michael Paquier (#4)

Re: Random number generation, take two

On Wed, Nov 30, 2016 at 10:22 PM, Michael Paquier
<michael.paquier@gmail.com> wrote:

On Wed, Nov 30, 2016 at 8:51 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
On 11/30/2016 09:01 AM, Michael Paquier wrote:
+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);
Shouldn't an exclusive lock be taken only when the initialization
phase is called? When reading the value a shared lock would be fine.
Do we need to worry about performance in the case of application doing
small transactions and creating new connections for each transaction?
This would become a contention point when calculating cancel keys for
newly-forked backends. It could be rather easy to measure a
concurrency impact with for example pgbench -C with many concurrent
transactions running something as light as SELECT 1.

I got curious about this point, so I have done a couple of tests with
my laptop using the following pgbench command:
pgbench -f test.sql -C -c 128 -j 4 -t 100
And test.sql is just that:
\set aid random(1,10)
In short, a backend is spawned and a cancel key is generated but
nothing is done with it to avoid any overhead. With HEAD and the patch
without/with --disable-strong-random, I am seeing pretty close
numbers. My laptop has only 4 cores, so we may see something on a
machine with a higher number of cores. But as far as things go I am in
the noise range.
--
Michael

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Heikki Linnakangas

hlinnaka@iki.fi

about 9 years ago

In reply to: Michael Paquier (#4)

Re: Random number generation, take two

On 11/30/2016 03:22 PM, Michael Paquier wrote:

On Wed, Nov 30, 2016 at 8:51 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

On 11/30/2016 09:01 AM, Michael Paquier wrote:

Attached is a patch for MSVC to apply on top of yours to enable the
build for strong and weak random functions. Feel free to hack it as
needs be, this base implementation works for the current
implementation.

Great, thanks! I wonder if this is overly complicated, though. For
comparison, we haven't bothered to expose --disable-spinlocks in
config_default.pl either. Perhaps we should just always use the Windows
native function on MSVC, whether or not configured with OpenSSL, and just
put USE_WIN32_RANDOM in pg_config.h.win32? See 2nd attached patch
(untested).

I could live with that. Your patch is not complete though, you need to
add pg_strong_random.c into the array @pgportfiles in Mkvcbuild.pm.
You also need to remove fortuna.c and random.c from the list of files
in $pgcrypto->AddFiles(). After doing so the code is able to compile
properly.

Ok, did that, I hope I got it right.

+               (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+                errmsg("pg_random_bytes() is not supported by this build"),
+                errdetail("This functionality requires a source of
strong random numbers"),
+                errhint("You need to rebuild PostgreSQL using
--enable-strong-random")));
Perhaps this should say "You need to rebuild PostgreSQL without
--disable-strong-random", the docs do not mention
--enable-strong-random nor does ./configure --help.

I could go either way, but I left it as it is, to avoid the double
negative "without disable".

+/* port/pg_strong_random.c */
+#ifndef USE_WEAK_RANDOM
+extern bool pg_strong_random(void *buf, size_t len);
+#endif
This should be HAVE_STRONG_RANDOM.

Fixed.

Pushed with those fixes. Let's see what the buildfarm thinks now.

Tom: I expect pademelon to fail at the configure step, complaining that
"no source of strong random numbers was found". Let's wait for one
cycle, to verify that it does fail like that. After that, can you add
the --disable-strong-random flag to fix it, please?

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Michael Paquier

michael.paquier@gmail.com

about 9 years ago

In reply to: Heikki Linnakangas (#8)

Re: Random number generation, take two

On Mon, Dec 5, 2016 at 8:45 PM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

On 11/30/2016 03:22 PM, Michael Paquier wrote:

I could live with that. Your patch is not complete though, you need to
add pg_strong_random.c into the array @pgportfiles in Mkvcbuild.pm.
You also need to remove fortuna.c and random.c from the list of files
in $pgcrypto->AddFiles(). After doing so the code is able to compile
properly.

Ok, did that, I hope I got it right.

The build works for me. Thanks.
--
Michael

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

#10

Tom Lane

tgl@sss.pgh.pa.us

about 9 years ago

In reply to: Heikki Linnakangas (#8)

Re: Random number generation, take two

Heikki Linnakangas <hlinnaka@iki.fi> writes:

Tom: I expect pademelon to fail at the configure step, complaining that
"no source of strong random numbers was found". Let's wait for one
cycle, to verify that it does fail like that. After that, can you add
the --disable-strong-random flag to fix it, please?

Roger, I'll deal with that later today.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

#11

Tom Lane

tgl@sss.pgh.pa.us

about 9 years ago

In reply to: Tom Lane (#10)

Re: Random number generation, take two

I wrote:

Heikki Linnakangas <hlinnaka@iki.fi> writes:

Tom: I expect pademelon to fail at the configure step, complaining that
"no source of strong random numbers was found". Let's wait for one
cycle, to verify that it does fail like that. After that, can you add
the --disable-strong-random flag to fix it, please?

Roger, I'll deal with that later today.

Results seem to be as expected:

http://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=pademelon&dt=2016-12-05%2016%3A14%3A10

http://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=pademelon&dt=2016-12-05%2022%3A19%3A42

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

#12

Michael Paquier

michael.paquier@gmail.com

about 9 years ago

In reply to: Tom Lane (#11)

Re: Random number generation, take two

On Tue, Dec 6, 2016 at 10:31 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I wrote:

Heikki Linnakangas <hlinnaka@iki.fi> writes:

Tom: I expect pademelon to fail at the configure step, complaining that
"no source of strong random numbers was found". Let's wait for one
cycle, to verify that it does fail like that. After that, can you add
the --disable-strong-random flag to fix it, please?

Roger, I'll deal with that later today.

Results seem to be as expected:

http://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=pademelon&dt=2016-12-05%2016%3A14%3A10

http://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=pademelon&dt=2016-12-05%2022%3A19%3A42

Nice to see. I'll send a rebased patch set for SCRAM soon now that we
know that things are fine here.
--
Michael

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers