Why does mt19937 fail the universal test in NIST SP 800-22?

Question

Update: with the help of @SqueamishOssifrage and @PaulUzdak, we discovered that my NIST SP 800-22 has a broken universal test. So this becomes a moot question.

Check this report. It seems to sail through all tests, but all p-values of the universal test fall in the first 10-percentile. I've set the generator's seed to 1. Here's my configuration of the assess program:

$ ./assess 100000
           G E N E R A T O R    S E L E C T I O N
           ______________________________________

    [0] Input File                 [1] Linear Congruential
    [2] Quadratic Congruential I   [3] Quadratic Congruential II
    [4] Cubic Congruential         [5] XOR
    [6] Modular Exponentiation     [7] Blum-Blum-Shub
    [8] Micali-Schnorr             [9] G Using SHA-1

   Enter Choice: 0


                User Prescribed Input File: mt19937-seed-1.dat

                S T A T I S T I C A L   T E S T S
                _________________________________

    [01] Frequency                       [02] Block Frequency
    [03] Cumulative Sums                 [04] Runs
    [05] Longest Run of Ones             [06] Rank
    [07] Discrete Fourier Transform      [08] Nonperiodic Template Matchings
    [09] Overlapping Template Matchings  [10] Universal Statistical
    [11] Approximate Entropy             [12] Random Excursions
    [13] Random Excursions Variant       [14] Serial
    [15] Linear Complexity

         INSTRUCTIONS
            Enter 0 if you DO NOT want to apply all of the
            statistical tests to each sequence and 1 if you DO.

   Enter Choice: 1

        P a r a m e t e r   A d j u s t m e n t s
        -----------------------------------------
    [1] Block Frequency Test - block length(M):         128
    [2] NonOverlapping Template Test - block length(m): 9
    [3] Overlapping Template Test - block length(m):    9
    [4] Approximate Entropy Test - block length(m):     10
    [5] Serial Test - block length(m):                  16
    [6] Linear Complexity Test - block length(M):       500

   Select Test (0 to continue): 0

   How many bitstreams? 10

   Input File Format:
    [0] ASCII - A sequence of ASCII 0's and 1's
    [1] Binary - Each byte in data file contains 8 bits of data

   Select input mode:  1

     Statistical Testing In Progress.........

     Statistical Testing Complete!!!!!!!!!!!!

$

The reason I'm using the sample size 100000 is because NIST SP 800-22 mentions it as a possible size. (See also appendix E, page 121: "[d]uring the testing phase, NIST commonly evaluated sequences on the order $10^6$.") I have no idea what is the ideal size.

------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
   generator is <mt19937-seed-1.dat>
------------------------------------------------------------------------------
 C1  C2  C3  C4  C5  C6  C7  C8  C9 C10  P-VALUE  PROPORTION  STATISTICAL TEST
