Secure randomness is usually taught as a rule: "use the cryptographic random generator, not the ordinary one." Give the definition behind the rule — what makes a generator cryptographically secure, why a generator can pass every statistical randomness test and still be useless for keys and tokens, and what property you are actually buying.
answer
- distribution vs unpredictability
- next-bit test, not chi-squared
- MT19937: 624 outputs recover state
- LCG: two outputs, brute force low bits
- backtracking + prediction resistance
basics
~20 sOrdinary generators are designed for good distribution; cryptographic ones are designed for unpredictability. The question is never whether output looks random, but whether an attacker who has seen past output can predict the next one or recover the internal state. Statistical tests cannot answer that.
solid answer
~60 sEvery pseudo-random generator is deterministic: an internal state, an output step, a state update. **Statistical quality** means the output is uniformly distributed and uncorrelated. **Cryptographic security** is an adversarial property on top of that: the *next-bit test* — given all previous output, no feasible attacker predicts the next bit better than a coin flip — plus **state-compromise resistance**: if the state leaks, past output stays hidden (backtracking resistance) and future output recovers after reseeding (prediction resistance). Ordinary generators fail the first property cheaply. A Mersenne Twister's state is 624 words and its output tempering is invertible, so 624 consecutive outputs reconstruct it exactly. A 48-bit linear congruential generator is solvable from two outputs by brute-forcing the missing bits. The xorshift-family generator behind typical JavaScript `Math.random` falls to a handful of doubles. All of these pass Diehard/TestU01-class batteries. Cryptographic generators are built so that inverting the output step is the hard problem: a block cipher in counter mode, an HMAC or hash chain, or a stream cipher. Same-looking output, categorically different guarantee.
go deeper
Know the two-category answer: ordinary generators are for simulations and shuffles, cryptographic generators for anything an attacker would want to guess — keys, tokens, session ids, salts. Say plainly that looking random is not the same as being unpredictable.
Give the next-bit definition and at least one concrete break: Mersenne Twister's state recovered from 624 outputs, or an LCG solved from two values. Mention that these generators pass standard statistical suites, which is why the defect is invisible in testing.
Add state-compromise resistance (backtracking and prediction) and why it matters after a heap dump or a cloned image; explain that secure generators are cipher/hash constructions whose inversion is the hard problem, and that the choice must be made at the call site because it cannot be verified downstream.
Frame it as a property you cannot test for, therefore one that must be structurally guaranteed: a single vetted randomness facility, non-crypto generators unreachable from security-relevant code, and a review posture that treats "looks random" as no evidence at all.
## The two different questions People say "random" for two unrelated requirements, and almost every weak-randomness bug comes from answering the wrong one. **Question 1 — distribution.** Are the values spread evenly, without visible correlation, so a simulation, a shuffle, a load-balancing decision or a jitter interval behaves fairly? This is a *statistical* question. You answer it with test batteries (Diehard, TestU01, NIST SP 800-22 style suites), and plenty of small, fast, non-cryptographic generators answer it well. **Question 2 — unpredictability.** Given everything an attacker can observe, can they compute what comes next, or what came before? This is a *computational* question about an adversary with time and memory, and no statistical test can settle it. It is the question that matters for keys, session identifiers, password-reset tokens, CSRF tokens, salts, and anything else whose security rests on "nobody can guess this value." A generator that answers question 1 but not question 2 is called a PRNG. One that answers both is a CSPRNG. ## The formal properties A generator is cryptographically secure when it satisfies the **next-bit test**: for any efficient adversary given the first *k* output bits, the probability of correctly predicting bit *k+1* exceeds one half only negligibly. An equivalent formulation is *indistinguishability*: no efficient adversary can tell a stream of generator output from a stream of true random bits. Two further properties matter in practice because real states get stolen (a heap dump, a memory-disclosure bug, a cloned VM image): - **Backtracking resistance** (a.k.a. forward secrecy of output): an attacker who obtains the current state cannot reconstruct *previously* emitted values. Implementations get this by making the state update one-way — hash or encrypt forward and discard the old state. - **Prediction resistance**: an attacker who obtains the state cannot predict output arbitrarily far into the future, because fresh entropy is periodically mixed in (reseeding). Notice what these properties are about: they are all statements about an *attacker's* computational ability, never about how the numbers look. ## Why ordinary generators lose Ordinary generators are chosen for speed, small state, and long period. Their output is a simple, usually invertible function of a small state, so the state can be solved for: - **Linear congruential generators** (the classic 48-bit variety in many standard libraries) update by multiply-add modulo a power of two and return the high bits. Two consecutive values leave only the discarded low bits unknown — a brute force of a few tens of thousands of candidates. - **Mersenne Twister (MT19937)** keeps 624 words of state. The tempering applied to each word is a fixed, invertible bit-mixing step, so 624 consecutive outputs invert directly into the state; from there every future *and* past value follows. - **xorshift / xoroshiro variants**, used for fast scripting-language randomness, have 128 bits of state recoverable from a small number of outputs by solving linear equations over GF(2). Crucially, none of these bugs shows up as *bad-looking* numbers. MT19937 passes almost every standard test suite. That is exactly why "but the tokens look random / no two are the same / we ran a chi-squared test" is not evidence of anything. Also: seeding an ordinary generator from a clock, a process id, or a request counter compounds the problem — the attacker no longer needs to solve for the state, only to enumerate a few million plausible seeds and regenerate your whole token stream offline. ## How secure generators are built They compose a primitive that is already believed hard to invert: - **Counter-mode block cipher** designs (a CTR_DRBG shape): encrypt an incrementing counter under a secret key held in the state. Predicting output means distinguishing the cipher from a random permutation. - **Hash / HMAC chains** (Hash_DRBG, HMAC_DRBG shapes): repeatedly hash the state forward; one-wayness gives backtracking resistance for free. - **Stream ciphers** such as ChaCha20, which is what modern operating-system generators use to expand a seed. All of them are still deterministic functions of a state. What changes is that recovering that state from output is as hard as breaking the underlying cipher or hash, and that the state is seeded from a genuine entropy source rather than a clock. ## The practical rule and what justifies it The rule "use the cryptographic API for anything security-relevant" is not superstition or cargo cult; it is the observation that unpredictability is not testable after the fact. You cannot look at output and conclude it is safe, you cannot fix a weak generator by hashing its output (the hash is deterministic and the input space is still small), and you will not get a runtime error when you get it wrong. The property has to be chosen at the point where the generator is selected, because that is the only place it can be established.
- If the ordinary generator's output looks fine, can you fix it by hashing every value before use?No. Hashing is a deterministic public function, so it preserves whatever guessability the input had. If the attacker can enumerate the generator's state or seed — a clock value, a counter, a recovered 48-bit state — they enumerate the hashes just as cheaply. Hashing only helps when the input already has enough unpredictable entropy, in which case you did not need the hash.
- Does a generator with a very long period, say 2^19937, give you security?No. Period measures how long before the sequence repeats; security measures how hard it is to predict the next value. Mersenne Twister has that enormous period and is trivially predictable from 624 outputs. Period and unpredictability are independent properties, and confusing them is a common interview trap.
- What does state-compromise resistance buy you if the attacker already has memory access?It bounds the blast radius in time. With backtracking resistance, a state snapshot does not retroactively expose tokens already issued — so past sessions and past reset links are not decryptable from the dump. With reseeding, the attacker's window closes going forward once fresh entropy is mixed in. Neither helps while the attacker still has live access, but incident scope is usually decided by exactly these bounds.
A shuffled deck and a deck a magician shuffled both look shuffled. The difference is not in the card order — it is in whether someone in the room can name the next card.
saying these in an interview costs you the question
- "We tested the output distribution and it was uniform, so the generator is fine" — uniformity is orthogonal to predictability.
- "It has a huge period, so it is secure" — period is not unpredictability.
- "We hash the output, so it cannot be predicted" — hashing preserves the guessability of a small input space.
- "We seed it with the current time in nanoseconds, that is plenty of entropy" — the seed space is enumerable offline.
- Treating a randomly-generated-looking value as proof of unpredictability because no duplicates were observed.