2
$\begingroup$

I'd like a sample of true random data from a source that has a known entropy. It's not easy to even produce true random data in sufficient quantity --- much less know the entropy of the source. For instance, my only chance at grabbing true random data is waiting for /dev/random.

I'm spinning my hard drive and using the system as hard as I can to feed the kernel with enough entropy. Meanwhile I'm collecting data up to 1,000,000 so as to satisfy NIST SP 800-90B because I'd like to estimate the entropy of /dev/random using the state of the art in entropy estimation. (I'm aware of various problems with NIST SP 800-90B, but I have not found anything better out there that has been received the due scrutiny from the scientific community.)

How am I spinning my system?

$ while true; do sudo find /; done

How am I collecting the data?

$ cat /dev/random >> random.bit

Why am I not collecting it quickly from /dev/urandom? Because that does not make sense. I'd like to estimate the entropy. I won't get more entropy from using a PRNG to process true random data. As far as I can tell, using a PRNG might just make it harder for the estimators. (Any thoughts on that?)

Do you know of any sample of random data out there that has a respectful entropy estimation that I can use to see how well NIST SP 800-90B does on it? Is there any work done that states the entropy of Linux's /dev/random?

$\endgroup$
2
  • 3
    $\begingroup$ Actually, the 800-90B tests don't actually measure entropy; instead, they take a guess on how much entropy a sample would have; any source that is computationally indistinguishable from random would be treated the same by them. $\endgroup$
    – poncho
    Sep 28 '20 at 20:05
  • 2
    $\begingroup$ /dev/random and /dev/urandom are the same source. The only difference is that /dev/random needlessly blocks sometimes. Both are using the exact same CSPRNG. $\endgroup$ Sep 28 '20 at 20:49
3
$\begingroup$

The question really asks for a sample of data from a source with a known entropy rate.


