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@xxxxxxxxxx> 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)
