2
$\begingroup$

I have a question on how to interpret test results of NIST test suite. First, when the asterisk mark appear on the report, what does it mean? I thought it means the random sequence fails the test. However, some p-values are more than 0.01 and it appears

enter image description here

second, some tests have p-value lower than 0.01. However, the asterisk mark did not appear. why is that (like the RUN test in the report below.)

enter image description here

$\endgroup$

2 Answers 2

2
$\begingroup$

when the asterisk mark appear on the report, what does it mean?

The * shown in the question appears when we should reject the hypothesis of true uniform random input with low probability of false rejection, based on the fraction on the left, where the numerator is the number of "successful" tests, and the denominator is the number of tests, with test's type on the right.

We must turn to the source code to find that the * tells that in this fraction passCount/sampleSize the numerator is out of bounds [proportion_threshold_min, proportion_threshold_max] computed as:

p_hat = 1.0 - ALPHA;
proportion_threshold_max = (p_hat + 3.0 * sqrt((p_hat*ALPHA)/sampleSize)) * sampleSize;
proportion_threshold_min = (p_hat - 3.0 * sqrt((p_hat*ALPHA)/sampleSize)) * sampleSize;

where parameter ALPHA (by default $\alpha=0.01=1\%$) "denotes the significance level that determines the region of acceptance and rejection", and (thus) the expected proportion of tests that fail for true uniform random input. The formulas for these bounds are asymptotically those of the "3-sigma rule" (probability $0.27\%$ that passCount is outside the bounds under a Gaussian assumption of the distribution), with rounding to nearest integer. Notice it takes many tests before that stabilizes! The table below gives the [Min, Max] interval for acceptance (no *), and the residual probability that the * appears for true uniform random input.

