3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I think that the question is a little more targetted at explaining "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?". I thought hard on this last night and decided to pass as I can't for the life of me answer the quote above. I suspect (having poked around some NIST conferences) that they can't either. This standard seems to have the same academic statistics hallmarks of the even worse 800-90B tests. Even ent will easily catch your 4002000/3998000 example. $\endgroup$
    – Paul Uszak
    May 27 at 11:07
  • $\begingroup$ Also in 3.1 Frequency (Monobits) Test, we have "All subsequent tests are conditioned on having passed this first basic test. " Why? Is it to save compute cycles and not tire out the machine? I don't get it. $\endgroup$
    – Paul Uszak
    May 27 at 11:24
  • 1
    $\begingroup$ @Paul Uszak: when testing a RNG, the net effect of that provision is to make it necessary to have some level of conditioning in the RNG, thus rendering the rest useless (from the standpoint of asserting the RNG quality) when it passes. We can only imagine why that is. $\endgroup$
    – fgrieu
    May 27 at 11:34
  • 1
    $\begingroup$ Err, everything below the first horizontal rule is covered precisely in the last para of the abstract: "The design and cryptanalysis of generators is outside the scope of this paper." That's not the question. Final comment. $\endgroup$
    – Paul Uszak
    May 27 at 21:43
  • 1
    $\begingroup$ The Runs Test will already catch the problems in that example, because there is an obvious pattern / correlation between the bits. The Frequency Tests check that the bits are from a uniform distribution, but don't look for correlations between the bits. The other tests, including the Runs Test, do that. This is why they say to do a Monobits Test over the whole sample, and only if that passes, do the other tests. But also why it seems pointless to do the Frequency Test as part of the Runs Test. $\endgroup$
    – Chris VP
    May 28 at 4:54

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.