# Can you explain the entropy estimate used in random.c

`/dev/random` uses the timings of kernel interupts to add to the entropy pool. The amount of entropy in the pool is tracked in a variable named `entropy_count`.

Here is the relevant snippet of code from `random.c`. It represents the time (in jiffies I think) between the last two interupts in variable `delta` and the differences in deltas as `delta2`.

``````delta = time - state->last_time;
state->last_time = time;

delta2 = delta - state->last_delta;
state->last_delta = delta;

if (delta < 0) delta = -delta;
if (delta2 < 0) delta2 = -delta2;
delta = MIN(delta, delta2) >> 1;
for (nbits = 0; delta; nbits++)
delta >>= 1;

r->entropy_count += nbits;

/* Prevent overflow */
if (r->entropy_count > POOLBITS)
r->entropy_count = POOLBITS;
``````

It looks like the estimate of the entropy added is essentially the floor (not ceil because of the initial bitshift before the loop) of base 2 logarithm of delta. This makes some intuitive sense, though I'm not sure what assumptions would be needed to make this formally correct.

So, my first question is "what is the reasoning behind this estimate?"

My second question is about `delta = MIN(delta, delta2) ...`. What does this do? Why take the minimum of this delta and the last one? I don't know what this is supposed to achieve - perhaps it makes the estimate better, maybe just more conservative.

Edit: I've found a paper that specifies the estimate, but it doesn't really give a reasoned argument for it (though it does outline some informal conditions that the estimator should meet).

Other resources that have come up in the comments:

• Note that the value of the entropy estimate in Linux's `/dev/random` is on a shaky foundation — see Feeding /dev/random entropy pool?. I've pinged Thomas in the hope that he'll answer your question. – Gilles May 13 '14 at 23:52
• If anyone is interested in this topic the treatment about it in Wikipedia is a pretty good starting point: en.wikipedia.org/wiki//dev/random – slm May 14 '14 at 0:10
• @Lucas - take a look at this paper as well: [An interpretation of the Linux entropy estimator ](eprint.iacr.org/2012/487.pdf) – slm May 14 '14 at 0:25
• @slm Interesting, though I'm not sure it's correct - the step of justifying the minimum function using Kolmogorov complexity is a big leap in reasoning and it's not clear to me that this conceptually sound. – Lucas May 14 '14 at 0:52
• @Lucas - Thought I'd pass it along, I'm out of my league w/ this Q 8-) – slm May 14 '14 at 0:55

## 1 Answer

`delta2` is not the previous `delta`, but the difference between two successive values of `delta`. It is a kind of derivative: if `delta` measures the speed, `delta2` is the acceleration.

The intuitive idea behind that estimate is that interrupts occur at more or less random intervals, dictated by unpredictable events from the physical world (e.g. key strokes or arrival of network packets). The longer the delay, the more unpredictable events are involved. However, there are physical systems which fire interrupts at a fixed rate; the `delta2` measure is a protection mechanism which detects such occurrences (if interrupts occur at fixed intervals, hence decidedly predictable, all `delta` will have the same value, hence `delta2` will be zero).

I said "intuitive" and there is not much more to say. In fact, in the "random physical events" model, counting the bits is wrong; if an hardware event occurs with probability p for each time unit, and you get a delay expressed over n bits, then the entropy contribution should be accounted as n/2 bits, not n bits. But we know that in reality the physical events don't occur at exactly random moments; the `delta2` mechanism admits as much.

So in practice, the "entropy estimate" is exactly that: an estimate. Its security value does not come from a well-reasoned, mathematically exact justification, but from the usual source of security: nobody seems to have found a way to abuse it (yet).

This page was written by someone who got fed up with the myths about `/dev/random` and its entropy estimator, and I think it explains things well, with enough details. It is important to get some basic ideas right when dealing with RNG.

• Ooops, I misspoke, I should have said change in deltas. I have to say that most estimates do have a "well-reasoned, mathematically exact justification", that's what differentiates them from guesses - and if it works at all it should have some formal justification. It's totally fine not to care about these things and only care about the pragmatics of security, but this isn't true for everyone. Not agreeing on what is interesting is not a matter of getting "basic ideas right". – Lucas May 14 '14 at 15:54
• I'm not saying that your wrong in it being a practical estimate for the purposes it was designed. – Lucas May 14 '14 at 16:07