Re: So much entropy it's coming out of our ears?

On Thu, 5 Aug 2004, Mark Murray wrote:

> Sam Leffler writes:
> > Virtually all performance-sensitive installations will disable entropy 
> > gathering through fast paths.  I've suggested for a long time that this sort 
> > of collection should be enabled only under dire circumstances and never by 
> > default.  Regardless the last time I looked at the entropy harvesting it used
> > a model where entropy was unilateraly sent for harvest and discarded when too
> > plentiful.  I term this the "push model".  I've advocated a "pull model" 
> > where the PRNG requests entropy when a low water mark is hit and/or a hybrid 
> > scheme where producers have some sort of flow control or feedback mechanism. 
> 
> Yarrow is not conducive to "water-mark" type flow-control, but I'm
> looking at replacing Yarrow with Fortuna (code at an advanced stage).
> This should improve things all-round. 

Could we do the rate limiting on the sender side, then, by making a
guestimate at a maximum useful entropy rate?  I.e., if we think that a
system getting entropy from 20 ethernet packets a second has enough
entropy to operate safely, there's presumably not all that much
incremental benefit to 20,000 ethernet packets a second getting fed to
yarrow (with the corresponding 80,0000 mutex operations in the interrupt
path).  If so, we can simply have a counter of some sort that cheaply
tracks how much entropy has been gathered and inhibits gathering once a
threshold is reached, with the counter reset by a callout once in a while?
This would avoid the need to introduce a replacement PRNG implementation,
which is (I assume) unlikely to happen in the next two weeks, but allow us
to avoid the cost today (it's not cheap). 

I.e., add a "entropy_gathered" int that uses a unlocked read to test for
non-zero, and is decremented while holding one of the harvesting mutexes
if it's non-zero.  Reset it in a callout a few times a second, and set it
to some small value, like 4.  This will result in the gathering of some
entropy each second, but not so much that it seriously hits the packet
delivery path in higher workloads.

Similarly, Max makes the suggestion that we can afford weaker
synchronization for gathered entropy.  This strikes me as a reasonable
idea, although I haven't given a mechanism much thought as yet.

> > Everything that goes on inside the PRNG is a separate issue.
> 
> *nod*

Other than observing the per-packet mutex operations that can be coalesced
when pulling harvested entropy off the harvesting fifos, I haven't made
any attempt to dig into the /dev/random yarrow code yet.  So much code, so
little time... :-)

Robert N M Watson             FreeBSD Core Team, TrustedBSD Projects
robert_at_fledge.watson.org      Principal Research Scientist, McAfee Research