------------------------------------------------------------------------------
  2   1   1   0   3   0   0   1   1   1  0.534146     10/10      Frequency
  4   1   1   0   1   0   0   1   0   2  0.122325      9/10      BlockFrequency
  1   2   1   0   1   1   1   1   2   0  0.911413     10/10      CumulativeSums
  2   0   1   0   2   0   2   1   2   0  0.534146     10/10      CumulativeSums
  1   1   4   0   0   0   2   1   1   0  0.122325     10/10      Runs
  1   2   1   1   0   2   1   0   0   2  0.739918     10/10      LongestRun
  1   1   1   0   1   2   0   1   2   1  0.911413     10/10      Rank
  0   1   0   2   1   1   1   0   3   1  0.534146     10/10      FFT
  2   0   2   0   1   0   1   2   1   1  0.739918     10/10      NonOverlappingTemplate
  2   2   3   0   0   1   0   0   1   1  0.350485     10/10      NonOverlappingTemplate
  0   1   3   1   1   1   0   1   1   1  0.739918     10/10      NonOverlappingTemplate
  3   1   0   2   1   1   0   0   1   1  0.534146     10/10      NonOverlappingTemplate
  1   2   1   1   1   1   2   0   1   0  0.911413     10/10      NonOverlappingTemplate
  1   2   0   2   1   0   0   2   1   1  0.739918     10/10      NonOverlappingTemplate
  1   2   0   0   2   2   0   1   1   1  0.739918     10/10      NonOverlappingTemplate
  1   1   3   0   0   2   2   0   0   1  0.350485     10/10      NonOverlappingTemplate
  0   1   0   2   2   1   1   1   1   1  0.911413     10/10      NonOverlappingTemplate
  1   1   0   0   0   1   2   1   1   3  0.534146     10/10      NonOverlappingTemplate
  1   0   1   1   2   2   0   1   1   1  0.911413     10/10      NonOverlappingTemplate
  1   1   0   3   0   0   2   0   1   2  0.350485      9/10      NonOverlappingTemplate
  2   0   1   1   2   1   2   0   1   0  0.739918     10/10      NonOverlappingTemplate
  0   3   1   1   2   1   1   0   0   1  0.534146     10/10      NonOverlappingTemplate
  0   0   2   2   1   3   1   1   0   0  0.350485     10/10      NonOverlappingTemplate
  3   0   1   0   1   3   2   0   0   0  0.122325     10/10      NonOverlappingTemplate
  0   0   1   2   2   1   1   2   0   1  0.739918     10/10      NonOverlappingTemplate
  1   0   3   1   0   0   2   1   1   1  0.534146     10/10      NonOverlappingTemplate
  1   0   1   3   1   1   1   1   1   0  0.739918     10/10      NonOverlappingTemplate
  2   1   2   0   0   0   0   3   1   1  0.350485     10/10      NonOverlappingTemplate
  2   0   0   1   0   1   2   3   1   0  0.350485      9/10      NonOverlappingTemplate
  0   1   1   1   0   0   0   4   1   2  0.122325     10/10      NonOverlappingTemplate
  0   3   2   1   1   0   1   1   1   0  0.534146     10/10      NonOverlappingTemplate
  1   0   0   0   3   0   2   1   3   0  0.122325     10/10      NonOverlappingTemplate
  3   1   0   0   2   0   0   2   1   1  0.350485      9/10      NonOverlappingTemplate
  0   1   2   1   0   0   3   2   0   1  0.350485     10/10      NonOverlappingTemplate
  0   1   2   1   0   0   2   1   1   2  0.739918     10/10      NonOverlappingTemplate
  0   1   1   1   0   1   1   1   2   2  0.911413     10/10      NonOverlappingTemplate
  2   2   0   0   0   1   2   2   0   1  0.534146     10/10      NonOverlappingTemplate
  1   1   0   2   0   1   0   0   2   3  0.350485     10/10      NonOverlappingTemplate
  1   2   0   1   0   0   1   3   2   0  0.350485     10/10      NonOverlappingTemplate
  1   1   1   0   0   2   2   2   1   0  0.739918     10/10      NonOverlappingTemplate
  1   0   2   1   2   0   2   0   0   2  0.534146     10/10      NonOverlappingTemplate
  0   2   1   1   0   1   0   3   0   2  0.350485     10/10      NonOverlappingTemplate
  0   1   1   3   3   0   1   0   1   0  0.213309     10/10      NonOverlappingTemplate
  0   3   1   0   1   2   0   0   2   1  0.350485     10/10      NonOverlappingTemplate
  0   1   1   1   2   0   0   2   1   2  0.739918     10/10      NonOverlappingTemplate
  1   1   3   1   1   0   0   1   1   1  0.739918     10/10      NonOverlappingTemplate
  0   0   1   0   0   1   2   5   1   0  0.008879     10/10      NonOverlappingTemplate
  1   1   0   1   1   1   1   3   0   1  0.739918     10/10      NonOverlappingTemplate
  0   1   0   1   1   1   1   2   1   2  0.911413     10/10      NonOverlappingTemplate
  1   1   1   0   0   1   1   2   2   1  0.911413     10/10      NonOverlappingTemplate
  0   1   1   2   1   1   2   0   1   1  0.911413     10/10      NonOverlappingTemplate
  0   1   0   2   1   1   3   0   1   1  0.534146     10/10      NonOverlappingTemplate
  1   1   2   2   0   3   0   0   1   0  0.350485     10/10      NonOverlappingTemplate
  0   3   1   1   1   1   1   0   0   2  0.534146     10/10      NonOverlappingTemplate
  1   2   1   1   0   1   2   2   0   0  0.739918     10/10      NonOverlappingTemplate
  0   2   0   1   1   2   3   0   1   0  0.350485     10/10      NonOverlappingTemplate
  1   1   1   1   1   0   1   1   1   2  0.991468     10/10      NonOverlappingTemplate
  2   0   0   2   0   1   1   2   2   0  0.534146     10/10      NonOverlappingTemplate
  1   1   3   0   0   0   4   0   0   1  0.035174     10/10      NonOverlappingTemplate
  0   1   1   0   1   0   1   3   0   3  0.213309     10/10      NonOverlappingTemplate
  2   1   0   0   2   0   2   1   1   1  0.739918     10/10      NonOverlappingTemplate
  2   1   3   1   0   0   0   0   1   2  0.350485     10/10      NonOverlappingTemplate
  0   2   1   1   1   2   1   0   2   0  0.739918     10/10      NonOverlappingTemplate
  2   0   0   1   0   4   0   1   1   1  0.122325     10/10      NonOverlappingTemplate
  1   2   1   0   0   1   2   1   2   0  0.739918      9/10      NonOverlappingTemplate
  1   1   1   2   0   0   2   0   2   1  0.739918     10/10      NonOverlappingTemplate
  1   1   3   1   0   1   0   1   2   0  0.534146     10/10      NonOverlappingTemplate
  0   1   3   2   0   1   0   2   1   0  0.350485     10/10      NonOverlappingTemplate
  0   1   0   1   0   3   2   2   0   1  0.350485     10/10      NonOverlappingTemplate
  2   1   0   2   0   0   0   4   0   1  0.066882     10/10      NonOverlappingTemplate
  0   1   2   1   1   2   0   1   0   2  0.739918     10/10      NonOverlappingTemplate
  3   0   1   0   1   0   1   1   0   3  0.213309     10/10      NonOverlappingTemplate
  1   1   1   1   1   2   1   0   2   0  0.911413      9/10      NonOverlappingTemplate
  0   1   3   0   2   0   1   1   2   0  0.350485     10/10      NonOverlappingTemplate
  1   1   1   0   2   0   1   0   2   2  0.739918     10/10      NonOverlappingTemplate
  0   1   0   1   3   1   0   0   3   1  0.213309     10/10      NonOverlappingTemplate
  2   2   2   0   0   2   0   0   0   2  0.350485     10/10      NonOverlappingTemplate
  1   3   0   0   1   3   0   2   0   0  0.122325      9/10      NonOverlappingTemplate
  1   1   0   0   2   1   0   1   3   1  0.534146      9/10      NonOverlappingTemplate
  0   1   0   2   1   1   2   0   1   2  0.739918     10/10      NonOverlappingTemplate
  0   0   1   1   0   1   0   1   3   3  0.213309     10/10      NonOverlappingTemplate
  0   0   3   3   0   0   1   1   2   0  0.122325     10/10      NonOverlappingTemplate
  2   0   2   0   1   0   1   2   1   1  0.739918     10/10      NonOverlappingTemplate
  0   0   3   0   2   0   0   2   2   1  0.213309     10/10      NonOverlappingTemplate
  2   3   0   1   1   1   2   0   0   0  0.350485     10/10      NonOverlappingTemplate
  1   1   1   0   3   1   0   1   0   2  0.534146     10/10      NonOverlappingTemplate
  1   0   1   1   1   1   2   2   0   1  0.911413     10/10      NonOverlappingTemplate
  0   1   0   0   1   3   1   0   2   2  0.350485     10/10      NonOverlappingTemplate
  2   1   3   0   0   0   2   1   1   0  0.350485      9/10      NonOverlappingTemplate
  0   0   2   1   2   2   0   0   0   3  0.213309     10/10      NonOverlappingTemplate
  2   2   0   1   0   1   1   1   2   0  0.739918     10/10      NonOverlappingTemplate
  0   1   1   1   0   3   1   0   0   3  0.213309     10/10      NonOverlappingTemplate
  2   0   2   1   2   1   1   0   1   0  0.739918     10/10      NonOverlappingTemplate
  2   2   0   1   2   1   0   0   2   0  0.534146      9/10      NonOverlappingTemplate
  2   0   1   1   2   1   2   0   0   1  0.739918     10/10      NonOverlappingTemplate
  1   1   0   2   0   3   2   1   0   0  0.350485     10/10      NonOverlappingTemplate
  2   0   1   1   1   1   0   2   1   1  0.911413     10/10      NonOverlappingTemplate
  0   1   1   2   2   0   1   0   1   2  0.739918     10/10      NonOverlappingTemplate
  0   1   2   1   0   3   0   2   1   0  0.350485     10/10      NonOverlappingTemplate
  1   1   2   0   2   1   2   0   0   1  0.739918     10/10      NonOverlappingTemplate
  0   3   0   0   2   0   1   3   0   1  0.122325     10/10      NonOverlappingTemplate
  1   0   0   1   3   1   2   1   1   0  0.534146     10/10      NonOverlappingTemplate
  0   0   0   1   1   2   0   0   2   4  0.066882     10/10      NonOverlappingTemplate
  1   1   0   2   1   2   1   1   1   0  0.911413     10/10      NonOverlappingTemplate
  0   0   1   0   1   2   3   1   2   0  0.350485     10/10      NonOverlappingTemplate
  1   4   1   0   1   0   0   0   3   0  0.035174     10/10      NonOverlappingTemplate
  1   1   2   3   0   0   0   0   2   1  0.350485     10/10      NonOverlappingTemplate
  1   1   0   1   2   2   2   0   1   0  0.739918     10/10      NonOverlappingTemplate
  0   1   1   1   3   1   1   0   1   1  0.739918     10/10      NonOverlappingTemplate
  1   0   2   0   2   1   0   1   3   0  0.350485     10/10      NonOverlappingTemplate
  1   1   0   1   0   0   4   2   1   0  0.122325      9/10      NonOverlappingTemplate
  2   2   1   0   3   0   1   1   0   0  0.350485     10/10      NonOverlappingTemplate
  2   1   2   2   0   0   1   1   0   1  0.739918      9/10      NonOverlappingTemplate
  1   0   0   1   2   2   0   0   2   2  0.534146     10/10      NonOverlappingTemplate
  1   2   1   2   1   1   0   0   1   1  0.911413      9/10      NonOverlappingTemplate
  2   1   0   2   0   1   3   0   1   0  0.350485      9/10      NonOverlappingTemplate
  2   0   1   0   2   1   1   1   0   2  0.739918     10/10      NonOverlappingTemplate
  3   2   2   0   1   0   0   0   1   1  0.350485     10/10      NonOverlappingTemplate
  2   2   1   0   1   2   1   0   0   1  0.739918     10/10      NonOverlappingTemplate
  1   0   2   1   1   2   2   1   0   0  0.739918      9/10      NonOverlappingTemplate
  1   0   2   0   1   2   0   0   2   2  0.534146     10/10      NonOverlappingTemplate
  1   2   0   0   0   1   2   2   1   1  0.739918     10/10      NonOverlappingTemplate
  0   1   1   1   1   0   1   2   2   1  0.911413     10/10      NonOverlappingTemplate
  1   0   2   2   0   0   2   3   0   0  0.213309     10/10      NonOverlappingTemplate
  1   3   0   0   0   0   2   2   0   2  0.213309     10/10      NonOverlappingTemplate
  1   0   2   2   1   1   1   0   0   2  0.739918     10/10      NonOverlappingTemplate
  0   3   0   0   1   1   1   1   1   2  0.534146     10/10      NonOverlappingTemplate
  1   0   1   3   0   1   2   1   0   1  0.534146     10/10      NonOverlappingTemplate
  1   0   0   1   1   4   1   1   1   0  0.213309     10/10      NonOverlappingTemplate
  2   0   2   0   2   0   1   1   2   0  0.534146     10/10      NonOverlappingTemplate
  1   0   3   0   0   1   0   2   0   3  0.122325     10/10      NonOverlappingTemplate
  2   0   2   1   0   1   1   1   1   1  0.911413     10/10      NonOverlappingTemplate
  1   4   1   1   1   0   0   1   1   0  0.213309      9/10      NonOverlappingTemplate
  2   1   1   1   2   0   1   0   1   1  0.911413     10/10      NonOverlappingTemplate
  1   0   0   1   0   5   0   2   0   1  0.008879     10/10      NonOverlappingTemplate
  1   1   0   2   1   0   1   0   4   0  0.122325     10/10      NonOverlappingTemplate
  1   1   1   2   1   1   1   1   0   1  0.991468     10/10      NonOverlappingTemplate
  3   3   0   0   2   0   1   0   0   1  0.122325     10/10      NonOverlappingTemplate
  0   0   1   2   1   3   2   0   0   1  0.350485     10/10      NonOverlappingTemplate
  1   4   0   0   0   0   1   2   0   2  0.066882     10/10      NonOverlappingTemplate
  1   1   0   1   4   1   1   0   0   1  0.213309     10/10      NonOverlappingTemplate
  2   0   1   0   1   0   1   2   2   1  0.739918      9/10      NonOverlappingTemplate
  0   1   1   2   1   1   1   2   0   1  0.911413     10/10      NonOverlappingTemplate
  0   1   1   2   1   2   1   1   1   0  0.911413     10/10      NonOverlappingTemplate
  2   2   0   0   1   1   4   0   0   0  0.066882      9/10      NonOverlappingTemplate
  1   1   0   1   2   3   0   1   1   0  0.534146     10/10      NonOverlappingTemplate
  2   0   0   2   0   1   1   1   1   2  0.739918     10/10      NonOverlappingTemplate
  2   1   0   0   2   1   0   2   1   1  0.739918     10/10      NonOverlappingTemplate
  3   0   0   0   0   1   2   1   2   1  0.350485     10/10      NonOverlappingTemplate
  0   1   3   0   1   1   0   1   2   1  0.534146     10/10      NonOverlappingTemplate
  2   1   0   0   0   1   5   0   1   0  0.008879     10/10      NonOverlappingTemplate
  1   2   1   1   2   0   2   0   1   0  0.739918     10/10      NonOverlappingTemplate
  4   1   2   1   0   0   1   1   0   0  0.122325      9/10      NonOverlappingTemplate
  2   0   1   2   1   1   0   1   0   2  0.739918     10/10      NonOverlappingTemplate
  1   2   0   2   0   2   1   1   0   1  0.739918     10/10      NonOverlappingTemplate
  0   0   3   3   0   0   1   1   2   0  0.122325     10/10      NonOverlappingTemplate
  1   1   2   0   2   0   2   1   1   0  0.739918     10/10      OverlappingTemplate
 10   0   0   0   0   0   0   0   0   0  0.000000 *    0/10   *  Universal
  1   0   1   1   2   2   3   0   0   0  0.350485     10/10      ApproximateEntropy
  1   0   0   0   0   0   0   0   0   0     ----       1/1       RandomExcursions
  0   0   0   0   0   0   1   0   0   0     ----       1/1       RandomExcursions
  0   0   1   0   0   0   0   0   0   0     ----       1/1       RandomExcursions
  0   0   0   0   0   0   1   0   0   0     ----       1/1       RandomExcursions
  1   0   0   0   0   0   0   0   0   0     ----       1/1       RandomExcursions
  1   0   0   0   0   0   0   0   0   0     ----       1/1       RandomExcursions
  1   0   0   0   0   0   0   0   0   0     ----       1/1       RandomExcursions
  0   0   0   0   1   0   0   0   0   0     ----       1/1       RandomExcursions
  0   0   0   1   0   0   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   1   0   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   0   1   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   0   0   0   1   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   0   0   0   0   0   1     ----       1/1       RandomExcursionsVariant
  0   0   0   0   0   1   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   1   0   0   0   0   0   0   0   0     ----       1/1       RandomExcursionsVariant
  1   0   0   0   0   0   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   1   0   0   0   0   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   1   0   0   0   0   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   1   0   0   0   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   0   0   1   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   0   0   0   0   1   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   1   0   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   1   0   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   0   1   0   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   0   0   1   0   0   0     ----       1/1       RandomExcursionsVariant
  0   0   0   0   0   0   0   1   0   0     ----       1/1       RandomExcursionsVariant
  0   3   0   1   1   0   3   0   0   2  0.122325     10/10      Serial
  1   1   0   0   2   1   1   1   2   1  0.911413     10/10      Serial
  0   1   1   1   0   2   1   3   0   1  0.534146     10/10      LinearComplexity

