A counter passes the health tests

Take a counter. It counts from 0 to 255 and starts again. It has no entropy at all, because anyone who has seen one byte knows every byte after it. Give 8,192 of its samples to the two approved continuous health tests of NIST SP 800-90B, with a claim of 8 bits a sample. Both pass. The most common value estimate then says that the counter holds 7.46 bits a sample.

The second row is a source that falls into a short cycle. The standard names that failure itself, as an example of what a maker has to write tests for (section 4.3, requirement 8). It passes the approved tests as well. You can reproduce the first row on the entropy page. Set the entropy the maker claims to 8 bits, choose the fault called Counts, and start it at sample 1.

What the tests are for

The standard is plain about their limits. Continuous tests run on every sample, so they have to be cheap and almost never raise a false alarm. The standard says that this limits what they can detect, and that they are usually designed so that only gross failures are likely to be detected (section 4.2).

The repetition count test catches a source that gets stuck on one value. The adaptive proportion test catches a value that starts to occur much more often than the claim allows. Both count how often values appear, and neither looks at the order in which they arrive. The values of a counter are spread as evenly as values can be. In a window of 512 samples the first value returns once more, so the busiest window has a count of 2, against a cutoff of 13.

A pass means two things. The source is not stuck, and no value has taken over. It does not mean that the samples are unpredictable.

What the estimate adds

The most common value estimate (section 6.3.1) has the same blind spot. It takes the share of the most common value, adds an upper bound of 2.576 standard deviations, and takes minus the base 2 logarithm of the result. In 8,192 samples of a counter every value appears 32 times. The share is 1/256, the bound lifts it to 0.0057, and the estimate is 7.46 bits. The shortfall from 8 bits is the margin of the bound. The estimator saw nothing wrong. With the million samples that the standard asks for the margin is narrower, and the estimate for the counter is 7.94 bits.

The standard does not stop at one estimator. For a source that is not independent and identically distributed it requires up to ten, three of which apply only to binary data, and takes the smallest of their results as the assessment (section 6.2). It gives the reason itself. Testing sequences with dependent values may overestimate entropy, and a diverse battery makes a large overestimate less likely.

What the plate leaves out

The plate on the entropy page runs the two approved continuous tests and the most common value estimate. It does not run the other estimators, the restart tests or the choice between the independent and dependent tracks, and the page says so in its list of what the plate covers. The estimate it shows is one estimator and nothing more, and it is not an assessment of a source.

What to run as well

Run the whole battery of section 6.2 on a million raw samples of the real source, and take the smallest result. Then do what section 4.3 asks. Write down the failures that the source is known or suspected to have, and a continuous test for each. A source that can fall into a short cycle needs a test that sees cycles.

The program below reproduces the table with the standard library alone. It works out the cutoff of the adaptive proportion test from the standard’s formula, 1 + CRITBINOM(W, 2^-H, 1 - 2^-20), in whole numbers of any size. That agrees with the five entries of Table 2 that are claims of whole bits, which are the ones whole numbers can express. The engine reproduces all ten entries, and statement EN-03 on the verification page says so.

from math import ceil, comb, log2, sqrt


def rct_cutoff(claim, alpha=20):
    return 1 + ceil(alpha / claim)


def apt_cutoff(claim, window, alpha=20):
    # 1 + CRITBINOM(window, 2^-claim, 1 - 2^-alpha), worked out in whole numbers.
    other = 2**claim - 1            # weight of "a different value"
    total = 2 ** (claim * window)   # the common denominator of every term
    tail = 0                        # the numerator of P(X > k)
    for k in range(window, -1, -1):
        if tail * 2**alpha > total:
            return k + 2
        tail += comb(window, k) * other ** (window - k)
    return 2


def longest_run(samples):
    run = longest = 1
    for a, b in zip(samples, samples[1:]):
        run = run + 1 if a == b else 1
        longest = max(longest, run)
    return longest


def busiest_window(samples, window):
    starts = range(0, len(samples) - window + 1, window)
    return max(samples[i : i + window].count(samples[i]) for i in starts)


def most_common_value(samples):
    n = len(samples)
    p = max(samples.count(v) for v in set(samples)) / n
    return -log2(min(1, p + 2.576 * sqrt(p * (1 - p) / (n - 1))))


N = 8192
streams = [
    ("counter", 8, 512, [i % 256 for i in range(N)]),
    ("alternating", 1, 1024, [i % 2 for i in range(N)]),
]
for name, claim, window, s in streams:
    print(f"{name}: longest run {longest_run(s)} (cutoff {rct_cutoff(claim)}),",
          f"busiest window {busiest_window(s, window)} (cutoff {apt_cutoff(claim, window)}),",
          f"estimate {most_common_value(s):.2f} bits")

It prints this.

counter: longest run 1 (cutoff 4), busiest window 2 (cutoff 13), estimate 7.46 bits
alternating: longest run 1 (cutoff 21), busiest window 512 (cutoff 589), estimate 0.96 bits

The window is 512 for the counter, which has 256 different values, and 1,024 for a source with two values, as the standard sets it.

What we have not checked

• We ran one counter and one alternating stream. Other sources pass the approved tests and are far from random, and we have not catalogued them.
• We did not run the other estimators on either stream, so we do not know what the whole battery would say about them.
• The numbers are for 8,192 samples, the size of the stream on the entropy page. At a million samples the counter still passes both tests, and its estimate is 7.94 bits.
• We read the January 2018 publication. Later revisions were not checked.