Back to Homepage


NIST statistical tests suite

 

 
The NIST statistical test suite (C sources) and documentation can be downloaded from http://csrc.nist.gov/rng.

Each of the 16 tests was applied on 50 data-streams generated by the VMPC Stream Cipher for 50 different keys. Following recommendations in the documentation and considering memory requirements of some of the tests the following parameters have been chosen for the tests:

* S denotes the length (in BITS) of each of the 50 tested data-streams
* P (P1,P2) denote additional parameters required by some of the tests

1.   Frequency Test:S=10.000.000;
2.   Frequency Test within a Block:S=10.000.000; P=200.000;
3.   Runs Test:S=10.000.000;
4.   Longest Run of Ones in a Block Test:S=10.000.000;
5.   Binary Matrix Rank Test:S=10.000.000;
6.   Discrete Fourier Transform Test:S=1.000.000;
7.   Non-Overlapping Template Matching Test:  S=10.000.000; P=9
8.   Overlapping Template Matching Test:S=10.000.000; P=9
9.   Maurer's Universal Statistical Test:S=10.000.000; P1=9; P2=5.120
10. Lempel-Ziv Compression Test:S=1.000.000;
11. Linear Complexity Test:S=10.000.000; P=1.000
12. Serial Test:S=10.000.000; P=10
13. Approximate Entropy Test:S=10.000.000; P=10
14. Cumulative Sums Test:S=10.000.000;
15. Random Excursions Test:S=10.000.000;
16. Random Excursions Variant Test:S=10.000.000;

The resulting P-values have been analysed by computing their average (A), their standard deviation (D), the expected standard deviation of the measured average (DA), the expected standard deviation of the measured standard deviation (DD) and by testing by how many standard deviations (DA and DD) the measured average (A) and the measured standard deviation (D) differ from their expected values of EA=0.50 and ED=sqrt(1/12)=0,288675).

[The latter parameters (rA = (A-EA)/DA) and (rD = (D-ED)/DD)) can be interpreted as if A and D were normally distributed, i.e. the probability that rA or rD is higher than 1 or lower than -1 is about 0,32; higher than 2 or lower than -2: about 0,045 and higher than 3 or lower than -3: about 0,0026 - in a single observation. (Obviously in the table below - because of the fact that 32 variables are tested - probability that one of them will be "suspiciously unlikely" is growing. E.g. an event occurring with probability 0,02 in a single observation has a chance close to 0,5 to occur in a set of 32 observations]

Test No. of
P-values
Average
(A)
Std. Dev.
(D)
Std. Dev.
of A (DA)
Std. Dev.
of D (DD)
rA=
(A-EA)/DA
rD=
(D-ED)/DD
Frequency 50 0,5229 0,3009 0,0408 0,01830,56 0,67
Frequency within a Block 50 0,5351 0,3098 0,0408 0,01830,86 1,16
Runs 50 0,4408 0,2988 0,0408 0,0183-1,45 0,55
Longest Run of Ones 50 0,4731 0,2758 0,0408 0,0183-0,66 -0,70
Binary Matrix Rank 50 0,5266 0,2940 0,0408 0,01830,65 0,29
Discrete Fourier Transform 50 0,4603 0,2737 0,0408 0,0183-0,97 -0,82
Non-Overlapping Templates 7400 0,4994 0,2905 0,0033 0,0015-0,18 1,23
Overlapping Templates 50 0,5180 0,3055 0,0408 0,01830,44 0,92
Maurer's Universal 50 0,5336 0,2869 0,0408 0,01830,82 -0,10
Lempel-Ziv 50 0,5099 0,2952 0,0408 0,01830,24 0,36
Linear Complexity 50 0,4762 0,3071 0,0408 0,0183-0,58 1,01
Serial 100 0,4654 0,2952 0,0288 0,0130-1,20 0,51
Approximate Entropy 50 0,5256 0,2821 0,0408 0,01830,63 -0,36
Cumulative Sums 100 0,4983 0,2949 0,0288 0,0130-0,06 0,48
Random Excursions 400 0,5109 0,2871 0,0144 0,00640,76 -0,25
Random Excursions Variant 900 0,4951 0,2889 0,0096 0,0043-0,51 0,04

None of the measured relative deviations rA and rD showed an unexpectedly high value, which indicates that the performed statistical tests found no bias in the output generated by the VMPC Stream Cipher.


by Bartosz Zoltak




Copyright © 1999-2016 Bartosz Zoltak
Supported by OHTON EXPO Okna Wroc³aw