CoChat
Sign Up
Cited by 5Cryptographic Implementations and SecurityCoding theory and cryptographyProbability and Statistical Research

New statistical randomness tests: 4-bit template matching tests

Open access
SULAK, Fatih·2017·TURKISH JOURNAL OF MATHEMATICS
DOI 10.3906/mat-1509-19
Open this paper in CoChat — free accountOpen PDF

Abstract

For cryptographic algorithms, secret keys should be generated randomly as the security of the system depends on the key and therefore generation of random sequences is vital. Randomness testing is done by means of statistical randomness tests. In this work, we show that the probabilities for the overlapping template matching test in the NIST test suite are only valid for a specific template and need to be recalculated for the other templates. We calculate the exact distribution for all 4-bit templates and propose new randomness tests, namely template matching tests. The new tests can be applied to any sequence of minimum length 5504 whereas the overlapping template matching test in the NIST test suite can only be applied to sequences of minimum length $10^6$. Moreover, we apply the proposed tests to biased nonrandom data and observe that the new tests detect the nonrandom behavior of the generator even for a bias of $0.001$, whereas the template matching tests in NIST cannot detect that bias.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper recalculates exact distributions for all 4-bit templates in overlapping template matching and proposes four new randomness tests based on the number of overlapping bits. The new tests work on sequences as short as 5504 bits and detect biased nonrandom data at a bias of 0.001 where the NIST template matching tests do not.