Tests      1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33    34    35    36    37    38    39    40    41    42    43    44    45    46    47    48    49    50    55    60    65    70    75    80    85    90    95   100   105   110   115   120   125   130   135   140   145   150   155   160   165   170   175   180   185   190   195   200   205   210   215   220   225   230   235   240   245   250   255   260   265   270   275   280   285   290   295   300   305   310   315   320   325   330   335   340   345   350   355   360   365   370   375   380   385   390   395   400   405   410   415   420   425   430   435   440   445   450   455   460   465   470   475   480   485   490   495   500   510   520   530   540   550   560   570   580   590   600   610   620   630   640   650   660   670   680   690   700   710   720   730   740   750   760   770   780   790   800   810   820   830   840   850   860   870   880   890   900   910   920   930   940   950   960   970   980   990  1000  1010  1020  1030  1040  1050  1060  1070  1080  1090  1100  1110  1120  1130  1140  1150  1160  1170  1180  1190  1200  1210  1220  1230  1240  1250  1260  1270  1280  1290  1300  1310  1320  1330  1340  1350  1360  1370  1380  1390  1400  1410  1420  1430  1440  1450  1460  1470  1480  1490  1500  1510  1520  1530  1540  1550  1560  1570  1580  1590  1600  1610  1620  1630  1640  1650  1660  1670  1680  1690  1700  1710  1720  1730  1740  1750  1760  1770  1780  1790  1800  1810  1820  1830  1840  1850  1860  1870  1880  1890  1900  1910  1920  1930  1940  1950  1960  1970  1980  1990  2000
Min        1     2     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    18    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33    34    35    36    37    38    39    40    41    42    43    44    44    45    46    47    52    57    62    67    72    77    81    86    91    96   101   106   111   116   120   125   130   135   140   145   150   155   160   164   169   174   179   184   189   194   199   204   208   213   218   223   228   233   238   243   248   253   257   262   267   272   277   282   287   292   297   302   307   311   316   321   326   331   336   341   346   351   356   361   365   370   375   380   385   390   395   400   405   410   415   420   424   429   434   439   444   449   454   459   464   469   474   478   483   488   498   508   518   528   537   547   557   567   577   587   597   606   616   626   636   646   656   665   675   685   695   705   715   724   734   744   754   764   774   784   793   803   813   823   833   843   852   862   872   882   892   902   912   921   931   941   951   961   971   981   990  1000  1010  1020  1030  1040  1050  1059  1069  1079  1089  1099  1109  1119  1128  1138  1148  1158  1168  1178  1188  1197  1207  1217  1227  1237  1247  1257  1266  1276  1286  1296  1306  1316  1326  1335  1345  1355  1365  1375  1385  1395  1404  1414  1424  1434  1444  1454  1464  1473  1483  1493  1503  1513  1523  1533  1542  1552  1562  1572  1582  1592  1602  1612  1621  1631  1641  1651  1661  1671  1681  1690  1700  1710  1720  1730  1740  1750  1759  1769  1779  1789  1799  1809  1819  1829  1838  1848  1858  1868  1878  1888  1898  1907  1917  1927  1937  1947  1957  1967
Max        1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33    34    35    36    37    38    39    40    41    42    43    44    45    46    47    48    49    50    55    60    65    70    75    80    85    90    95   100   105   110   115   120   125   130   135   140   145   150   155   160   165   170   175   180   185   190   195   200   205   210   215   220   225   230   235   240   245   250   255   260   265   270   275   280   285   290   295   300   305   310   315   320   325   330   335   340   345   350   355   360   365   370   375   380   385   390   395   400   405   410   415   420   425   430   435   440   445   450   455   460   465   470   475   480   485   490   495   500   510   520   530   540   550   560   570   580   590   600   610   620   630   640   650   660   670   680   690   700   710   720   730   740   750   760   770   780   790   800   810   820   830   840   850   860   870   880   890   900   910   920   930   940   950   960   970   980   989   999  1009  1019  1029  1039  1049  1059  1069  1079  1089  1099  1109  1119  1129  1139  1149  1159  1169  1178  1188  1198  1208  1218  1228  1238  1248  1258  1268  1278  1288  1298  1308  1318  1328  1338  1347  1357  1367  1377  1387  1397  1407  1417  1427  1437  1447  1457  1467  1477  1487  1497  1506  1516  1526  1536  1546  1556  1566  1576  1586  1596  1606  1616  1626  1636  1646  1656  1665  1675  1685  1695  1705  1715  1725  1735  1745  1755  1765  1775  1785  1795  1805  1815  1824  1834  1844  1854  1864  1874  1884  1894  1904  1914  1924  1934  1944  1954  1964  1973  1983  1993
Prob[*] 1.00% 1.99% 0.03% 0.06% 0.10% 0.15% 0.20% 0.27% 0.34% 0.43% 0.52% 0.62% 0.72% 0.84% 0.96% 1.09% 1.23% 1.38% 1.53% 0.10% 0.12% 0.13% 0.15% 0.17% 0.20% 0.22% 0.24% 0.27% 0.30% 0.33% 0.36% 0.40% 0.44% 0.47% 0.52% 0.56% 0.60% 0.65% 0.70% 0.75% 0.80% 0.86% 0.92% 0.98% 1.04% 1.10% 0.13% 0.14% 0.15% 0.16% 0.23% 0.31% 0.42% 0.54% 0.69% 0.87% 0.17% 0.22% 0.28% 0.34% 0.42% 0.51% 0.62% 0.74% 0.17% 0.21% 0.25% 0.30% 0.36% 0.42% 0.49% 0.57% 0.66% 0.17% 0.21% 0.24% 0.28% 0.32% 0.37% 0.43% 0.49% 0.56% 0.16% 0.18% 0.21% 0.24% 0.28% 0.32% 0.36% 0.40% 0.45% 0.51% 0.16% 0.18% 0.20% 0.23% 0.26% 0.29% 0.32% 0.36% 0.40% 0.45% 0.49% 0.16% 0.18% 0.21% 0.23% 0.26% 0.28% 0.31% 0.35% 0.38% 0.42% 0.46% 0.16% 0.18% 0.20% 0.22% 0.24% 0.27% 0.29% 0.32% 0.35% 0.39% 0.42% 0.46% 0.17% 0.19% 0.21% 0.23% 0.25% 0.27% 0.30% 0.32% 0.35% 0.38% 0.41% 0.16% 0.17% 0.19% 0.23% 0.27% 0.31% 0.36% 0.16% 0.19% 0.22% 0.26% 0.30% 0.34% 0.40% 0.18% 0.21% 0.24% 0.28% 0.32% 0.37% 0.17% 0.20% 0.23% 0.26% 0.30% 0.34% 0.16% 0.18% 0.21% 0.24% 0.28% 0.31% 0.35% 0.17% 0.20% 0.22% 0.25% 0.29% 0.32% 0.16% 0.18% 0.20% 0.23% 0.26% 0.29% 0.33% 0.16% 0.19% 0.21% 0.23% 0.26% 0.30% 0.33% 0.17% 0.19% 0.22% 0.24% 0.27% 0.30% 0.33% 0.17% 0.19% 0.21% 0.24% 0.27% 0.29% 0.33% 0.17% 0.19% 0.21% 0.25% 0.27% 0.30% 0.33% 0.18% 0.20% 0.22% 0.24% 0.26% 0.29% 0.32% 0.17% 0.19% 0.21% 0.23% 0.26% 0.28% 0.32% 0.18% 0.20% 0.22% 0.24% 0.26% 0.28% 0.31% 0.17% 0.19% 0.21% 0.23% 0.25% 0.27% 0.29% 0.17% 0.20% 0.21% 0.23% 0.25% 0.27% 0.29% 0.17% 0.18% 0.20% 0.22% 0.23% 0.25% 0.28% 0.30% 0.17% 0.19% 0.22% 0.24% 0.26% 0.28% 0.30% 0.18% 0.19% 0.21% 0.22% 0.24% 0.26% 0.28% 0.17% 0.18% 0.19% 0.21% 0.25% 0.26% 0.28% 0.30% 0.18% 0.20% 0.21% 0.23% 0.24% 0.26% 0.28% 0.17% 0.18% 0.20% 0.21% 0.25% 0.26% 0.28%

