Todays Apple Event has just started: https://www.apple.com/apple-events/event-stream/

Has anyone ever understood Linux’s entropy estimation available at /proc/sys/kernel/random/entropy_avail? I mean the algorithm. The strategy (expressed in C) is https://raw.githubusercontent.com/torvalds/linux/f227e3ec3b5cad859ad15666874405e8c1bbc1d4/drivers/char/random.c\|here. (See procedure add_timer_randomness().) It’s very simple — they keep 3 deltas which are the distances between events, expressed in jiffies (an oscillation of the computer’s clock). Once the 3 deltas are available, they pick the smallest one and compute its lg (logarithm in base 2). That’s an estimate of how much entropy the last four events produced.

Why does that work? (Or doesn’t it?)

My intuition leads me to the following type of argument. Suppose I’m trying to predict when an event will happen. By looking at the distance between each two adjacent events, I have an idea of how often they occur. I can use this information to guess when the next will happen. Every time I make a mistake, there’s an error. Then I look at this error as a random variable. The greater the error, the more entropy I have — because otherwise I’m guessing well, so I’m predicting well (and that’s low entropy). To be conservative, I take the smallest error (my best prediction) and estimate entropy based on my best prediction, so my entropy estimate is conservative.

In more precise terms now. The variable delta is a random variable of how far apart events occur. The variable delta2 is another random variable and it describes my error in guessing the exact moment of events. The variable delta3 describes my error in guessing delta2. What is my guess (the kernel’s guess)? My guess is that the next thing to happen will be the same as the previous. (That’s why subtraction is the operation that checks whether I guessed right. If I got it right, the subtraction yields zero and so I have zero entropy. If the subtraction produces a big number, then I’m very far off, so I got a lot of entropy.) However, instead of just one random variable, I got three — and so I look at the one that’s doing better and I estimate it based on that one — a conservative position.

Why do I why compute the lg? My only answer to that is that logarithms are the only (mathematical) functions that satisfy <https://pure.mpg.de/rest/items/item_2383162_7/component/file_2456978/content|Shannon’s axioms for entropy> [see section 6, pages 392—393, PDF-pages 14—15]. An estimate is a measure of how much information (in Shannon’s sense) is there, so I must satisfy the requirements, otherwise I am not measuring information-quantity in the way I intend to — in the way Shannon intended to.

What explanations are out there? I have not found any documentation anywhere that explains the theory behind it. It must be because the theory is pretty obvious? The two papers below are also trying to understand it. The first proposes a theory that explains the estimate — I don’t get it and I’m not sure about it at all. The second one doesn’t try to understand and remarks that random.c did not explain it.

Benjamin Pousse. An interpretation of the linux entropy estimator. Cryptology ePrint Archive Report available at http://eprint.iacr.org/2012/487, 2012. URL: https://eprint.iacr.org/2012/487.pdf

François Goichon, Cédric Lauradoux, Guillaume Salagnac, Thibaut Vuillemin. Entropy transfers in the Linux Random Number Generator. [Research Report] RR–8060, INRIA. 2012, pp.26. ffhal00738638f URL: https://hal.inria.fr/hal-00738638/file/rr8060.pdf