2
$\begingroup$

NIST SP 800-90B offers various tests for estimating entropy. They also offer an implementation of these tests. With their program called ea_iid, estimating entropy is very easy.

$ ea_iid random.dat
Calculating baseline statistics...
H_original: 7.884314
H_bitstring: 0.998545
min(H_original, 8 X H_bitstring): 7.884314

** Passed chi square tests

** Passed length of longest repeated substring test

Beginning initial tests...
Beginning permutation tests... these may take some time
** Passed IID permutation tests

So the min-entropy estimation for the source that produced random.dat is 7.88 bits of information per byte.

However, this page calls it USELESS. I'm unable to reproduce the claims made this page --- none of my NIST SP 800-90B programs show even similar output as those displayed by this page. The output above is an example. Am I running a totally different version of the programs?

$\endgroup$
4
$\begingroup$

The page says right near the top:

The NIST SP 800-90B tests+ only apply (and only when they’re behaving) to uniformly distributed data sets. The kind that you hardly ever get sampling real world, physical entropy sources.

Uniformly distributed, in the context of bit sequences, means behavior like an idealized coin toss:

  1. Each bit has an equal probability of coming up as 0 or 1;
  2. The value of any random bit is independent of that of any other.

This is indeed the flavor of randomness that most cryptographic software expects to be given. The entropy of such a uniform random bit string is equal to its length—i.e., it gives you the maximum entropy possible for its size.

But physical noise sources tend to be normally distributed, or as more popularly known, "bell curves" where there is a mean value that the likeliest, 68% fall within one standard deviation of the mean, and so on. The page you link is in a site about a physical device to produce random noise that evidently makes no claim that its output is uniformly distributed. So indeed, tests for uniform distribution would not be proper for evaluating the entropy of its output.

Note that in practice, to use such a non-uniform device in a cryptographic typical application, some sort of conditioning or randomness extraction would be performed to synthesize its raw output into processed output indistinguishable from uniform randomness. This might well happen implicitly if you, for example, use its output to feed an operating system random generator entropy pool.


So I'd say that this page's labeling of the SP-800-90B tests as "useless" is hyperbolic and unhelpful. It really just means that they're not designed to evaluate non-uniform random noise sources, but says it in a way that is likely to mislead people to think that the tests are somehow flawed.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Actually, these tests are specific to "IID" (Independent and Identically Distributed) sources; that is, those that meet your criteria 2 (generalized if it's not a binary source), but not necessarily criteria 1. Why it's not common is that physical noise sources generally have some correlation between generated symbols; IID specifically assumes there isn't one $\endgroup$ – poncho Sep 12 at 12:02
  • $\begingroup$ NIST SP-800-90B is also designed for non-IID sources. They have specific tests for non-IID sources. The page that calls it USELESS is precisely using tests specific for non-IID sources. It's the contrary of what @poncho is saying. (If I'm not mistaken.) $\endgroup$ – user12406990 Sep 12 at 14:09
  • $\begingroup$ @LuisCasillas, are you saying the page that calls it USELESS is correct --- though it should be worded differently? If the source is uniform, does NIST SP-800-90B estimate entropy reasonably well? $\endgroup$ – user12406990 Sep 12 at 14:15
  • 1
    $\begingroup$ @user12406990: I was specifically addressing the ea_iid tests discussed in the question; I am quite aware that 800-90B includes non-iid tests... $\endgroup$ – poncho Sep 12 at 15:03
  • $\begingroup$ @LuisCasillas, would you be so kind to provide a reference for the claim that most physical noise sources tend to be normally distributed? That'd be very useful. Thank you! $\endgroup$ – user12406990 Sep 14 at 18:33
2
$\begingroup$

As the author of that page I feel that some clarification is necessary:-

Am I running a totally different version of the programs?

Yes. You're running the IID test. You need to run ea_non_iid. What you've run assumes that the data sample is IID within a p=0.01 certainty. It then calculates the min. entropy of the dataset using the maximum probability ($H_\infty$). That's easy.

ea_non_iid attempts to measure $H_\infty$ of correlated data. That's hard. The reason 90B is pretty useless (and never used) is that code assumes uniformly distributed data. Well to be honest, no one really knows what the authors were thinking. [Insert appropriate conspiracy theory, but I draw your attention to Federal Information Security Modernization Act (FISMA) of 2014, 44 U.S.C. § 3551 et seq., which is referenced on page 3 of 90B].

Other than a few laboratory binary entropy sources, most generate some form of non uniform distribution. You can get really weird ones depending on how the source is sampled and packed into bytes. That site has examples, and this is another one from a current project's source:-

histogram

The site also says to not trust anything on that site. Do your own research and have a look at:-

John Kelsey, Kerry A. McKay and Meltem Sönmez Turan, Predictive Models for Min-Entropy Estimation, and Joseph D. Hart, Yuta Terashima, Atsushi Uchida, Gerald B. Baumgartner, Thomas E. Murphy and Rajarshi Roy, Recommendations and illustrations for the evaluation of photonic random number generators.

This is an extract:-

graph

You can see that in some cases $H_\infty$ is underestimated sixfold. Their various predictors are not very good. From experience and research I trust the LZ78Y compression predictor the most, but still. This is consistent with my own testing as shown.

John Kelsey is one of the 90B authors and so he criticises himself!

| improve this answer | |
$\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.