Re: [HACKERS] Random number generation, take two

[Michael Paquier]

On Tue, Dec 6, 2016 at 10:31 AM, Tom Lane  wrote:
> I wrote:
>> Heikki Linnakangas  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=2016-12-05%2016%3A14%3A10
>
> http://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=pademelon=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

Re: [HACKERS] Random number generation, take two

[Tom Lane]

I wrote:
> Heikki Linnakangas  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=2016-12-05%2016%3A14%3A10

http://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=pademelon=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

Re: [HACKERS] Random number generation, take two

[Tom Lane]

Heikki Linnakangas  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

Re: [HACKERS] Random number generation, take two

[Michael Paquier]

On Mon, Dec 5, 2016 at 8:45 PM, Heikki Linnakangas  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

Re: [HACKERS] Random number generation, take two

[Heikki Linnakangas]

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

On Wed, Nov 30, 2016 at 8:51 PM, Heikki Linnakangas  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

Re: [HACKERS] Random number generation, take two

[Michael Paquier]

On Wed, Nov 30, 2016 at 10:22 PM, Michael Paquier
 wrote:
> On Wed, Nov 30, 2016 at 8:51 PM, Heikki Linnakangas  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

Re: [HACKERS] Random number generation, take two

[Heikki Linnakangas]

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

Re: [HACKERS] Random number generation, take two

[Alvaro Herrera]

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 Herrerahttps://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

Re: [HACKERS] Random number generation, take two

[Michael Paquier]

On Wed, Nov 30, 2016 at 8:51 PM, Heikki Linnakangas  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

Re: [HACKERS] Random number generation, take two

[Heikki Linnakangas]

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

On Tue, Nov 29, 2016 at 10:02 PM, Heikki Linnakangas  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 

Re: [HACKERS] Random number generation, take two

[Michael Paquier]

On Tue, Nov 29, 2016 at 10:02 PM, Heikki Linnakangas  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...@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


strong_random_msvc.patch
Description: invalid/octet-stream

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