Re: [PATCH AUTOSEL 5.17 16/43] random: use computational hash for entropy extraction

Michael Brooks
2022-03-30T17:10:52Z

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> wrote:
>
> 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)