DSP Explorables

Randomness

Every cipher on this site keeps its secret in a key, and every key starts life as random bits. The one-time pad needs a whole message’s worth of them. Where do they come from, and what does “random” even mean for a key? This page follows that question from guessing games to the generators real systems use, breaking several on the way.

1 · Random means unpredictable

Section titled “1 · Random means unpredictable”

For a key, random has one meaning that matters: the attacker can’t predict it. If a key is chosen evenly from N possibilities, an attacker who knows how it was chosen (and, as Kerckhoffs’s principle says, we should assume they do) has to try them: all N in the worst case, half on average.

So the measure of a key is how many possibilities it was chosen from. Cryptographers count them in bits: N possibilities is log₂ N bits, the number of coin tosses that would make as many choices. A key chosen from 1,024 possibilities has 10 bits; each extra bit doubles the attacker’s work. This count is the key’s entropy.

Ways of choosing a key, with how many keys each could be (as bits, log₂ of the count) and how long trying every one would take at the rate this browser manages, timed when the figure comes into view: trying keys on a toy cipher (a few rounds of multiplying and shifting, the same as on What we want from cryptography), on one core. A real cipher takes longer to try per key, but a determined attacker has thousands of fast processors, so take the times as a feel, and the bits as what counts.

A word from Alice’s first chapter is one of 611, so 9.3 bits: a fraction of a second. Two digits after it add only 6.6 bits more. But four words picked at random from the same chapter make 37.0 bits, nearly as many as 8 random letters (37.6 bits), and far easier to remember. What matters is never how a key looks, only how it was chosen: “rabbit42” is as strong as the method that produced it, and a person choosing “something with a number in” is a method attackers know well. At 128 random bits, the time in the figure stops meaning anything: that’s the size of key modern ciphers use.

2 · A seed and a rule

Section titled “2 · A seed and a rule”

Tossing coins is slow, and computers are machines that do exactly what they’re told, so most “random” numbers in software are pseudo-random: a small state (the seed), and a rule that steps it on and produces a number each time. The simplest rule, used for decades, is the linear congruential generator (LCG): multiply by a constant, add another, and keep the remainder after dividing by 2³²:

x → (1664525 × x + 1013904223) mod 2³²

The numbers it gives look random enough at a glance. Draw them in binary, one number per row, and they don’t:

48 numbers from the LCG above, one per row, each as its 32 bits (bit 31, the most significant, on the left). Look at the right-hand columns: bit 0 simply alternates, bit 1 repeats every 4 numbers, and bit k every 2ᵏ⁺¹ (checked in the tests). Only the top bits look like noise. Switch to the browser’s cryptographic generator for comparison: no column has a pattern.

The low bits fall out of the arithmetic: bit 0 of a·x + c depends only on bit 0 of x (adding and multiplying never carry downwards), so it can only alternate or stay still; bits 0 and 1 together have only 4 states, so they repeat within 4 steps; and so on up. A program that took x mod 2 from this generator as a coin toss would get 0, 1, 0, 1 …

The flaws can be subtler. RANDU was IBM’s generator for its scientific computers in the 1960s, used in countless simulations: x → 65539 × x mod 2³¹. Take its numbers three at a time, as points in a cube:

3,000 points (u, v, w): three consecutive numbers from RANDU, each scaled to 0 … 1. Drag to turn the cube. From most angles they fill it evenly. Look along the planes: every point lies on one of just 15 flat sheets (checked in the tests). The browser’s cryptographic generator, from any angle, fills the cube.

Why 15? The multiplier is 65539 = 2¹⁶ + 3. Stepping twice multiplies by its square:

65539² = 2³² + 6 × 2¹⁶ + 9, which, keeping the remainder after 2³¹, is 6 × 2¹⁶ + 9 = 6 × 65539 − 9

So each number is 6 times the one before, minus 9 times the one before that: x₃ = 6x₂ − 9x₁, give or take a multiple of 2³¹. Scaled to 0 … 1, that means 9u − 6v + w is always a whole number. With u, v and w all between 0 and 1, it’s more than −6 and less than 10: one of the 15 whole numbers from −5 to 9. Each is a plane, and every triple lies on one of them.

Neither flaw is about keys, but they show the general problem: a generator is a short rule, and its output has that rule’s shape. Statistical tests catch some shapes. An attacker looking for one will find more.

3 · Predicting an LFSR

