Messages in this thread | | | Date | Wed, 15 Aug 2012 13:37:23 -0700 | From | "H. Peter Anvin" <> | Subject | Re: [PATCH RFC] random: Account for entropy loss due to overwrites |
| |
On 08/15/2012 12:30 PM, Matt Mackall wrote: > On Mon, 2012-08-13 at 10:26 -0700, H. Peter Anvin wrote: >> From: "H. Peter Anvin" <hpa@linux.intel.com> >> >> When we write entropy into a non-empty pool, we currently don't >> account at all for the fact that we will probabilistically overwrite >> some of the entropy in that pool. > > Technically, no, nothing is overwritten. The key fact is that the mixing > function is -reversible-. Thus, even if you mix in known data, you can't > learn anything about the state and thus can't destroy any of the > existing entropy. > > But you are correct, mixing new actual entropy is not purely additive > (with saturation). For that to happen, we'd need an input mixing > function with perfect maximal cascading. Instead we effectively cascade > across somewhere between 6 and 64 bits. So the truth lies somewhere > between linear and your exponential estimate (which would be the case > for mixing a single bit into the pool with XOR), but much closer to > linear due to combinatoric expansion. >
I think you have it backwards; if the input was a FIFO, with no mixing at all, and no reuse, the linear estimate would be correct. The mixing into an already-existent and potentially-observed pool is what causes the exponential estimate to apply... although it is assuming perfect mixing. However, I believe it is still correct in the aggregate.
> On the other hand, I don't think this sort of thing matters at all. > There is so much more fundamentally wrong with even trying to do entropy > accounting in the first place that these sorts of details don't even > matter. Instead we should stop fooling ourselves and just drop the > pretense of accounting entirely. Now that we've got a much richer set of > inputs, I think the time is ripe... but of course, I'm no longer the > maintainer.
If we're going to fundamentally change the structure perhaps we should actually take the suggestions long offered from the cryptographic community, and look at structures like Fortuna.
-hpa
| |