Обсуждение: Random number generation, take two

Ok, here's my second attempt at refactoring random number generation.
Previous attempt crashed and burned, see
https://www.postgresql.org/message-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

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
> https://www.postgresql.org/message-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

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

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

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

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

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

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

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

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

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

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