Where can I find a sample of data with a known entropy to see how well NIST SP 800-90B does on it?

Question

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?

Answer 1

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$):

Answer 2

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.

Answer 3

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.