Received-SPF: pass (google.com: domain of linux-crypto-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
MIME-Version: 1.0
References: <CALFqKjSnOWyFjp7NQZKMXQ+TfzXMCBS=y8xnv5GE56SHVr5tCg@mail.gmail.com>
 <CACXcFmnRAkrj0Q3uFjyLu7RaWQh0VPbmErkj+cUaxZMb=YiGCw@mail.gmail.com>
 <CACXcFmmW+tCUf8JS=a=wJEnBY2JojP8VwEGLncYcGLZqiU+5Jw@mail.gmail.com>
 <CACXcFmmosvNMxwjOFZ9SDadqJE11w6Vva+i9AV1zYQxbwoB9sA@mail.gmail.com> <YRp1YbpFdNG0IJMI@mit.edu>
In-Reply-To: <YRp1YbpFdNG0IJMI@mit.edu>
From:   Sandy Harris <sandyinchina@gmail.com>
Date:   Thu, 27 Jan 2022 08:35:54 +0800
Message-ID: <CACXcFmmSBZ3zzpPOCtQ7Sp7y3cAcwi54kZP894PGR8DzHny_UQ@mail.gmail.com>
Subject: Re: Lockless /dev/random - Performance/Security/Stability improvement
To:     "Theodore Ts'o" <tytso@mit.edu>,
        "Jason A. Donenfeld" <Jason@zx2c4.com>
Cc:     Linux Crypto Mailing List <linux-crypto@vger.kernel.org>,
        Stephan Mueller <smueller@chronox.de>,
        John Denker <jsd@av8n.com>, m@ib.tc
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Mon, Aug 16, 2021 at 10:25 PM Theodore Ts'o <tytso@mit.edu> wrote:

> On Mon, Aug 16, 2021 at 06:59:50PM +0800, Sandy Harris wrote:

> > I am by no means convinced that Mike's idea of a lockless driver is a
> > good one. Without some locks, if two or more parts of the code write
> > to the same data structure, then there's a danger one will overwrite
> > the other's contribution & we'll lose entropy.
> >
> > However, I cannot see why any data structure should be locked when it
> > is only being read. There's no reason to care if others read it as
> > well. If someone writes to it, then the result of reading becomes
> > indeterminate. In most applications, that would be a very Bad Thing.
> > In this contact, though, it is at worst harmless & possibly a Good
> > Thing because it would make some attacks harder.
> >
> > For example, looking at the 5.8.9 kernel Ubuntu gives me, I find this
> > in xtract_buf()
> >
> > /* Generate a hash across the pool, 16 words (512 bits) at a time */
> >     spin_lock_irqsave(&r->lock, flags);
> >     for (i = 0; i < r->poolinfo->poolwords; i += 16)
> >         sha1_transform(hash.w, (__u8 *)(r->pool + i), workspace);
> >
> >     /*
> >      * We mix the hash back into the pool ...
> >      */
> >     __mix_pool_bytes(r, hash.w, sizeof(hash.w));
> >     spin_unlock_irqrestore(&r->lock, flags);
> >
> > The lock is held throughout the fairly expensive hash operation & I
> > see no reason why it should be.
>
> The reason why this is there is because otherwise, there can be two
> processes both trying to extract entry from the pool, and getting the
> same result, and returning the identical "randomness" to two different
> userspace processes.  Which would be sad....  (unless you are a
> nation-state attacker, I suppose :-)

So lock the chacha context, the data structure it writes, instead.
Since the write back to the pool is inside that lock, two threads
extracting entropy will get different results. Call mix_pool_bytes()
instead of __mix_pool_bytes() and it will do the necessary
locking when the input pool is written.

I think this deals with Mike's main objection:

" It is highly unusual that /dev/random is allowed to degrade the
" performance of all other subsystems - and even bring the
" system to a halt when it runs dry.

At any rate, it reduces the chance of other code that
writes to the input pool being blocked by random(4).