Geodesic
Experimental study of NIST Statistical Test Suite ability to detect long repetitions in binary sequences
Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 137-145 
A. M. Zubkov; A. A. Serov. Experimental study of NIST Statistical Test Suite ability to detect long repetitions in binary sequences. Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 137-145. http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a8/
@article{MVK_2023_14_2_a8,
     author = {A. M. Zubkov and A. A. Serov},
     title = {Experimental study of {NIST} {Statistical} {Test} {Suite} ability to detect long repetitions in binary sequences},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {137--145},
     year = {2023},
     volume = {14},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a8/}
}
TY  - JOUR
AU  - A. M. Zubkov
AU  - A. A. Serov
TI  - Experimental study of NIST Statistical Test Suite ability to detect long repetitions in binary sequences
JO  - Matematičeskie voprosy kriptografii
PY  - 2023
SP  - 137
EP  - 145
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a8/
LA  - en
ID  - MVK_2023_14_2_a8
ER  - 
%0 Journal Article
%A A. M. Zubkov
%A A. A. Serov
%T Experimental study of NIST Statistical Test Suite ability to detect long repetitions in binary sequences
%J Matematičeskie voprosy kriptografii
%D 2023
%P 137-145
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a8/
%G en
%F MVK_2023_14_2_a8

Voir la notice de l'article provenant de la source Math-Net.Ru

We present and discuss the results of empirical testing the ability of the NIST Statistical Test Suite to detect very long repetitions in binary sequences. We construct the set of deterministic binary sequences that are not rejected by the NIST Suite and corrupt all of them in a deterministic way. To corrupt a binary sequence we choose several its substrings of fixed length and insert in this sequence the copy of each substring. The length of substrings was chosen to be significantly larger than the typical length of the longest repeated substring. If the number of repeated substrings in the corrupted sequence is moderate then the NIST Suite does not reject such nonrandom binary sequences with an obvious cryptographic weakness. We describe the algorithm realizing the search for the longest repetition of substrings in a binary sequence of length $n$. This algorithm is based on the suffix tree and its time and space complexities are of the order $O(n)$.

[1] Zubkov A. M., Mikhailov V. G., “Limit distributions of random variables associated with long duplications in a sequence of independent trials”, Theory Probab. Appl., 19:1 (1974), 172–179 | DOI | MR | Zbl

[2] Ukkonen E., “On-line construction of suffix trees”, Algorithmica, 14 (1995), 249–260 | DOI | MR | Zbl

[3] Rukhin A., Soto J., Nechvatal J., Smid M., Barker E., Leigh S., Levenson M., Vangel M., Banks D., Heckert A., Dray J., Vo S., A statistical test suite for the validation of random number generators and pseudo random number generators for cryptographic applications, NIST Special Publication 800-22 Revision 1a, eds. L. E. Bassham III, NIST, 27 April 2010

[4] L'Ecuyer P., Simard R., TestU01, Dept. d'Inform. Rech. Oper. Univ. Montreal, 2013, 214 pp. http://simul.iro.umontreal.ca/testu01/guideshorttestu01.pdf | MR

[5] Zubkov A. M., Serov A. A., “Testing the NIST Statistical Test Suite on artificial pseudorandom sequences”, Matematicheskie Voprosy Kriptografii, 10:2 (2019), 89–96 | DOI | MR | Zbl

[6] Zubkov A. M., Serov A. A., “A natural approach to the experimental study of dependence between statistical tests”, Matematicheskie Voprosy Kriptografii, 12:1 (2021), 131–142 | DOI | MR | Zbl