Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
MIME-Version: 1.0
References: <20220328111828.1554086-1-sashal@kernel.org> <20220328111828.1554086-16-sashal@kernel.org>
 <CAOnCY6TTx65+Z7bBwgmd8ogrCH78pps59u3_PEbq0fUpd1n_6A@mail.gmail.com> <9e78091d07d74550b591c6a594cd72cc@AcuMS.aculab.com>
In-Reply-To: <9e78091d07d74550b591c6a594cd72cc@AcuMS.aculab.com>
From:   Michael Brooks <m@sweetwater.ai>
Date:   Wed, 30 Mar 2022 10:10:37 -0700
Message-ID: <CAOnCY6QNPUC-VK+ARLb6i_UskV2CkW+AG5ZqWe_oMGUumL9Gnw@mail.gmail.com>
Subject: Re: [PATCH AUTOSEL 5.17 16/43] random: use computational hash for
 entropy extraction
To:     David Laight <David.Laight@aculab.com>
Cc:     Sasha Levin <sashal@kernel.org>,
        Dominik Brodowski <linux@dominikbrodowski.net>,
        Eric Biggers <ebiggers@google.com>,
        Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
        "Jason A. Donenfeld" <Jason@zx2c4.com>,
        Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>,
        "Theodore Ts'o" <tytso@mit.edu>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        "stable@vger.kernel.org" <stable@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

Of course I am assuming local user non-root access.  One does not need
to reverse the mix operations in order to form a parallel construction
- a one way function is sufficient for such a construct as both sides
will operate on the data in the same manner.

This attack scenario is simply a non-issue in keypoolrandom.
https://github.com/TheRook/KeypoolRandom

On Wed, Mar 30, 2022 at 9:49 AM David Laight <David.Laight@aculab.com> wrot=
e:
>
> From: Michael Brooks
> > Sent: 30 March 2022 17:08
> ...
> > I=E2=80=99d like to describe this bug using mathematics, because that i=
s how I
> > work - I am the kind of person that appreciates rigor.  In this case,
> > let's use inductive reasoning to illuminate this issue.
> >
> > Now, in this attack scenario let =E2=80=9Cp=E2=80=9D be the overall poo=
l state and let
> > =E2=80=9Cn=E2=80=9D be the good unknown values added to the pool.  Fina=
lly, let =E2=80=9Ck=E2=80=9D be
> > the known values - such as jiffies.  If we then describe the ratio of
> > unknown uniqueness with known uniqueness as p=3Dn/k then as a k grows
> > the overall predictability of the pool approaches an infinite value as
> > k approaches zero.   A parallel pool, let's call it p=E2=80=99 (that is
> > pronounced =E2=80=9Cp-prime=E2=80=9D for those who don=E2=80=99t get th=
e notation).  let
> > p=E2=80=99=3Dn=E2=80=99/k=E2=80=99. In this case the attacker has no ho=
pe of constructing n=E2=80=99,
> > but they can construct k=E2=80=99 - therefore the attacker=E2=80=99s pa=
rasol model of
> > the pool p=E2=80=99 will become more accurate as the attack persists le=
ading
> > to p=E2=80=99 =3D p as time->=E2=88=9E.
> >
> > Q.E.D.
>
> That rather depends on how the (not) 'randmoness' is added to the pool.
> If there are 'r' bits of randomness in the pool and a 'stir in' a pile
> of known bits there can still be 'n' bits of randomness in the pool.
>
> The whole thing really relies on the non-reversability of the final prng.
> Otherwise if you have 'r' bits of randomness in the pool and 'p' bits
> in the prng you only need to request 'r + p' bits of output to be able
> to solve the 'p + r' simultaneous equations in 'p + r' unknowns
> (I think that is in the field {0, 1}).
>
> The old kernel random number generator that used xor to combine the
> outputs of several LFSR is trivially reversable.
> It will leak whatever it was seeded with.
>
> The non-reversability of the pool isn't as important since you need
> to reverse the prng as well.
>
> So while, in some sense, removing 'p' bits from the entropy pool
> to seed the prng only leaves 'r - p' bits left.
> That is only true if you think the prng is reversable.
> Provided 'r > p' (preferably 'r >> p') you can reseed the prng
> again (provided you take reasonably random bits) without
> really exposing any more state to an attacker.
>
> Someone doing cat /dev/urandom >/dev/null should just keep reading
> values out of the entropy pool.
> But if they are discarding the values that shouldn't help them
> recover the state of the entropy pool or the prng - even if only
> constant values are being added to the pool.
>
> Really what you mustn't do is delete the bits used to seed the prng
> from the entropy pool.
> About the only way to actually reduce the randomness of the entropy
> pool is if you've discovered what is actually in it, know the
> 'stirring' algorithm and feed in data that exactly cancels out
> bits that are present already.
> I suspect that anything with root access can manage that!
> (Although they can just overwrite the entropy pool itself,
> and the prng for that matter.)
>
>         David
>
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1=
 1PT, UK
> Registration No: 1397386 (Wales)