The file containing the data is a binary file containing all numbers output by mt19937 in little-endian format. It was produced by this program

#include <random>
#include <stdio.h>

using namespace std;

int main()
{
  unsigned int n;
  std::minstd_rand0 generator(1);

  for (;;) {
    n = generator();
    fwrite(&n, sizeof n, 1, stdout);
  }

  return 0;
}

For example, you can run

$ ./cppmt19937 > mt19937-seed-1.dat

and interrupt it after a few seconds. It'll have produced some megabytes of data.

Why is the universal test doing so well here? (FWIW, the same happens to the ranlux48 generator.)

Why wouldn't the universal test run well on the output of the Mersenne Twister? That it is not secure doesn't mean that it is not well distributed pseudo random, right? — Maarten Bodewes, Commented Sep 23, 2019 at 21:37
Mersenne Twister is failing the universal test. It's the universal test that's doing well, not the PRNG. — user45491, Commented Sep 23, 2019 at 21:41
Have you tried running the same test on, e.g., AES-CTR output under all-zero key and nonce? Is it reproducible on the Mersenne twister with different seeds? — Squeamish Ossifrage, Commented Sep 24, 2019 at 0:51
The ranlux48 link does not work for me and redirects to hastebin.com through the Internet Archive Wayback Machine. Can you please make a more accessible link for that? — Squeamish Ossifrage, Commented Sep 24, 2019 at 0:56
@SqueamishOssifrage, it looks like hastebin.com is not functioning properly right now. I'll try again later and download the data and add to the question. More soon. — user45491, Commented Sep 24, 2019 at 1:31

