Why does the NIST Runs Test include a Frequency Test?

Question

In the NIST suite of RNG tests (https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final), one of the tests is the Runs Test, which tests counts of runs of 1's and 0's. According to the documentation, you need to first carry out a Frequency Test, which essentially confirms if the number of 1's within the sequence is within $\pm$4 standard deviations (where $\sigma=1/{\sqrt{2n}}$) for $n$ total bits.

There is already a Frequency Monobit Test elsewhere in the test suite, and the test statistic is very similar in each. One calculates $count_{1}/n - 0.5$, and the other calculates $|{count_{1}-count_{0}}|/\sqrt{n}$. Why do we need this second Frequency Test as part of the Runs Test? Why not just let the Runs Test test the Runs, and the Frequency Monobit Test test the frequencies of each bit?

Answer 1

The Monobit test checks the frequency of 0 and 1 over the whole sequence tested. The Frequency test does that on $M$ sub-blocks, where $M$ is an additional parameter. For example, with $M>1$ (and way up), a sequence of $n=8000000$ bits consisting of $4002000$ times 0 followed by $3998000$ times 1, which passes the Monobit test, will fail the Frequency test.

---

Such detailed examination of the justification of each test should not obscure the big picture: only failing SP-822 (or any statistical test of randomness) matters. SP-822 is good at what it does, but passing a statistical test does not prove anything useful from a cryptographic standpoint. When a generator fails SP-822, the generator is flawed. Don't fall to a converse error!

It's impossible to assess positively the quality of a conditioned¹ random source from its output alone (as SP-822 proceeds). That's a trivial consequence of the existence of practically secure PRNGs. And SP-822 is not applicable in practice to unconditioned random sources (for one thing, they tend to fail the Monobit test. Those that do not for long sequences have some internal de-biasing, which amounts to conditioning).

Remember, Dual_EC_DRBG was developed with the purpose of having a backdoor in crypto gear, and phased out when that got widely known. Meanwhile, Dual_EC_DRBG had become a standard, and people tend to trust standards. A RNG using Dual_EC_DRBG passes SP-822 with flying colors. SP-822 is a de-facto standard on randomness testing. That test and Dual_EC_DRBG are developed by the same organization. I do not make a certain conclusion on intention. Draw your own.

---

Actual security evaluation of cryptographic random generators should assess:

• The physical soundness of the unconditioned random source.
• The statistical soundness of an online test that monitors that source on the field, and safely shuts the whole thing off on failure. Principles of the simplest tests of SP-822 apply.
• The cryptographic soundness of the conditioning algorithm.
• The conformity of the implementation to the above design.

---

¹ The traditional structure of a RNG comprises a source of randomness followed by conditioning that produce the final output, plus supervision to detect failure. Some classic conditioning techniques include Von Neumann Extractor; LFSR in scrambler mode followed by decimation; and various CSPRNGs.