Date: Tue, 13 Nov 2018 21:34:12 -0800
From: Noah Misch <noah@leadboat.com>
To: Thomas Munro <thomas.munro@enterprisedb.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>, Pg Hackers <pgsql-hackers@postgresql.org>
Subject: Re: DSM segment handle generation in background workers
Message-ID: <20181114053412.GD1096408@rfd.leadboat.com>
References: <17043.1539046409@sss.pgh.pa.us>
 <CAEepm=2RqzvRyEXWxq8B9zR8p45tt-xsvA4S8ZNKNwpiUzMVKA@mail.gmail.com>
 <CAEepm=1xxETRCZexNSxkABpNg-65U6Z2pxynJ8V0vURqob+Rqw@mail.gmail.com>
 <9879.1539233472@sss.pgh.pa.us>
 <CAEepm=20PEf5bM3FAtD=CL7x0_WxFXfQ4Se9N9nConKucsr8pg@mail.gmail.com>
 <20181112083358.GA1073796@rfd.leadboat.com>
 <CAEepm=1+1jZiNHuRKaHgKZz1f=RFd8BnFpSgVsxEFNafjsqWZg@mail.gmail.com>
 <32455.1542033541@sss.pgh.pa.us>
 <20181114022435.GC1096408@rfd.leadboat.com>
 <CAEepm=1COuNcj_va0Qt2KTEE4rDvhWCixZ-pyh8iUbrusEVBzQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: 
 <CAEepm=1COuNcj_va0Qt2KTEE4rDvhWCixZ-pyh8iUbrusEVBzQ@mail.gmail.com>
User-Agent: Mutt/1.5.24 (2015-08-30)
Precedence: bulk

On Wed, Nov 14, 2018 at 05:50:26PM +1300, Thomas Munro wrote:
> On Wed, Nov 14, 2018 at 3:24 PM Noah Misch <noah@leadboat.com> wrote:
> > On Mon, Nov 12, 2018 at 09:39:01AM -0500, Tom Lane wrote:
> > > I doubt that's a good idea; to a first approximation, it would mean that
> > > half the seed depends only on the PID and the other half only on the
> > > timestamp.  Maybe we could improve matters a little by left-shifting the
> > > PID four bits or so, but I think we still want it to mix with some
> > > rapidly-changing time bits.
> > >
> > > I'm not really sure that we need to do anything though.  Basically,
> > > what we've got here is a tradeoff between how many bits change over
> > > a given timespan and how unpredictable those bits are.  I don't see
> > > that one of those is necessarily more important than the other.
> >
> > What counts is the ease of predicting a complete seed.  HEAD's algorithm has
> > ~13 trivially-predictable bits, and the algorithm that stood in BackendRun()
> > from 98c5065 until 197e4af had no such bits.  You're right that the other 19
> > bits are harder to predict than any given 19 bits under the old algorithm, but
> > the complete seed remains more predictable than it was before 197e4af.
> 
> However we mix them, given that the source code is well known, isn't
> an attacker's job really to predict the time and pid, two not
> especially well guarded secrets?

True.  Better to frame the issue as uniform distribution of seed, not
unpredictability of seed selection.

Incidentally, possible future work may be to use pg_strong_random() when
available, like pgbench set_random_seed() does.  That would achieve both
unpredictability and uniform distribution.  It would be mere defense in depth;
if unpredictability matters, one still needs a CSPRNG (e.g. pgcrypto).