I suggest starting with the simplest: sources with zero entropy rate. Examples from which the first megabytes can be readily obtained:

  • a source producing only bytes at zero.
  • a source cycling over the 256 bytes incrementally.
  • a source consisting of the SHA-256 hashes of bytestrings of increasing length, in lexicographic order.
  • /dev/random or /dev/urandom modified to replace the input of their built-in PRNG with zeroes.
  • a source producing the bytes of $\pi$ (e.g. using Bellard's method).

NIST SP 800-90B tests won't help distinguish the last three from a source with some entropy. That illustrates these (or similar) tests can't reliably detect even a total lack of entropy, unless some hypothesis is made on the nature of the source.


We can use a lightly conditioned source. It's easy to make one from a microphone in front of something emitting noise (a fan will do), sampled by an ADC (sound input of a PC will do), and the bytes from some number of samples fed thru some light conditioning (like: group $n$ 16-bit samples and output the sum modulo 256 of the $2n$ bytes). That's a better fit for what NIST SP 800-90 is designed to work on. It'll be interesting to see how the gain of the microphone preamplifier, the position of the microphone, and parameter $n$, all influence the results. This source doesn't have a known entropy rate, though.


We can manufacture a source with biased but (presumably) independent bytes and a known biased distribution leading to (at most) a certainly known entropy. One way is to take /dev/urandom (or any source which output can't be discerned from that of a perfect true random source), group bytes by two to form an integer in $[0\ldots2^{16})$, and output the high-order byte of that unless the integer is less than $k$, for some parameter $k\in[0\ldots2^8]$. This leads to a source with byte zero having probability $(2^8-k)/(2^{16}-k)$, and the others $2^8/(2^{16}-k)$. Entropy in bit/byte is easy to compute as a function of $k$, and goes (for $k$ up to $100$): Entropy in bit/byte

$\endgroup$
3
  • $\begingroup$ The graph needs axis names or explicitly written as $k$ values for $x$-axis. $\endgroup$
    – kelalaka
    Sep 30 '20 at 18:37
  • $\begingroup$ @kelalaka: I hoped the X axis was clear from "for $k$ up to 100", and the Y axis clear from "Entropy in bit/byte is..". Will try to annotate better. $\endgroup$
    – fgrieu
    Sep 30 '20 at 18:39
  • $\begingroup$ A little formula for the graph will help, too. clean all whenever you want. $\endgroup$
    – kelalaka
    Sep 30 '20 at 18:41
1
$\begingroup$

In practice you won't learn anything from this exercise. The entropy guessing methods in NIST SP 800-90B, even if they're state of the art, are very easy to fool. It's probably safe to assume that the true entropy of the source isn't substantially higher than what these tests tell you it is, but it could easily be much lower. Even the output of a non-cryptographic PRNG like the Mersenne twister, seeded with 0 or with the current POSIX time, will probably pass all of the tests.

If you had a Kolmogorov complexity oracle, it would be interesting to feed the output of /dev/random or the RAND million digits to it to see what other analyses might have missed. But the difference between asking a Kolmogorov oracle and a real-world entropy guessing algorithm is like the difference between asking God and your six year old kid.

$\endgroup$
2
  • $\begingroup$ Can you show a sample that fools NIST SP 800-90B? NIST SP 800-90B has been reported to give ``massive underestimates''. It has not been reported any overestimation --- as far as I'm aware. Can you cite a reference to back up your claim? I'm not aware of any pass/not-pass report by NIST SP 800-90B. It estimates entropy so you can compare it against your theoretical estimate. It will not say pass or does not pass. Can you clarify? $\endgroup$ Sep 29 '20 at 14:41
  • $\begingroup$ @user12406990 As well as Kelsey's own self critique, there's Hart et al and this analysis by running ea_non_iid over Shakespeare's works. In that latter case, look at the 52 ratio. I can't understand nor explain it, and I think that the elusive definition of $H_{\infty}$ in the general case (non IID) is at the heart of 90B's problem. $\endgroup$
    – Paul Uszak
    Dec 20 '20 at 13:51
0
$\begingroup$

I'd like a sample of true random data from a source that has a known entropy.

You don't need to. You simply leverage computational indistinguishability.

Just use any decent random number generator (not necessarily cryptographic) and generate appropriate files for testing. The entropy tests cannot distinguish the difference, so they just measure the files' entropy as if it were truly random. The beauty is that since you're generating the files, you know exactly how much entropy goes into them. Stuff as simple as:-

import random
with open('/tmp/entropy.bin', 'wb') as f:
    for i in range(2_000_000):
        value = round(random.gauss(127, 5))
        f.write(value.to_bytes(1, byteorder='big'))

And you check that against the theoretical $H_{\infty}$ for $Pr(126.5 \le x_i \le 127.5)$ within an $\mathcal{N}(127, 5^2)$ distribution. Hint: It's $-\log_2(0.0797)$ or 3.65 bits/byte. Loads more examples here and here and make up your own too.

But overall this is a difficult one to answer succinctly. 90B features two pathways:-

1. IID Track

This one's uncontroversial. It's common permutation testing to verify that the samples are IID with $p = 0.001$ confidence. $H_{\infty} = -\log_2(p_{max})$ arises directly from it.

2. Non-IID Track

Controversial indeed, and pretty much still an open question as to what is $H_{\infty}$ for a correlated sequence. You clearly realise this: "I'm aware of various problems with NIST SP 800-90B, but I have not found anything better out there that has been received the due scrutiny from the scientific community" and you're correct. This is nothing else really.

As a result, and with even John Kelsey (lead author of the tests) saying that they're not very good, no one uses the non-IID track. You'll be hard pressed to find a paper that ran ea_non_iid on their entropy source. So my advice to you is not to either. Decorrelate your sampling regime and just calculate $-\log_2(p_{max})$ from the histogram. The mathematical reason for this advice is that we can validate non correlated data with a much higher confidence than we can $\frac{H_{Estimate}}{H_{Actual}}$, especially since many of the non-iid tests are compression algorithm derivates.

$\endgroup$

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.