Section titled “3 · Predicting an LFSR”

The linear-feedback shift register on the DSP site is a much better generator by the usual tests: with the right taps its output is balanced, its runs come in coin-toss proportions, and its spectrum is flat. A 32-bit register goes through 4,294,967,295 states before it repeats. So why not encrypt by XORing a message with its output, a “keystream”, as the one-time pad does with truly random bits, and keep the register’s starting state as the key?

Because most messages have a predictable start: a header, a greeting, a file format’s first bytes. An attacker who knows the first few characters can XOR them with the ciphertext and get that much keystream, a known-plaintext attack. And as the DSP page’s last section shows, Berlekamp–Massey finds an n-bit register from 2n of its bits: for 32 bits, 64 bits, 8 characters.

What the attacker captured

What they decrypt (known, wrong)
A message XORed with a 32-bit LFSR’s output (taps x³² + x²² + x² + x + 1, which go through all 2³² − 1 states,
checked in the tests). The attacker knows how the message starts, From: Alice and a new line. They XOR what
they know with the ciphertext to get keystream bits, run Berlekamp–Massey on them, and run the register it finds
on to decrypt the rest. With 8 or more characters known (64 bits) it finds the register and the whole message
reads. Slide down to 7 (56 bits): the register it finds is a shorter, wrong one, and the rest is garbage.


Four billion bits before it repeats, and 64 give it away. A long period is not the same as being unpredictable.


4 · Only as good as its seed
Section titled “4 · Only as good as its seed”


A generator might hide its rule well, and still be no better than its seed. If the seed can be guessed, the
attacker just runs the same generator from each guess. A favourite seed in software is the time, which is
different every run, but hardly secret.


The 128-bit key
A 128-bit key from a generator seeded with the time, in seconds, at a secret moment today. The generator is a
decent one (mulberry32), but whatever it is, its output is decided by its seed, and a day has only 86,400
seconds: 16.4 bits. The attacker tries each one, as they would check a guessed key against a message they’ve
captured; here comparing with the key stands in for that. The time taken is measured in this browser.


That’s a 128-bit key with 16.4 bits of entropy. This exact mistake broke the Netscape browser’s secure
connections in 1995: Ian Goldberg and David Wagner found that it seeded the generator for its secret keys from
the time of day and two process numbers. Those are hardly secrets: the time is known roughly from when the
connection was made, and the process numbers are small and often visible to other programs on the same computer.
Trying the possibilities found the key quickly enough to read the connection.


5 · Generators fit for cryptography
Section titled “5 · Generators fit for cryptography”


What a key generator needs is a much stronger promise than “looks random”: that no feasible computation,
seeing all the bits so far, can predict the next bit better than a coin toss. This is the next-bit test, a
definition from the early 1980s (by Manuel Blum, Silvio Micali and Andrew Yao). Every generator above fails it,
spectacularly:


Three generators against one predictor, which guesses each bit from all the bits before it, two ways: by
spotting a repeat (copying the bit as far back as the shortest period it has seen), and by Berlekamp–Massey (the
shortest LFSR that makes the bits so far, run on one step). It uses whichever has been right more often. The
line is its share right over the last 100 bits. The LCG’s bit 3 repeats every 16; the LFSR is predicted
perfectly once 64 bits have gone by; SHA-256 in counter mode, about half: no better than guessing.


A predictor with two tricks failing proves nothing on its own. The evidence that a cryptographic generator is
good is that many people, with every trick they know, have tried to predict it and failed. The usual way to
build one is from a part that has already had that scrutiny: a hash function or a cipher. The third
generator above takes a secret seed and hashes it along with a counter (seed and 0, seed and 1, …): SHA-256,
designed so that its output can’t be predicted without knowing its input, gives 256 new bits each time.
Real designs add more: they reseed regularly, and they change their state so that someone who steals it can’t
run it backwards to find the keys already made.


The seed still has to come from somewhere unpredictable. The operating system collects it from the physical
world: the exact timings of keystrokes, disk and network interrupts, and on most modern chips a hardware noise
source. It mixes them into a pool and seeds a cryptographic generator from it. In a browser,
crypto.getRandomValues hands out its output; this page’s “new key” buttons use it. (Math.random is a
different thing: fast, statistically fine, and not for keys.)


When these pieces fail, they fail quietly, because bad random numbers look just like good ones:



Summary
Section titled “Summary”



Further reading
Section titled “Further reading”