kodlu · Accepted Answer · 2019-09-23 22:18:46Z

The other answer is correct regarding the already known weakness of MT as a keystream generator.

Maurer has designed his test by evaluating the sample average of the repeat times of binary windows in an ergodic (more general than i.i.d.) binary source with finite memory and computing an estimate of the entropy of the source, based only on these features of the output of the keystream. Thus his test is a universal entropy rate estimator.

So he does not target a specific defect but structural defects.

See the discussion on pages 10-11 of his paper here. Later on, Coron found an error in a formula Maurer used in his paper, see here. Presumably the NIST test has taken this correction into account.

$\begingroup$ $ \text{IID} \in \text{Ergodic} $ ? $\endgroup$
– Paul Uszak
Commented Jan 18, 2021 at 14:23 — Paul Uszak, Commented Jan 18, 2021 at 14:23

Paul Uszak · Accepted Answer · 2019-09-23 23:58:59Z

Your testing is wrong somewhere I'm afraid.

MT is used throughout the world and is good enough for most scientists. Yes, it's not cryptographic and has some very minor defects in the higher dimensions. But the NIST Universal test has no chance of picking that up. If the simple ~100 lines of code in universal.c could invalidate the Twister, no one would use it.

There is zero correlation in it's output as I determined via permutation testing in line with NIST 800-90b, § 5.1. I used snappy, lzma, bz2 and zlib algorithms. cmix (one of the most powerful compressors in the world) can't compress it whatsoever. Remember that Maurer’s test is a compressability test after all. But most importantly, this is my output from the NIST Universal test:-

    ------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
   generator is </tmp/mt.bin>
