Date:   Wed, 30 Mar 2022 16:49:25 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     'Michael Brooks' <m@...etwater.ai>, Sasha Levin <sashal@...nel.org>
CC:     Dominik Brodowski <linux@...inikbrodowski.net>,
        Eric Biggers <ebiggers@...gle.com>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        "Jason A. Donenfeld" <Jason@...c4.com>,
        Jean-Philippe Aumasson <jeanphilippe.aumasson@...il.com>,
        Theodore Ts'o <tytso@....edu>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        "stable@...r.kernel.org" <stable@...r.kernel.org>
Subject: RE: [PATCH AUTOSEL 5.17 16/43] random: use computational hash for
 entropy extraction

From: Michael Brooks
> Sent: 30 March 2022 17:08
...
> I’d like to describe this bug using mathematics, because that is 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 “p” be the overall pool state and let
> “n” be the good unknown values added to the pool.  Finally, let “k” be
> the known values - such as jiffies.  If we then describe the ratio of
> unknown uniqueness with known uniqueness as p=n/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’ (that is
> pronounced “p-prime” for those who don’t get the notation).  let
> p’=n’/k’. In this case the attacker has no hope of constructing n’,
> but they can construct k’ - therefore the attacker’s parasol model of
> the pool p’ will become more accurate as the attack persists leading
> to p’ = p as time->∞.
> 
> 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)

Powered by blists - more mailing lists