2
$\begingroup$

The Linux kernel has an entropy source and it estimates its amount of bits in the device /proc/sys/kernel/random/entropy_avail. How can I verify that this number makes sense? I did the following experiment. The system in question is:

# uname -rvmpio
4.15.0-1050-aws #52-Ubuntu SMP Thu Sep 12 19:56:00 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

The following program prints the number of bytes of information available in each second as claimed by the kernel.

$ while true; do cat /proc/sys/kernel/random/entropy_avail; sleep 1; done | awk ' { t += 1; s += $0; print "t =",t,"sum =",s/8, "avg =", s/t/8, "now =",$0/8 }'
t = 1 sum = 86.375 avg = 86.375 now = 86.375
t = 2 sum = 174.625 avg = 87.3125 now = 88.25
t = 3 sum = 175.875 avg = 58.625 now = 1.25
t = 4 sum = 179.75 avg = 44.9375 now = 3.875
t = 5 sum = 186 avg = 37.2 now = 6.25
t = 6 sum = 186.875 avg = 31.1458 now = 0.875
[...]

The following program consumes /dev/random as much as possible and estimates how many bytes of information is practically available at each second.

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>

int main() {
  int r, bs; char b[512];
  unsigned int t = 0, n, sum = 0;
  fcntl(0, F_SETFL, fcntl(0, F_GETFL) | O_NONBLOCK);
  while (1) {
    n = 0;
    while ( (bs = read(0, b, 512)) != -1) n += bs;
    t += 1; sum += n;
    printf("t = %3d, sum = %3d, avg = %.4f :: just read %d bytes\n",
           t, sum, (float) sum/t, n);
    sleep(1);
  }
}

Here's how to compile and run it:

$ make p
cc     p.c   -o p
$ ./p < /dev/random
t =   1, sum =  20, avg = 20.0000 :: just read 20 bytes
t =   2, sum =  20, avg = 10.0000 :: just read 0 bytes
t =   3, sum =  20, avg = 6.6667 :: just read 0 bytes
t =   4, sum =  26, avg = 6.5000 :: just read 6 bytes
t =   5, sum =  26, avg = 5.2000 :: just read 0 bytes
t =   6, sum =  26, avg = 4.3333 :: just read 0 bytes
t =   7, sum =  26, avg = 3.7143 :: just read 0 bytes
[...]

Keeping the file system in high activity (while true; do find /; done), we get a certain number of bits being produced at regular intervals. Running p first to keep entropy production being consumed as much as possible and then checking out the estimate by the kernel, it seems these two numbers do not quite converge, but they are roughly close. After 100 iterations, I get the following values:

$ while true; do cat /proc/sys/kernel/random/entropy_avail; sleep 1; done | awk ' { t += 1; s += $0; print "t =",t,"sum =",s/8, "avg =", s/t/8, "now =",$0/8 }'
[...]
t = 100 sum = 1534.12 avg = 15.3413 now = 7.625
t = 101 sum = 1537.88 avg = 15.2265 now = 3.75
^C

$ ./p < /dev/random
[...]
t = 100, sum = 2002, avg = 20.0200 :: just read 0 bytes
t = 101, sum = 2014, avg = 19.9406 :: just read 12 bytes
^C

It seems therefore that Linux 4.5 underestimates its amount of entropy --- assuming I'm the only consumer. This assumption is probably false, but perhaps I am not too far from the truth. My verification finds about 5 bytes over the estimate of the kernel.

$\endgroup$
2
  • 2
    $\begingroup$ lwn.net/Articles/808575 $\endgroup$
    – kelalaka
    Oct 10 '20 at 18:13
  • $\begingroup$ The random driver source code is actually pretty easy to read. $\endgroup$
    – forest
    Oct 13 '20 at 0:08
-2
$\begingroup$

You can't, and you're not the only consumer. The operating system rips you off. It uses true randomness to prevent attacks by shoving code into random places. And randomly sequencing it's network traffic. But here's the thing...

“We have to remember that what we observe is not nature in itself but nature exposed to our method of questioning.”

-Werner Heisenberg

and that's compounded with the concept of the observer effect.

Essentially what the kernel does is quantize various external events via a made up second order differential algorithm. There's a write up in Documentation and Analysis of the Linux Random Number Generator but essentially it comes down to temporal quantization of hardware events as :-

pic

And so,

It seems therefore that Linux 4.5 underestimates its amount of entropy

Yes. That's the conclusion of all of the academic works I've seen on /dev/random. It's essentially the least signification digit of system time when something happens. But, the problem is that it shouldn't take 160 PDF pages to convince us of randomness. My concept of Open Entropy dictates that it should be screaming right up in your face without funky science.

With delicacy, what's your real question?


  1. Nothing in this post relates to Micro$oft operating systems.

  2. If this is important to you, build your own entropy source. It's not difficult considering the 2nd law of thermodynamics. Get a diode.

  3. There's a dangerous and hugely misunderstood meme out there that suggests /dev/random = /dev/urandom without appreciating the role of time. $(\epsilon, \tau)$ and the left over hash lemma is everything.

$\endgroup$
3
  • $\begingroup$ Your #3 is particularly confusing. What does the "role of time" have to do with it? All the non-blocking random driver is is a CSPRNG that doesn't block (unlike the blocking pool which does). Anyway modern Linux kernels have done away with the blocking pool. $\endgroup$
    – forest
    Jan 2 at 0:21
  • $\begingroup$ @forest 1st: The definition of output ‘rate’ $(\tau^{-1})$ necessitates the consideration of time. Remember that only the old \dev\random can be used to construct a proper one time pad because it counts entropy. 2nd: Yes, now most can’t. That’s another successful project for the NSA et al., and a great curtailment of our privacy. Final: That’s why we should build our own entropy sources, or buy raw ones. It’s really really unfair/undemocratic that I have access to true randomness (aka privacy) and you don’t. Sorry. But there are sites ‘out there’ that can fix that... $\endgroup$
    – Paul Uszak
    Jan 3 at 15:33
  • $\begingroup$ Randomness and privacy have nothing to do with each other. As for the /dev/random change, that was a good thing. I supported it and even helped (to a limited extent) to get it through. It's completely secure. $\endgroup$
    – forest
    Jan 3 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.