Key findings

  • The probabilities used in NIST’s overlapping template matching test are valid only for the specific template \(B = 111111111\); the distribution depends on the number of overlapping bits in the template. The paper classifies all 16 4-bit templates into 0-, 1-, 2-, and 3-bit-overlapping groups and derives exact distributions for each.
  • The proposed 4-bit template matching tests can be applied to sequences of minimum length 5504 bits, whereas NIST’s overlapping template matching test requires sequences of minimum length \(10^6\).
  • The tests were applied to binary expansions of \(e\), \(\pi\), \(\sqrt{2}\), and \(\sqrt{3}\) using approximately \(10^6\) bits, and to four PRNGs (Mersenne Twister, C# Random, RNGCryptoServiceProvider, and AES) using \(2^{24}\) bits; these sequences passed all tests.
  • On biased nonrandom data of length \(2^{24}\) with \(Pr(a_i = 1) = 1/2 + q\), three instances of the new tests detected nonrandom behavior even for \(q = 0.001\), whereas the template matching tests in NIST could not detect that bias.

Methods

  • Exact probability distributions for 4-bit templates were derived combinatorially by classifying templates according to their number of overlapping bits, assuming circular bits within each subsequence, and summing over possible weights and run counts.
  • The test procedure chooses a 4-bit template \(B\), divides the sequence into \(M = \lfloor n/128 \rfloor\) 128-bit blocks, appends the first 3 bits to each block, counts overlapping occurrences of \(B\), assigns counts to 5 bins using the paper’s Table 2 probabilities, and applies a \(\chi^2\) goodness-of-fit test; the null hypothesis is rejected if the p-value is \(< 0.01\).
  • Simulations compared the new tests with the NIST test suite on binary expansions, PRNG outputs, and biased nonrandom data, using specified NIST parameters for the comparison tests.

Limitations

  • Stated: future work includes obtaining exact distributions for all 5-bit templates and calculating probabilities for other overlapping templates in NIST’s overlapping template matching test.
  • Evident from the text: the proposed tests are limited to 4-bit templates, and the simulation evaluates one representative template per overlap class (0001, 0010, 0101, 1111) rather than all 16 templates.
  • Evident from the text: the power evaluation uses only an i.i.d. bit-bias model, so detection of other forms of nonrandomness is not assessed.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.3906/mat-1509-19

Cites

21 of 23 references verified0 citation errors · 2 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

0 of 15 cited sources checked · 0 supported · 0 flagged

  • Findingreasoning

    The frequency distribution of a chosen 4-bit template is determined solely by how many bits overlap within that template.

    “Proposition 3.1 The distribution of the frequency of a prespecified template depends only on the number of overlapping bits in the template.”
    • Also stated in: § Proposition 3.1 The distribution of the frequency of a prespecified template depends only on the number of overlapping bits in the template. · boosted
      “This shows that the distribution depends only on the number of overlapping bits in the block.”
    Quote in the paperSubstantial claim
  • Findingreasoning

    For a circular binary sequence of length n that is not constant, the unconditional probability of exactly k occurrences of 0001 is obtained by summing the conditional probability over all weights and run counts, as in Corollary 3.8.

    “Let {a 1 , a 2 , . . ., a n } be a binary sequence and b i = a i a i+1 a i+2 a i+3 be blocks of length 4 for 1 ≤ i ≤ n with a n+j = a j for j = 1, 2, 3 , and let K denote the number of 0001 blocks among b i for 1 ≤ i ≤ n .If the sequence is not all zero or all one then”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The bits in each subsequence are treated as circular.
    • The authors state this as an assumption: When k=0, the combinatorial equation has only one solution, and this convention is used throughout the paper.
  • Findingown data

    The NIST overlapping template matching test's probabilities hold only for one particular template and require recomputation for other templates.

    “In this work, we show that the probabilities for the overlapping template matching test in the NIST test suite are only valid for a specific template and need to be recalculated for the other templates.”
    • Also stated in: § 1. Introduction · plain
      “We observe that the probabilities are not the same for each overlapping template, which shows that the probabilities for overlapping template matching test in the NIST are valid only for B = 111111111 .”
    Quote in the paperSubstantial claim
  • Findingreasoning

    For a binary sequence that is not all zeros or all ones, conditional on its weight w and its number of runs 2r, the probability that the number K of 1111 blocks among overlapping length-4 blocks equals k is given by the stated inclusion-exclusion formula.

    “P r(K = k) = n r • 2 n ( n -w -1 r -1 ) r ∑ t=0 ( r t )( k -1 t -1 ) • r ∑ i=0 ( w -k -3t -3i -1 r -t -1 )( r -t i ) (-1) i .”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: In the proof of Theorem 3.13, the bits can be arranged on a circle and ones and zeros written consecutively to define 2r runs.
    • The authors state this as an assumption: In the proof of Theorem 3.13, without loss of generality, t of the one-runs have length at least 3 and the remaining one-runs have length between 0 and 2.
  • Findingreasoning

    A circular arrangement produces n linear sequences, but the r occurrences of the 01 block make r of them duplicates.

    “Moreover, each arrangement on the circle gives n sequences.However, since there are r many 01 blocks, r of these sequences are identical.”
    Quote in the paperSubstantial claim
  • The quote only partly states this claim. 5
  • May combine two claims. 9
  • Classified as probably not a substantial claim. 6

  • The quote only partly states this claim.

    Findingreasoning

    For a circular binary sequence of length n that is not constant, the conditional probability that exactly k occurrences of 1010 appear, given weight w and 2r runs, is the combinatorial expression in Theorem 3.11.

    “Let {a 1 , a 2 , . . ., a n } be a binary sequence and b i = a i a i+1 a i+2 a i+3 be blocks of length 4 for 1 ≤ i ≤ n with a n+j = a j for j = 1, 2, 3 , and let K denote the number of 1010 blocks among b i for 1 ≤ i ≤ n .”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The bits in each subsequence are treated as circular.
    • The authors state this as an assumption: The two-bit-overlapping case can be modeled as r red-white box pairs with balls distributed into white and red boxes, and K=k corresponds to exactly k empty pairs.

  • The quote only partly states this claim.

    Findingreasoning

    For a circular binary sequence of length n that is not constant, the conditional probability that exactly k occurrences of 0110 appear, given weight w and 2r runs, is the combinatorial expression in Theorem 3.9.

    “Let {a 1 , a 2 , . . ., a n } be a binary sequence and b i = a i a i+1 a i+2 a i+3 be blocks of length 4 for 1 ≤ i ≤ n with a n+j = a j for j = 1, 2, 3 , and let K denote the number of 0110 blocks among b i for 1 ≤ i ≤ n .”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The bits in each subsequence are treated as circular.
    • The authors state this as an assumption: When k=0, the combinatorial equation has only one solution, and this convention is used throughout the paper.

  • The quote only partly states this claim.

    Findingreasoning

    For a circular binary sequence of length n that is not constant, the conditional probability that exactly k occurrences of 0001 appear, given weight w and 2r runs, is the combinatorial expression in Theorem 3.6.

    “Let {a 1 , a 2 , . . ., a n } be a binary sequence and b i = a i a i+1 a i+2 a i+3 be blocks of length 4 for 1 ≤ i ≤ n with a n+j = a j for j = 1, 2, 3 , and let K denote the number of 0001 blocks among b i for 1 ≤ i ≤ n .”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: The bits in each subsequence are treated as circular.
    • The authors state this as an assumption: When k=0, the combinatorial equation has only one solution, and this convention is used throughout the paper.

  • May combine two claims.

    Findingown data

    The proposed tests detect nonrandomness in a generator with bias 0.001, while the NIST template matching tests do not.

    “Moreover, we apply the proposed tests to biased nonrandom data and observe that the new tests detect the nonrandom behavior of the generator even for a bias of 0.001 , whereas the template matching tests in NIST cannot detect that bias.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    The binary expansions of e, pi, sqrt(2), and sqrt(3), each about 10^6 bits, are random according to all applied randomness tests.

    “These four sequences are random according to all tests.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. The quote only partly states this claim.

    Findingown data

    The tested PRNGs-Mersenne Twister, C# Random, C# RNGCryptoServiceProvider, and AES-pass all applied statistical randomness tests.

    “Similar to the previous experiment, both generators pass all the statistical randomness tests.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [16]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [3]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims. The quote only partly states this claim.

    Interpretationreasoning

    The 4-bit templates divide into four classes by overlap count: none, one, two, and three overlapping bits, with the listed members in each class.

    “Using this proposition, we classify the 4-bit templates according to their number of overlapping bits.There 4 types of blocks:”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationnone given

    For the new 4-bit template matching tests, the subsequence length can be changed by recalculating the bin probabilities for that new length.

    “Furthermore, for the new tests, it is also possible to change the subsequence length by calculating the bin probabilities for the new subsequence length.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation

    Hamano et al. corrected the overlapping template matching probabilities for template B=111111111, and NIST updated them.

    “Hamano et al. corrected the probabilities for the overlapping template matching test, where they took the template as B = 111111111 [9] and NIST updated the probabilities accordingly.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [9]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation

    Goldberg and Wagner showed that Netscape SSL key-generation random numbers were based on processor time and predictable, revealing a major protocol weakness.

    “In 1996, Goldberg and Wagner [8] showed that the “random numbers” used to generate the keys in the Netscape SSL protocol were based on the time of the processor and therefore predictable, which helped them to find a major weakness in the protocol.”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [8]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Interpretationreasoning

    The NIST overlapping template matching test requires sequences of at least 10^6 bits, whereas the new 4-bit tests work for sequences longer than 5504 bits.

    “Moreover, NIST's overlapping template matching test can only be applied to long sequences, i.e. sequences of minimum length 10 6 , whereas the new proposed tests can be applied to any sequence whose length is greater than 5504.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [21]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given

    The inclusion-exclusion method used for the 4-bit template 1111 can be generalized to m = 9 and template B = 111111111.

    “We can still apply the inclusion-exclusion principle if we choose m = 9 and B = 111111111.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductreasoning

    The bin probabilities in Table 2 are computed from Corollaries 3.8, 3.10, 3.12, and 3.14.

    “The probabilities in Table 2 are evaluated using Corollaries 3.8, 3.10, 3.12, and 3.14.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data

    NIST's overlapping template matching test uses probabilities that hold only for the template B = 111111111; other overlapping blocks require recalculated probabilities.

    “In this work, we classify all templates according to their number of overlapping bits and show that the probabilities used in NIST's overlapping template matching test are valid only for B = 111111111 and should be recalculated for different overlapping blocks.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [21]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Premisecitation

    Okutomi et al. found that Maurer's universal test and the overlapping template matching test had problems with the proportion of random data passing.

    “Okutomi et al. applied the tests in the NIST test suite to the random data taken from the cryptographic algorithms DES and SHA-1 [19].They observed that Maurer's universal statistical test and the overlapping template matching test have problems with the ratio of the random data that pass the tests.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [19]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Classified as probably not a substantial claim.

    Premisecitation

    The NIST overlapping template matching test requires sequences of at least 10^6 bits.

    “Some tests in the suite require sequences of length 10 6”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [21]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Premisecitation

    Sulak et al. used exact distributions instead of approximations, which reduced the need for long sequences and allowed tests directly on algorithm outputs rather than concatenated outputs.

    “Recently, Sulak et al. proposed an alternative method where they computed and used the exact distributions instead of approximations or asymptotic distributions [24].Having these exact probabilities, the necessity of long sequences was reduced, and they applied the randomness tests directly to the outputs of the algorithms instead of concatenating them.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [24]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

17 of 17

  • The authors state this as an assumption.

    The bits in each subsequence are treated as circular.

    “Different from the previous approaches, we assume that the bits are circular in each subsequence.”

  • The authors state this as an assumption.

    When k=0, the combinatorial equation has only one solution, and this convention is used throughout the paper.

    “Note that if k = 0 , we cannot apply Lemma 3.4, and in that case we assume there is only one solution.We use this assumption throughout the paper.”

  • The authors state this as an assumption.

    The two-bit-overlapping case can be modeled as r red-white box pairs with balls distributed into white and red boxes, and K=k corresponds to exactly k empty pairs.

    “Assume that there are r red-white box pairs and we distribute w -r balls into white boxes and n -w -r balls into red boxes.P r(K = k) is the probability that exactly k pairs are empty.”

  • The authors state this as an assumption.

    In the combinatorial derivation, the empty boxes among the red boxes can be assumed to be the first a boxes without loss of generality.

    “Assume that the empty boxes are the first a boxes (with a factor of ( r a ) ).”

  • The authors state this as an assumption.

    In the same derivation, the empty boxes among the first a white boxes can be assumed to be the first k boxes without loss of generality.

    “Assume that the empty boxes are the first k boxes (with a factor of ( a k ) ).”

  • The authors state this as an assumption.

    In the proof of Theorem 3.13, the bits can be arranged on a circle and ones and zeros written consecutively to define 2r runs.

    “we assume the bits are arranged on a circle and we write 'one's and 'zero's consecutively to define 2r runs.”

  • The authors state this as an assumption.

    In the proof of Theorem 3.13, without loss of generality, t of the one-runs have length at least 3 and the remaining one-runs have length between 0 and 2.

    “Without loss of generality (or multiplying by ( r t ) ), assume y j ≥ 3 for 1 ≤ j ≤ t, and 0 ≤ y s ≤ 2 for t + 1 ≤ s ≤ r .”
7 of 7

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Four generators are later called two

    Minor

    The simulation section says it tests four PRNGs and lists four data sources, but then refers to both PRNGs and both generators.

1 of 1

Cites

Flagged first, then by citations

Research works printed but not linked: 4

  1. Doganaksoy A, C ¸alık C ¸, Sulak F, Turan MS. New randomness tests using random walk. In: 2nd National Conference Proceedings; 15-17 December 2006; Ankara, Turkey.
  2. Doganaksoy A, Tezcan C. An alternative approach to Maurer's universal statistical test. In: Information Security and Cryptology Conference ISC Turkey 2006 3rd International Conference Proceedings; 25-27 December 2008; Ankara, Turkey. pp. 187-189.
  3. Goldberg I, Wagner D. Randomness and the Netscape browser. Dr Dobb's Journal-Software Tools for the Profes- sional Programmer 1996; 21: 66-70.
  4. Okutomi H, Kaneda M, Yamaguchi K, Nakamuro K. A study on the randomness evaluation method using NIST randomness test. In: Symposium on Cryptography and Information Security -International Conference Proceedings; 2006.

Cited by

Sorted by citations

Related

Authors
SULAK, F.
Affiliations
Atilim University (TR)
Corresponding author
SULAK, Fatih
Venue
TURKISH JOURNAL OF MATHEMATICS
Publisher
The Scientific and Technological Research Council of Turkey (TUBITAK-ULAKBIM) - DIGITAL COMMONS JOURNALS
Published
2017
Volume
41
Pages
80-95
ISSN
  • 1300-0098 (ISSN-L)
  • 1303-6149
DOI
10.3906/mat-1509-19
OpenAlex
W2571912741
Semantic Scholar
3b5853baff516a285bf8786095942237c7a1830b
Cited by
5
References
20
Citations by year
2025: 1 · 2024: 1 · 2023: 1 · 2020: 1 · 2019: 1
FWCI
0.33
Type
journal article
Language
en
Open access
Locations
  • TURKISH JOURNAL OF MATHEMATICS (publishedVersion)
  • DergiPark (Istanbul University) (submittedVersion)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Cryptographic Implementations and Security
  • Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
  • Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
Keywords
randomness testing, exact distribution, random number generation, cryptographic key generation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-09.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-09.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review