The /dev/random device driver need not concern itself with root adversaries as this type of user has permissions to read and overwrite memory - this user even possesses permission to replace the kernel elf binary with a copy of /dev/random that always returns the number 0 - that is their right.
This whole issue of leaks is because we are relying upon fast but insecure hash-function-like methods to extract data from a sensitive pool. LFSR and CRC32 (which was used in an earlier version of /dev/random) have similarities to secure hash functions - but "aren't good enough for military work" - which is why we are even discussing the topic of leakage.
If we use a secure primitive in the right way - preferably one that is faster than SHA1 - such as chcha20 or even faster still AES-NI (both in a feedback mode). Then the leakage is stopped. If the pool cannot leak then we do not need an entropy counter which is the mutex that handle_irq_event_percpu() fights over. This reduces interrupt latency, reduces computational load of all interrupts, and helps contribute to the pool being less predictable because now an outside construct has to account for race conditions.
-Michael
On Wed, Mar 30, 2022 at 10:10 AM Michael Brooks m@sweetwater.ai wrote:
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)