Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Date:   Wed, 1 Apr 2020 05:17:59 +0000
From:   George Spelvin <lkml@SDF.ORG>
To:     "Theodore Y. Ts'o" <tytso@mit.edu>
Cc:     David Laight <David.Laight@ACULAB.COM>,
        Dan Williams <dan.j.williams@intel.com>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        Qian Cai <cai@lca.pw>, Kees Cook <keescook@chromium.org>,
        Michal Hocko <mhocko@suse.com>,
        Andrew Morton <akpm@linux-foundation.org>,
        Linux MM <linux-mm@kvack.org>,
        Thomas Garnier <thgarnie@google.com>, lkml@sdf.org
Subject: lib/random32.c security
Message-ID: <20200401051759.GA9616@SDF.ORG>
References: <202003281643.02SGhPmY017434@sdf.org>
 <CAPcyv4iagZy5m3FpMrQqyOi=_uCzqh5MjbW+J_xiHU1Z1BmF=g@mail.gmail.com>
 <20200328182817.GE5859@SDF.ORG>
 <98bd30f23b374ccbb61dd46125dc9669@AcuMS.aculab.com>
 <20200329174122.GD4675@SDF.ORG>
 <20200329214214.GB768293@mit.edu>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20200329214214.GB768293@mit.edu>
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On Sun, Mar 29, 2020 at 05:42:14PM -0400, Theodore Y. Ts'o wrote:
> If anyone is trying to rely on prandom_u32() as being "strong" in any
> sense of the word in terms of being reversable by attacker --- they
> shouldn't be using prandom_u32().  That's going to be true no matter
> *what* algorithm we use.
> 
> Better distribution?  Sure.  Making prandom_u32() faster?  Absolutely;
> that's its primary Raison d'Etre.

I'd like your comments on an idea I had to add a second PRNG state
for security-interesting applications.

There are some ASLR tasks, notably slab freelist shuffling and
per-syscall stack offset randomization, which need a Very Fast
source of random numbers.  No crypto-grade generator qualifies,
and both currently use very bad ad-hoc generators.

The per-syscall stack offset code currently uses the lsbits of the
TSC, which is obviously bad as they're observable by the (presumed
malicious) userspace immediately before the call and thus highly
predictable.

Likewise, the slab shuffling currently precomputes a permutation and
just picks a random starting position for every slab.

Both are saved by the fact that their PRNG outputs are mostly
unobservable, so an attacker can't start to predict them.

I was thinking that a second PRNG, identical to the prandom_u32()
one but seeded speartely, could be used for this purpose.  The good
distribution would preclude trivial patterns in their output, which
is about all we can hope for.

The difference is that it would only be used for applications which
both require high speed and are (mostly) unobservable to an attacker.


Any opinions, anyone?