10
$\begingroup$

I know there are different statistical tests out there (NIST, Dieharder, etc), which all do different ways of analyzing entropy.

What I'm having a hard time finding is any particular literature which describes how to go from those tests to actual bits of entropy in the byte stream.

How do you go from p value of a byte stream (say a 100 MB long) to bits of entropy?

Updated:

As mentioned below, you can't estimate entropy of the output (not possible), but only by understanding the physics of the underlying process that generates the entropy.

$\endgroup$
  • $\begingroup$ The common notion of entropy is the notion of Shannon entropy. The Shannon entropy H(x) of a value x that occurs with probability Pr[x] is H(x) = -log_2(Pr[x]). Related questions: crypto.stackexchange.com/q/378/6961 and crypto.stackexchange.com/q/700/6961 $\endgroup$ – e-sushi Sep 18 '13 at 3:32
  • 2
    $\begingroup$ There are two issues with Shannon entropy: 1) It's only defined for a probability distribution, not for an individual string 2) Shannon entropy and average key-strength aren't exactly the same thing if the probability distribution isn't uniform. $\endgroup$ – CodesInChaos Sep 18 '13 at 11:32
  • $\begingroup$ I've made some progress here. When I have a full answer, I will post it (especially given all the great help I've got it). I'm currently investigating Ping Li's work here: stanford.edu/group/mmds/slides2010/Li.pdf Ideally though I'd do something based off of NIST's work here: csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html $\endgroup$ – Blaze Sep 23 '13 at 22:16
  • $\begingroup$ Can you tell us more? Why do you want to measure the amount of entropy? What do you know about the source of the byte stream? The answer is going to depend heavily on the answers to these questions and on other details, so if you can give us more details, we might be more likely to be able to give you a good answer. This is not a simple subject with a simple one-line answer... $\endgroup$ – D.W. Oct 1 '13 at 22:49
  • $\begingroup$ No, I can't. I really want to simply estimate entropy. $\endgroup$ – Blaze Oct 3 '13 at 17:25
19
$\begingroup$

Entropy is a function of the distribution. That is, the process used to generate a byte stream is what has entropy, not the byte stream itself. If I give you the bits 1011, that could have anywhere from 0 to 4 bits of entropy; you have no way of knowing that value.

Here is the definition of Shannon entropy. Let $X$ be a random variable that takes on the values $x_1,x_2,x_3,\dots,x_n$. Then the Shannon entropy is defined as

$$H(X) = -\sum_{i=1}^{n} \operatorname{Pr}[x_i] \cdot \log_2\left(\operatorname{Pr}[x_i]\right)$$

where $\operatorname{Pr}[\cdot]$ represents probability. Note that the definition is a function of a random variable (i.e., a distribution), not a particular value!

So what is the entropy in a single flip of a coin? Let $F$ be a random variable representing such. There are two events, heads and tails, each with probability $0.5$. So, the Shannon entropy of $F$ is:

$$H(F) = -(0.5\cdot\log_2 0.5 + 0.5\cdot\log_2 0.5) = -(-0.5 + -0.5) = 1.$$

Thus, $F$ has exactly one bit of entropy, what we expected.

So, to find how much entropy is present in a byte stream, you need to know how the byte stream is generated and the entropy of any inputs (in the case of PRNGs). Recall that a deterministic algorithm cannot add entropy to an input, only take it away, so the entropy of all inputs to a deterministic algorithm is the maximum entropy possible in the output.

If you're using a hardware RNG, then you need to know the probabilities associated with the data it gives you, else you cannot formally find the Shannon entropy (though you could give it a lower bound if you know the probabilities of some, but not all, events).

But note that in any case, you are dependent on the knowledge of the distribution associated with the byte stream. You can do statistical tests, like you mention, to verify that the output "looks random" (from a certain perspective). But you'll never be able to say any more than "it looks pretty uniformly distributed to me!". You'll never be able to look at a bitstream without knowing the distribution and say "there are X bits of entropy here."

