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)