In the question's occurence of *, there are $41$ tests, the acceptance interval is $[39,41]$, and the residual probability that the * appears (as it does) is $0.80\%$. However the number of successes is $37$, which is more than one outside the acceptance interval, and the actual probability of such result is $$1-\sum_{38\le k\le41}{\binom{41}k(1-\alpha)^k \alpha^{41-k}}\quad\approx 0.075\%$$ Even considering that's one out of four RandomExcursionsVariant series of tests, it's a reason for alarm. At least, the series of tests should be repeated with different seed, or much more tests.


There can also be a * on the right of the P-value. Looking at the source tells that's for sampleSize<10. Note 11 in the nice manual correspondingly tells that the P-value "is undefined if less than 10 sequences are processed. As noted Section 4.2 at least 55 sequences must be processed to derive statistically meaningful results for the uniformity of p-values".


Some tests have P-value lower than 0.01. However, the asterisk mark did not appear. Why is that?

That's because the * appears on the basis of the number of failed tests, not based on the P-value shown.

At a different level, that's in some sense because for uniformly random input, the * appears with significantly lower probability ($0.27\%$ asymptotic target, $0.69\%$ for $75$ tests) than the probability ($1\%$) that the P-value is lower than $0.01$ as in the observation made.

Further, I think that the range to be considered should be $[0.005,0.995]$ for the $99\%$ confidence level, and the question's 0.005033 falls within that, if only barely.

Even further, with 6 series of tests and such $99\%$ confidence level on each series, we only have about $94\%$ confidence level that no series fail.


As usual: passing the NIST test, or any statistical test of the generator's output, is not a valid argument towards the suitability of a PRNG or TRNG for cryptographic purposes, contrary to what countless publications pretend or let suppose. As an illustration, NIST's Dual_EC_DRBG passes the NIST test, even though it is experimentally distinguishable from random and (independently) backdoorable by design, thus must be considered insecure, and has been exploited.

$\endgroup$
2
  • $\begingroup$ Thank you for the clear expanation $\endgroup$
    – O. Nawwar
    Commented Aug 29, 2023 at 6:18
  • $\begingroup$ @O.Nawwar: I've added an hopefully useful table, and a discussion on the significance of the series of tests that generated the *. $\endgroup$
    – fgrieu
    Commented Aug 29, 2023 at 8:34
1
$\begingroup$

enter image description here

I think this image can help you! I hope you succeed!

$\endgroup$
2
  • $\begingroup$ Do you not think that $\alpha = 0.0001$ is ridiculously lax? Especially given that this applies to cryptography... $\endgroup$
    – Paul Uszak
    Commented Dec 26, 2023 at 15:15
  • $\begingroup$ And welcome to the site :-) $\endgroup$
    – Paul Uszak
    Commented Dec 26, 2023 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.