------------------------------------------------------------------------------
 C1  C2  C3  C4  C5  C6  C7  C8  C9 C10  P-VALUE  PROPORTION  STATISTICAL TEST
------------------------------------------------------------------------------
  1   2   1   0   2   1   0   0   1   2  0.739918     10/10      Universal


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The minimum pass rate for each statistical test with the exception of the
random excursion (variant) test is approximately = 8 for a
sample size = 10 binary sequences.

The Twister aced it for a 10MB sample. We must then conclude that something went wrong with the test method given all the evidence supporting the Twister. Your line:-

10   0   0   0   0   0   0   0   0   0  0.000000 *    0/10   *  Universal
^^

with the 10 at one end indicates a very squiffy P distribution and a massive huge test failure. The probability of this occurring by chance is literally 0.000000.

The probability that a $p$-value rounded to 0.000000 occurs ‘by chance’ is about one in a million, just like the probability that a $p$-value rounded to 0.739918 occurs ‘by chance’. — Squeamish Ossifrage, Commented Sep 24, 2019 at 0:50
You got a point. It turns out, every generator I test under NIST SP 800-22 is failing the universal test. This actually closes this question as the question now is what is wrong with my test suite. — user45491, Commented Sep 24, 2019 at 1:37
@user45491 I'm both glad and sorry then :-) Glad to have helped, but sorry that you've now got another problem. But it's a curious one. Are you able to accept this answer then to formally close out the question? — Paul Uszak, Commented Sep 24, 2019 at 2:36

