2
$\begingroup$

I have a binary sequence of length $2^{20}$. I am using the NIST statistical test, assess.

  1. What should be taken for ./assess and How many bitstreams? in this test?

  2. In the final Analysis report, what p-values should be there to pass this test?

$\endgroup$
  • $\begingroup$ I'm not a fan of manually configured suites like the NIST one. It leads to self determination of what should be called random. As a sanity check that you've configured it correctly, simply run the ent test over your MB. If ent passes, you can expect reasonable results from NIST, although it might still fail somewhat. It ent fails, NIST will fail biggly. $\endgroup$ – Paul Uszak Feb 21 at 20:52
2
$\begingroup$

In general, if you draw a sample at random from a distribution $D$, and you apply a statistical test for the null hypothesis $D$ yielding a $p$-value, and you print the $p$-value, rounded to, say, a multiple of 0.05, it is as if you rolled a fair d20 to pick among the possible results. (For finer granularity, roll a die with more sides.) That's all that a $p$-value is.

One might hope that the test was designed so that if you sampled from a different distribution $D'$ instead of $D$, an alternative hypothesis, it is as if you rolled a d20 with a weight on one of the faces so that it comes up <0.05 most of the time. Then if you raise an alarm whenever $p < 0.05$, there's a 5% false alarm rate in your test of the null hypothesis, and a high true alarm rate when there's a problem and you're actually sampling from $D'$.

In the statistics literature, the false alarm rate for a test like this is confusingly called the ‘significance level’; the true alarm rate is called the ‘statistical power’. The false alarm rate depends only on the null hypothesis $D$, not on $D'$, while the statistical power depends only on the alternative hypothesis $D'$. A poorly designed test might behave identically on $D$ and $D'$, in which case an alarm means nothing at all about $D'$ even if your ‘significance level’ is 0.05. (An exceptionally poorly designed test might even have a lower alarm rate under $D'$.)

Typical ‘randomness tests’ like dieharder and the NIST SP 800-22 suite* are collections of statistical tests for a null hypothesis of the uniform random distribution $D$ on bit strings. They have high statistical power to detect very simple-minded alternative hypotheses like strings of IID bits with 1/4 chance of 0 and 3/4 chance of 1. They do not have high statistical power to detect alternative hypotheses like strings of $\operatorname{AES256}_k(0) \mathbin\| \operatorname{AES256}_k(1) \mathbin\| \cdots$ for uniform random key $k$.

What really matters in cryptography is how you got your sample. There are two options:

  1. You got your sample by measuring a physical process like counting ionizing events in a Geiger–Müller tube. In this case, you should have a specific probabilistic physical model in mind with fancy words like Poisson process: to measure the cryptographic value of this process you need to study the physics and engineering of the process to determine a lower bound on its min-entropy by finding the best way to reliably predict what the output is with the help of teams of trained physicists and engineers.

    The NIST tests cannot help you here: they don't know anything about Geiger–Müller tubes.

  2. You got your sample by computing a difficult-to-invert function on a small random input. In this case, the difficult-to-invert function, like AES-256, should be well-studied by teams of trained cryptographers around the world publishing papers with fancy words like differential cryptanalysis to get confidence that it really is difficult to invert.

    The NIST tests cannot help you here: they don't know anything about cryptanalysis techniques.

So what can the NIST tests do? Not much, really. They might give you hints about particular nonuniformities in the distribution that lead you to ideas about (1) or (2), that's all.

But, if you want cookie-cutter answers to questions…

  1. What should be taken for ./assess and How many bitstreams? in this test?

Pass the number of bits in your stream to ./assess. Specify 1 bit stream.

  1. In the final Analysis report, what p-values should be there to pass this test?

Always use p < 0.05, unless it's a two-tailed test in which case use $p < 0.025$ or $p > 0.975$. Beware of green jelly beans.


* Other tools like ent and the NIST SP 800-90B suite fit parameters to model families and compute or estimate the entropy of the resulting models. Many of the concepts are the same, and likewise these tools are too dumb to know anything about your physical process in (1) or your difficult-to-invert function in (2).

$\endgroup$
-2
$\begingroup$

The document relating to these tests is A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications.

The test assumes (assess) x (bitstreams) < total number of bits in sample file. NIST randomness tests tend to be quite poorly coded, and what they actually mean is:-

  1. assess = the number of bits you'd like to test in one test run. A test run is not the total number of bits in the sample file.
  2. bitstreams = the number of test runs you'd like to perform. You need multiple test runs in order to arrive at a final p value in the finalAnalysisReport.txt report. These ps are taken from $\chi^2$ tests over individual test run ps. I try to aim for at least 10 bitstreams. 20 is better and NIST recommends 55 bitstreams to be truly meaningful (§4.22).

So specific to your case, (assess) x (bitstreams) $ \ngtr 2^{20}$. With 10 bitstreams, you'd need to test batches of no more than 100,000 bits. That's low. The Random Excursion (variant) and Universal tests will not even report back as 100,000 bits is too low for them. These tests do not start producing meaningful p values until you test somewhere in the order of 1 million bits x 10 bitstreams. You need to make more bits!

From the NIST document, the P-values are described as:-

For these tests, each P-value is the probability that a perfect random number generator would have produced a sequence less random than the sequence that was tested, given the kind of nonrandomness assessed by the test. If a P-value for a test is determined to be equal to 1, then the sequence appears to have perfect randomness. A P-value of zero indicates that the sequence appears to be completely non-random. A significance level (α) can be chosen for the tests. If P-value ≥ α, then the null hypothesis is accepted; i.e., the sequence appears to be random. If P-value < α, then the null hypothesis is rejected; i.e., the sequence appears to be non-random. The parameter α denotes the probability of the Type I error. Typically, α is chosen in the range [0.001, 0.01]

And in the document's examples, they choose α = 0.01 which is hard coded into the test suite for determining PROPORTION of pass/fails. Due to the pesky nature of randomness, the P-values should be uniformly distributed over 0 - 1, giving you a histogram like below from the C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 section of finalAnalysisReport.txt:-

histogram

And for further comparison, the following is an extract from a 'perfect' test score on the expansion of $ \sqrt{2} $ . Like $\pi$, we know $ \sqrt{2} $ to be irrational and therefore any expansion to any base naturally creates an infinite and perfectly random sequence. God's random number generator if you will. Such numbers are commonly used as yardsticks in validating the randomness tests themselves, and inevitably you can see it passing the NIST test below:-

ps

So you see that there is a degree of black magic and experience necessary to rank a test. Typically though, when a sequence is not random, you tend to get a load of P = 0.00000 or P =1.00000 so it's more clear cut.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Ella Rose Feb 24 at 15:28
  • $\begingroup$ As I have had to say so many times: Please refrain from using comments for chat. Chat rooms exist for a reason. Also, that last comment of yours has no objective substance and is rude/condescending - please do not post such material anywhere on our site. $\endgroup$ – Ella Rose Feb 24 at 15:30
  • $\begingroup$ @EllaRose Not rude, just taken aback by forest's assertion that $\pi$ is missing 10% of it's digits. Quite a claim :-) Not sure how his comment aims to clarify my answer, nor how I can help him further with this one. I'll follow your earlier advice and ignore him. $\endgroup$ – Paul Uszak Feb 24 at 18:33
  • $\begingroup$ @PaulUszak No one is claiming that $\pi$ is missing 10% of its digits. $\endgroup$ – forest Feb 25 at 1:03

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.