Tests Cannot See Prediction

Three generators pass statistical tests. Then an attacker who has seen enough output predicts everything that comes next.

RandomnessPseudorandom generatorsStatistical testingdemo

Objectives

Run a distribution battery over a stream and read what each test actually measures.
Explain why a uniform byte histogram is not evidence of unpredictability.
Predict a counter stream from the key alone, and an LCG stream from one observed value.
Reverse the Mersenne Twister tempering on one output word and say why no search is involved.
State how many outputs recover the Twister state, and what the attacker holds afterwards.

20%

One generator, tested and then continued by somebody who never saw it.

Pick a generator. Each one is in real software. The page runs a distribution battery over 131,072 bytes of its output, the kind of test NIST SP 800-22 is made of.

Block i is the hash of one fixed key and the number i. This is what AES in counter mode does, with a hash standing in for the cipher.

The head of the stream

The first values the selected generator produces.
#	value
0	block 0 36d816e3453dbab2e031145ad1178895...
1	block 1 6098ce4b12e425f0d4aee4173bb26b7d...
2	block 2 8cdf2625dd374114dae77f0fe5288170...

What the battery says

Four distribution tests over 131,072 bytes from the selected generator.
test	result	compared against	verdict
Byte histogram (chi-square)	213.8	against 310.5, the 1% point at 255 degrees of freedom	pass
Counts per byte value	469 to 583	expected 512 each	pass
Entropy per byte	7.9988	out of a maximum of 8	pass
Monobit (share of one bits)	0.5002	expected 0.5000	pass

4 of 4 passed. Every one of these tests looks at how often each value appears and at nothing else.

The byte histogram, all 256 values

One bar per byte value, 0x00 to 0xFF. A flat row is what uniform means, and it is all the battery measured.

A statistical test asks how often each value appears. It never asks who can name the next one. Only the second is a security requirement.

What the attacker is given: Counter under a fixed key

observed

nothing at all

The attacker sees nothing at all and nothing else.

method

Hold the key and compute block i directly, for any i.

The next five values, predicted

Before pressing it: the battery above accepted this stream. Decide what you expect to happen.

Nothing there was a search. Each prediction is the generator's own arithmetic, started from what the attacker was allowed to see.

None of these generators is broken as a simulation tool. They were never built to resist an attacker, and the tests that pass them cannot tell you whether anything was.

step 1/5

CPE 645 / CS 685

Tests Cannot See Prediction

Entropy Calculator

Presentation Order Draw