Experimental study of NIST Statistical Test Suite ability to detect long repetitions in binary sequences

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)$.