$\endgroup$
  • 2
    $\begingroup$ Hmm, that doesn't seem to jive with what I've been asked unfortunately. I think if you have enough data and enough tests, you should be able to come up with a reasonable estimate of entropy. $\endgroup$ – Blaze Sep 18 '13 at 0:33
  • 1
    $\begingroup$ Yes, that's absolutely true (and a great point), however the sources under discussion have not been mathematically obfuscated and the assumption is that they are bare before analysis. One example of entropy measurement of course is compression. If we were to able to compress something 10 times more than something else, I think we can make some reasonable observations about how much more entropy that has. We can do heuristic analysis to come up an estimate of the entropy bits, but I think its nice (and generally expected) to have the results of experimental data to back that up with. $\endgroup$ – Blaze Sep 18 '13 at 1:42
  • 2
    $\begingroup$ I think what people are looking for is heuristic analysis + statistical analysis. For example, if I flip a coin, I can theoretically say 1 bit of entropy. Now, let's flip that coin 10 thousand times and do a statistical analysis to see if that measures up. If I get all heads, then so much for my heuristical analysis... I'm pretty sure this is the motivation. The part I'm missing is how to go from statistical analysis to 'bits per byte' of entropy. Note this request comes from experts. $\endgroup$ – Blaze Sep 18 '13 at 2:53
  • 4
    $\begingroup$ @Blaze: My whole point is that you can't go from a statistical analysis to a measurement of entropy. If you happen to know how the bitstream is generated, then you can calculate the entropy directly (via the above formula) --- but if you don't know how it's calculated, then it simply can't be done. $\endgroup$ – Reid Sep 18 '13 at 3:45
  • 3
    $\begingroup$ I would think we could pragmatically estimate entropy via a combination of statistics and good analysis. Empirically measure a statistical distribution on the lowest level of the entropy source that you can. Calculate $H$ where $Pr[x_i]$ is calculated from that distribution. How good an estimate of entropy this produces will rely on how good of a choice was made for "lowest level". Eg, if you chose the output of a PRG seeded by 0 you will have a false high entropy due to a poor decision. But if you choose a level the attacker won't have deeper insight to, the estimate should be good. $\endgroup$ – B-Con Sep 18 '13 at 4:58
1
$\begingroup$

There are some tests out there: Draft Special Publication 800-90B - National Institute of Standards

In particular the min-entropy, partial collections, Markov (useful for non-IID sources), collisions, and compression tests.

The issue with the Markov test is the constraint on bit size of the sample.

Updated:

These tests only measure output. They don't measure the underlying entropy that was used to generate the data. You can take completely non random data and make it look perfectly random according to these tests (or any tests).

$\endgroup$
  • $\begingroup$ It's a fair point. I'll change the accepted answer. The standards were (are?) messed up. $\endgroup$ – Blaze Jun 8 '15 at 17:22
  • 4
    $\begingroup$ No, the standards are not messed up. Instead, they take a problem which (as Neil mentioned) is insolvable as defined, and try to come up with a good as an answer as they can practically come up with. What the tools do is come up with a ceiling on the entropy (we're pretty sure that there's no more than N bits of entropy there); that leaves open the question of a lower bound, but we don't know how to solve that problem. Anyone using the tool should realize its limitations. $\endgroup$ – poncho Jun 8 '15 at 18:53
-3
$\begingroup$

I know there are different statistical tests out there (NIST, Dieharder, etc), which all do different ways of analyzing entropy.

Those statistical tests are intended to verify that a RNG is producing independent and uniformly distributed random numbers. That's all. Whilst some suite tests may produce an entropy estimate, that is not their primary purpose. (Eg. First line of the basic ent test.) They are for producing a estimate of likelihood (p value) that the test sequence is of good quality. You can only tell that the sequence is bad if there's a run of p = 0.00000 (SP 800-22) or a heap of FAILs (Dieharder).

There is NIST Special Publication 800-90B, Recommendation for the Entropy Sources Used for Random Bit Generation. It seemingly attempts to measure entropy but has massive issues if the data sample is not uniformly distributed. So inapplicable to natural data. And it also has severe programming errors resulting in estimates like 21 bits /byte.

What I'm having a hard time finding is any particular literature which describes how to go from those tests to actual bits of entropy in the byte stream.

I'm not aware of any either. The lack of discourse suggests that this is not an active field. The closest I've seen is the discussion Estimated entropy per bit given P-value of a statistical test, and number of bits tested? on this site. I think that the accepted answer is unproven for the reasons in my answer.

Revisiting this idea, I'm now fairly convinced that it's impossible. One can't compare the asymptotic nature of Chi, Gauss and t-distributions that produce the p values, to the 0 - 100% linear degrees of entropy within a sequence. And some tests such as car parking in Diehard(er) are not even defined algebraically, but rather by past computer simulation. The tests behave chaotically at the edges.

As mentioned below, you can't estimate entropy of the output (not possible), but only by understanding the physics of the underlying process that generates the entropy.

This is false. It's not just possible, it's done all the time. The very nature of all statistical science based on population sampling, ergodic data sources, NIST's 800-90B and most other branches of science unequivocally prove that you can. You simply need a sufficiently large output sample for one's intended test suite as p(randomness) ~ f(sample size).

As for understanding the physics, non trivial RNGs are 50/50. You can produce a reasonable entropy model of a photon interference based TRNG. You have very little chance accurately modelling a simple Zener diode, other than to say it's kinda log normal with correlation. Or the balls in the National Lottery's tumbling machine cylinder thingie.

To date, I've only found the "top 1" best ways of practically estimating natural entropy. Compression. I now use cmix, one of the strongest compressors in the world. Just compress the file, divide by two for safety and hey presto, your entropy estimate. Not perfect, but I'm unaware of any other direct technique that works on all natural sample distributions.

$\endgroup$
  • $\begingroup$ Please note that cmix is not ideal for entropy testing. In fact, despite being a good compressor, the way it works ensures that it will actually be really bad for the kind of data that comes from a failing noise source. $\endgroup$ – forest Jan 7 at 1:32
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Ella Rose Jan 7 at 16:18

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