Ripon Patgiri · Accepted Answer · 2021-01-18 04:27:16Z

1

I solved it. It happens due to low range in ./assess 100000. Here, it must be at least 387840 but 387840<100000, which will not work. Moreover, assess value must be >=387840.

answered Jan 18, 2021 at 4:27

Ripon Patgiri

111 bronze badge

Add a comment |

Squeamish Ossifrage · Accepted Answer · 2019-10-24 02:06:13Z

There are three possibilities, in general:

Your implementation of the Mersenne twister or of the test, or of something involved to wire them together, has a bug.
By a fluke, the test raised a false alarm. Under the null hypothesis of uniform random inputs, any test with ‘significance level’ at (say) 5% raises a false alarm for 5% of the test runs.
The Mersenne twister interacts with this test so that the test has high statistical power to distinguish it from uniform random—in other words, this test is an attack against the Mersenne twister. You'll have to find out how the test works, and study how it interacts with the Mersenne twister.

(I don't know exactly what the test does; if you want to ask a question about this, please include details about what the test does in your question.)

Either way, there is very little cryptographic significance to this. Maybe the test makes for a good distinguisher, but we already know a good distinguisher for the Mersenne twister so it would be foolish to use it for cryptography anyway.

Would the downvoter care to explain what Paul disagrees with in this answer? — Squeamish Ossifrage, Commented Sep 24, 2019 at 0:46
You got a point. It seems the test is not correctly implemented. Every generator I test under NIST SP 800-22 is failing the universal test. This actually closes this question as the question now is what is wrong with my test suite. — user45491, Commented Sep 24, 2019 at 1:38

Stack Exchange Network

Why does mt19937 fail the universal test in NIST SP 800-22?

4 Answers 4

Your Answer

Not the answer you're looking for? Browse other questions tagged
random-number-generator
randomness
pseudo-random-generator
statistical-test
or ask your own question.

Linked

Hot Network Questions

Why does mt19937 fail the universal test in NIST SP 800-22?

4 Answers 4

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged random-number-generatorrandomnesspseudo-random-generatorstatistical-test or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
random-number-generator
randomness
pseudo-random-generator
statistical-test
or ask your own question.