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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAOnCY6QNPUC-VK+ARLb6i_UskV2CkW+AG5ZqWe_oMGUumL9Gnw@mail.gmail.com>
Date:   Wed, 30 Mar 2022 10:10:37 -0700
From:   Michael Brooks <m@...etwater.ai>
To:     David Laight <David.Laight@...lab.com>
Cc:     Sasha Levin <sashal@...nel.org>,
        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

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@...lab.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)