Scientific article. : Marsaglia, G.; Zaman, A. Monkey Tests for Random Number Generators , Computers & Mathematics with Applications , 26(9), 1–10, 1993. DOI: 10.1016/0898-1221(93)90002-L.
This paper examines a family of statistical “monkey” tests proposed by J. Marsaglia and A. Zaman for identifying dependencies in sequences that superficially resemble independent uniform symbols. The central idea is to analyze the number of missing overlapping words of fixed length in a long string of symbols. It is shown that such tests are effective for detecting flaws in general-purpose linear and recurrent generators; however, passing a test does not prove cryptographic security. Based on this, a connection with cryptanalysis is formulated: a statistical anomaly serves as an indicator of structural predictability and prompts for state analysis, linear complexity, parameter recovery, and initialization errors.
Keywords: PRNG, CSPRNG, monkey test, OPSO, OQSO, DNA test, overlapping words, Poisson approximation, lattice structure, linear congruential generator, cryptanalysis.
1. Introduction
In Marsaglia and Zaman’s paper, the “monkey” is a model of a source that independently and equally probable presses the keys of the alphabet. If the generator truly imitates such a model on the chosen projection of its bits, then the distribution of words and the number of words not found in the recording obey predictable probabilistic patterns.
This formulation is important because checking the frequencies of individual bits reveals almost nothing about the relationships between adjacent and overlapping fragments. A generator might produce exactly 50% zeros and ones, have an acceptable histogram, but still leave systematic “holes” among words of length t ; these are precisely the holes that monkey tests look for.
2. Model and statistics
2.1 Words and cell occupancy
Let the alphabet be of size a , and let the sequence S_1,...,S_n form all overlapping words of length t :
W_i = (S_i, S_{i+1}, ..., S_{i+t-1}), 1 <= i <= n-t+1.
The word space contains m = a^t cells. For each cell, w a missingness indicator is introduced I_w = 1{w не встретилось}, and the basic statistics are:
M = sum_{w in A^t} I_w.
Given an idealized independent source, the probability of a particular word being missing is approximately:
P(I_w = 1) ≈ (1 - 1/m)^N ≈ exp(-N/m), N = n-t+1,
and, therefore, the mathematical expectation has the form:
E[M] ≈ m exp(-N/m).
The overlapping of words makes the indicators dependent; therefore, the naive binomial model is insufficient. In practical testing, derived or empirically calibrated mean and variance are used, after which the statistics are standardized:
Z = (M - mu_M) / sigma_M.
A large absolute value Z, or extreme value p-value, means that the observed row is incompatible with the null hypothesis of the selected model.
2.2 What is actually being tested
| Level | Object of verification | What can it reveal? | What it doesn’t prove |
|---|---|---|---|
| One-dimensional | Symbol frequencies | Offset, poor scaling | Independence |
| Serial | Pairs and short words | Local correlations, cycles | Unpredictability of the state |
| Monkey / occupancy | Many overlapping words | Pattern gaps, multi-point dependencies | Cryptographic strength |
| Cryptanalysis | Internal state, key, seed | Recoverability and forecast of future outputs | The statistical battery itself |
3. Monkey test categories
3.1. CAT test: didactic starting point
The simplest metaphor is to count how many times a random “typewriter” will print a given word, for example CAT, . For a word of length t in an alphabet of size a, the probability of its appearance in a fixed position is a^{-t}. This test explains the idea, but is weak for serious diagnostics: it looks at a single pattern and has low power against many alternatives.
Historical and practical context. Early software generators were often evaluated using frequency tests and small, serial checks. The development of Marsaglia’s DIEHARD batteries was a response to the fact that well-known generators passed simple tests but failed with more targeted statistics.
3.2 Overlapping Word Tests
The main category in the work is counting missing words when the window shifts by one character. Overlap is critical: words S_i...S_{i+t-1} and S_{i+1}...S_{i+t} divide t-1 characters. This creates sensitivity to the transition structure, which is not visible when splitting the stream into disjoint blocks.
| Name | Alphabet | Word | Interpretation |
|---|---|---|---|
| OPSO | 2^10 = 1024 characters | A couple of symbols | Overlapping-Pairs-Sparse-Occupancy; finding missing pairs |
| OQSO | 2^5 = 32 characters | Four symbols | Overlapping-Quadruples-Sparse-Occupancy; longer context |
| DNA | 4 characters: A, C, G, T | 10-character word | DNA Allegory: Testing the Richness of Long Overlapping Patterns |
In the DIEHARD-like implementation described in subsequent literature, OPSO, OQSO, and DNA generate a 2^21 character-length string and analyze pairs, quadruples, and ten-character words, respectively; the expected load is chosen to be around N/a^t ≈ 2. This ratio makes the number of empty cells particularly informative.
3.3. Sparse Employment
A full array of counters for all words can be expensive. The sparse occupancy approach stores only the “word has already appeared” feature; the final statistic is the number of unobserved cells. This saves memory and specifically measures the coverage geometry of the pattern space, not just the average frequency.
# Pseudocode: Counting Missing Overlapping T-Words
seen = bitset(a**t)
word = encode(S[0:t], a)
seen[word] = 1
for i in range(1, n - t + 1):
word = roll(word, S[i-1], S[i+t-1], a, t)
seen[word] = 1
M = a**t - popcount(seen)
A cryptanalytic example. If a weak nonce generator in an ECDSA signature has a short period, small state, or linear recursion, its low-order bit stream may not cover all expected t -grams. The monkey test doesn’t extract the private key directly, but the detected anomaly justifies switching to an attack on the nonce generator model, replay checking, and partial leakage analysis.
4. Linear and recurrent generators
4.1 Linear Congruential Generator
The classical LCG is defined by recursion:
X_{n+1} = (a X_n + c) mod m, U_n = X_n / m.
With suitable parameters, the period can be large for a given modulus, but the successive vectors (U_n,...,U_{n+d-1}) have an algebraic structure. For linear congruent schemes, the points in the multidimensional unit cube lie on a limited number of parallel hyperplanes—this is the essence of the spectral problem and the reason why good one-dimensional uniformity does not equate to a high-quality multidimensional distribution.
An archival example. The RANDU generator used on IBM systems utilized recursion X_{n+1}=65539 X_n mod 2^31. Its triplets of consecutive values form 15 planes—a classic example of how linear recurrence and poor parameters distort modeling.
4.2. Lag recursions and modulo 2^w operations
Lagged generators—for example, additive or lagged Fibonacci—are defined by relations of the form:
X_n = (X_{nr} + X_{ns}) mod 2^w, r > s.
They can exhibit acceptable simple performance, but linear relationships between outputs emerge when benchmarks consider words, bits, and multiple coordinates. Marsaglia and Zaman’s work emphasizes that using modulo odd multiplication 2^32 can significantly improve some variants of lagged-Fibonacci generators in monkey and other benchmarks, but improving the statistical profile does not transform the circuit into a CSPRNG.
4.3. Lattice diagnosis
Formally, the set of sequential vectors of a linear recurrent generator forms the intersection of a lattice with a hypercube [0,1)^d. The spectral test evaluates the distance between the hyperplanes covering these points: the larger it is, the coarser the structure is visible. Monkey tests work differently—using a discrete coverage of the word space—but both methods capture the same phenomenon: deterministic algebra can leave observable forbidden or rare configurations.
5. Connection with cryptanalysis
5.1 A statistical defect and an attack are not the same thing
Cryptographic security requires computational indistinguishability from a random source for an effective adversary unaware of the internal state. A monkey test is an empirical discriminator on a finite sample: it can show that a particular stream is inconsistent with the IID model, but it provides neither an estimate of the prediction difficulty nor a secret recovery algorithm.
Nevertheless, a negative result is extremely important from an engineering perspective: if publicly observable outputs have a statistically distinguishable structure, this often indicates a small state, linearity, poor entropy extraction, a duplicate seed, or an integration error. For cryptosystems, this is not a “minor quality defect,” but a signal of a risk of key material compromise.
5.2. Real cryptanalytic stories
| Plot | Fact and mechanism | Attitude towards monkey tests |
|---|---|---|
| Debian OpenSSL, 2006–2008 | A bug in an OpenSSL patch reduced the key generator’s state space to a practically enumerable range, leaving the generated keys and associated cryptographic operations vulnerable. | A word coverage test might detect a gross lack of diversity in some output projections, but code audit and entropy analysis establish the root cause. |
| Android Bitcoin, 2013 | Insufficiently predictable ECDSA nonces in some Android implementations allowed private keys to be extracted from signatures; repeating or predicting nonces undermines ECDSA security. | Statistical testing of the nonce stream is a useful monitoring tool, but the decisive check is the uniqueness of the nonce and a cryptographically secure source. |
| Dual_EC_DRBG | A known-point construction may have an implied backdoor: knowledge of the discrete-logarithmic relationship between the parameters helps predict the state from the reduced output. | Even passing statistical tests does not eliminate trapdoors; monkey tests are not a substitute for design analysis and parameter confidence. |
5.3. ECDSA as a critical illustration
For ECDSA, the signature over the hashed message z uses a secret nonce k:
r = (kG)_x mod q,
s = k^{-1}(z + rd) mod q,
where d is the private key, q is the group order. If the same key k is repeated for two messages, then for s_1 != s_2:
k = (z_1 - z_2)(s_1 - s_2)^{-1} mod q,
d = (s_1 k - z_1) r^{-1} mod q.
This demonstrates a qualitative limitation: monkey test might notice an atypical structure in the nonce array, but nonce repetition should be checked directly against the component r, and key compromise is deduced algebraically from signatures. In production, only standardized CSPRNGs or deterministic nonce generation according to RFC 6979, if implemented correctly, are acceptable.
6. Practical assessment methodology
- Identify the threat. Separate the simulated PRNG and the source for keys, nonces, tokens, reset links, and salts.
- Collect representative outputs. Test various seeds, process runs, platforms, reseed branches, and all published output transformations.
- Check projections. Analyze high/low bits, bytes, words, and decoded values; weaknesses are often localized to individual bits.
- Run monkey tests. Calculate occupancy statistics for several alphabets and word lengths, and use the correct calibration
p-value. - Supplement with batteries. Use modern test kits, such as TestU01, and specific linearity/rank tests.
- Conduct a cryptographic audit. Investigate state size, reversibility, linearity, seed, entropy, fork safety, API, and possible nonce reuse.
Engineering rule: Do not use LCG, Mersenne Twister, xorshift, or lag generators for secrets, keys, ECDSA/DSA nonces, session identifiers, or cryptographic salts. For these purposes, choose the OS’s system CSPRNG or a trusted cryptographic library; the statistical battery serves as a check, not a security certificate.
7. Limitations of interpretation
Multiple tests inevitably sometimes yield small results p-value even for an ideal source. Therefore, a decision cannot be based on a single failure: reproducibility, analysis of a series of independent runs, consideration of multiple testing, and a technical explanation for the anomaly are required. Likewise, a set of “good” p-values does not prove the absence of predictability.
It’s especially important to distinguish the output transformer from the entropy source. Nonlinear scrambling can hide some linear statistical defects without fixing the compromised seed; conversely, a high-quality source can be corrupted by improper truncation, state reuse, or an unsafe API.
8. Final Provisions
Marsaglia and Zaman’s monkey tests are valuable because they replace the vague “looks random” with a concrete test: how completely a stream covers the space of overlapping words. This is a powerful method for diagnosing multi-point dependencies and a useful bridge between statistical testing and the structural analysis of recurrent generators.
For a cryptanalyst, the test result should be interpreted as a benchmark. Failure prioritizes the search for linear recursions, short periods, weak initialization, and nonce repetitions; passing does not rule out predictability, backdoors, or entropy management flaws. Security arises from the CSPRNG design, a correct seed, and provably secure exploitation, not from a single statistical battery.
Literature
Monkey Tests for Random Number Generators: Statistical Diagnostics and Cryptanalytic Implications: https://nordai.ru/monkey-tests-for-random-number-generators-statistical-diagnostics-and-cryptanalytic-implications/
- Marsaglia, G., Zaman, A. Monkey Tests for Random Number Generators. Computers & Mathematics with Applications . 1993;26(9):1–10. DOI: 10.1016/0898-1221(93)90002-L.
- L’Ecuyer, P., Simard, R. TestU01: AC Library for Empirical Testing of Random Number Generators. ACM Transactions on Mathematical Software . 2007;33(4).
- Eastlake, D., Hansen, T. RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). IETF, 2013.
- NIST. SP 800-90A Rev. 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. 2015.
- Heninger, N. et al. Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. USENIX Security , 2012.
- Bernstein, DJ et al. On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng. 2016.