Randomness test question from FIPS 140-1 and comparison with 140-2

Question

In FIPS 140-1 there are 4 statistical random number generator tests (The Monobit Test, The Poker Test, The Runs Test and The Long Runs Test. Then FIPS 140-2 came along and supposedly tightened the criteria for these tests. I'll provide a short summary of the changes here:

The Monobit Test

Count the number of ones in the 20,000 bit stream. Denote this quantity by X.

FIPS 140-1: The test is passed if 9,654 < X < 10,346.
FIPS 140-2: The test is passed if 9,725 < X < 10,275.

The poker test

Divide the 20,000 bit stream into 5,000 consecutive 4 bit segments. Count and store the number of occurrences of the 16 possible 4 bit values. Denote f(i)as the number of each 4 bit value i, where 0 ≤ i ≤ 15.

Evaluate the following: X = (16/5000) * (SUM i=0 -> i=15 [f(i)]^2) - 5000

FIPS 140-1: The test is passed if 1.03 < X < 57.4.
FIPS 140-2: The test is passed if 2.16 < X < 46.17.

The Runs Test

A run is defined as a maximal sequence of consecutive bits of either all ones or all zeros, which is part of the 20,000 bit sample stream. The incidences of runs (for both consecutive zeros and consecutive ones) of all lengths ( >= 1 ) in the sample stream should be counted and stored.

1. The test is passed if the number of runs that occur (of lengths 1 through 6) is each within the corresponding interval specified below. This must hold for both the zeros and ones; that is, all 12 counts must lie in the specified interval.

2. The test is passed if the number of runs that occur (of lengths 1 through 6) is each within the corresponding interval specified below. This must hold for both the zeros and ones; that is, all 12 counts must lie in the specified interval. For the purpose of this test, runs of greater than 6 are considered to be of length 6.

FIPS 140-1:

Length of Run   Required Interval
1  2267-2733
2  1079-1421
3  502-748
4  223-402
5  90-223
6+ 90-223

FIPS 140-2:

Length of Run   Required Interval
1  2343–2657
2  1135–1365
3  542-708
4  251-373
5  111-201
6+ 111-201

The long runs test

On the sample of 20,000 bits, the test is passed if there are no long runs.

FIPS 140-1: A long run is defined to be a run of length 34 or more (of either zeros or ones).
FIPS 140-2: A long run is defined to be a run of length 26 or more (of either zeros or ones). 

So in general there are appears to be a narrowing of the criteria to pass the tests. I have a few questions however:

1. In FIPS 140-2 these tests are listed on page 57 but are striked out. I.e. there's a line through all the text. Why is this? In the draft 140-3 the tests do not appear at all..?

2. Does this narrowing down of the test criteria from 140-1 to 140-2 make for a better and stronger RNG if it passes the narrower/stricter criteria? Or does that make it weaker because there's less allowed variance?

3. For The Runs Test, when implementing this and checking if the run is within the required interval e.g. 2343–2657 is this inclusive or exclusive? So if the run was 2343 or 2657 is that a pass or fail?

Answer 1

Q1: Why are these tests stroked out?

These tests are stroked out on pages 57-58 of the current FIPS 140-2 because they are no longer part of the current FIPS 140-2 standard, since Change Notice 2 of 2002 December third, where these pages belong.

My guess for the rationale of removing these tests is that

• It was realized that the very principle of using theses RNG tests and bounds was unsound:
  1. When testing a Cryptographically Secure Pseudo-RNG, a " cryptographic algorithm test using a known answer " (of 4.9.1) is good enough, and a statistical test on the output of a PRNG only a nuisance: the only errors it can report are false positives (else the very definition of the CSPRNG would be broken, when the intend is to test the implementation)!
  2. When testing a True RNG, fact is that it is very hard to make a physical TRNG source that pass these tests (especially those in FIPS 104-2) with decent reliability, without some amount of conditioning between the actual TRNG source and the test point, especially if you account for process and temperature variation (on the field you will often get failures at a rate MUCH higher than predicted for a perfect RNG). This can be fixed e.g. with a LFSR inserted after the TRNG, but then a breakdown of the TRNG source will typically NOT be caught by the prescribed tests!
• It was realized that mandating these test " when the module is powered up " (as required at least for level 4) is impractical in some unattended applications, culminating with Smart Cards (which admittedly do not aim level 4), where:
  1. There can't be an operator to reset a "RNG test failed" condition.
  2. There can be hundreds of devices (millions for Smart Cards), implying an unacceptable number of field failures in combination with 1 and false-positives in the mandated tests.
  3. In addition, a Smart Card can be accidentally powered up several times per second in the normal (or at least practically unavoidable) operation of the device; I've witnessed applications powering off/on any unrecognized contact Smart Card like there's no tomorrow, and that will also occur when a contactless Smart Card is left in front of some perfectly reasonable ISO/IEC 14443 or NFC readers. So it would have been needed some creative redefinition of " powered up " implying intend to use rather than mere establishment of operating power.
  4. We want to be ready fast after power-up.

Thus if you made something per the letter of FIPS 140-1 or FIPS 140-2 before Change Notice 2, it was bound to sometime report failure (and stop functioning save for a sometime impractical human action) even if it worked fine; and this sorry state of things was not a good insurance that it would stop working if the most probable and dangerous cause of field failure occurred (TRNG source stuck, almost stuck, or otherwise non-operative, like synchronized to power-supply ripple). And attempts to reduce the rate of false positives to the bare possible minimum would tend to seriously worsen the risk of letting a dangerously defective device run.

Q2: Are the changes an improvement?

The removal of the prescribed test is a great improvement. Now, competent implementors are at least able to make something that reliably operates when not defective, and reliably stops operating when it becomes defective. And the incentive to add conditioning (like a LFSR) that allows to pass certification at the expense of actual field security is gone. Previously, with some perfectly sound TRNG sources (like with a bias of a few percents, which is fine when followed by a CSPRNG), what was prescribed could not be the main defense against likely defects of the TRNG source. All modern methodology for RNG certification, like AIS31, recognize the need for some access to the TRNG source before conditioning, or/and a model of the source, and adapting the tests to that (including making more comprehensive tests when a first one failed).

Changes in test limits made from FIPS 140-1 to FIPS 140-2 with Change Notice 1 make each of the tests significantly dramatically more stringent (and thus much more impractical when used to test an unconditioned TRNG, and generating more false positives even for a conditioned one or a CSPRNG). I think I remember reading or hearing (sorry for the imprecision of that uncertain non-reference) that at least some of these changes are also related to the fact that the tests are not independent (thus it matters to the false positive rate if the 20000 bits in the 4 tests are from the same or different runs, the later significantly increasing the false-positive rate). The changes in the acceptance level in the runs test made in FIPS 140-2 Change Notice 1 (from FIPS 140-2 before that) is documented (page 54) to be a " correction ", that seems credible. Notice that the question gives, for the runs test of FIPS 140-2, a table of the erroneous bounds of FIPS 140-2 without Change Notice 1.

Update: As pointed by poncho in a comment, the increase in false positive rate from FIPS 140-1 to FIPS 140-2 (CN1) is dramatic, more than a hundredfold in the monobit test assuming a perfect source:$$1-\sum_{i=9,655}^{10,345}{20,000\choose i}/2^{20,000}\approx1/974,603\text{ for FIPS 140-1}$$ $$1-\sum_{i=9,726}^{10,274}{20,000\choose i}/2^{20,000}\approx1/9,662\text{ for FIPS 140-2}$$ What's worse, if one defines a good source as one that is less biased than some threshold (a reasonable requirement for a physical TRNG), the false positive rate can go from rare for FIPS 140-1 bounds to totally disrupting for FIPS 140-2 bounds; that probably eased making the right decision and removing the tests altogether.

Q3: Are bounds for the run test inclusive?

Perhaps that could be determined by computing the odds of failure with and without the limits of the intervals given for a true random source, and seeing if some some round number emerges.

But why care? Statistical tests of the output a conditioned RNG, including any CSPRNG, is pointless; and has not been indispensable to get rubber-stamped since late 2002. And while the statistical test of an unconditioned TRNG source are necessary (and the tests in FIPS 140-1&2 rather sound), the acceptance levels of FIPS 140-1, and much more FIPS 140-2, are typically too harsh unless there is some backup strategy (like redoing a more complete test; notice that redoing the same test drastically alter the meaning of its original acceptance level).

Answer 2

The rationale for no longer mandating these tests include:

• These tests are generally not useful against most FIPS 140-2 approved random number generators.
• These tests can be useful against some kind of entropy sources.
• These tests give frequent false positives every few thousandth block of truely random stream will fail the test.
• Some entropy sources are biased, and such entropy sources cannot be tested via these tests without conditioning (which brings in other issues).

So all in all, it was found out that these tests are not universally useful, but that in many circumstances some other tests work better, and attempting to universally require these tests was counter productive.

NIST is in process of redefining approved strategies for random number generation. They are creating documents NIST SP 800-90A, B, C. The part A is finished and parts B and C are currently draft. The NIST SP 800-90A defines approved constructs for random number generation. The earlier random number generators, for instance RNGs from FIPS 186-2 have been deprecated and are disallowed after 2015.

NIST SP 800-90B (Recommendation for the Entropy Sources Used for Random Bit Generation, draft) contains advice on testing entropy sources. It considers conditioned entropy source, full entropy sources and other entropy sources. In a sense, this NIST SP 800-90B document is a kind of successor for these tests, which were once in FIPS 140-2.

In FIPS 140-2 validation, it is necessary to point out that generated keys are based on sufficient entropy (or that entropy available for module is modified by currently available entropy). When implementing this requirement, for some RNGs, the old FIPS 140-2 tests may be useful. Alternatively, it is possible that NIST SP 800-90B draft is useful.