Paper 2022/540

On the revision of NIST 800-22 Test Suites

Katarzyna Anna Kowalska, Davide Fogliano, and Jose Garcia Coello

Abstract

At Crypta Labs we are developing Quantum Random Number Generator technology and are using different random number test suites to assess the quality of our products. Among these is the NIST 800-22 suite. When testing our datasets, we found that we were consistently failing one particular test: the Overlapping Template Matching test. This was surprising to us, so we fed data from a known PRNG source into the same test and discovered that NIST approved PRNG was also failing in a similar fashion. At this point we decided to debug NIST's code. We did indeed find an error within the probability calculations and, once corrected, ran the tests again and passed. The code for this test had previously been revised by NIST due to an incorrect calculation of the probabilities, however, later in the revised source code the corrected calculations were calculated again using the originally incorrect formulas, and these overwrote the revised fix. Furthermore, the NIST 800-22 Test suite is currently under revision and our paper is a contribution towards it.