Random Number Generation

1. Why Crypto Lives or Dies on Randomness

Keys, nonces, IVs, salts, DH exponents must be unpredictable: attacker guessing the RNG output breaks AES-256 as easily as guessing the key. True Random Number Generators (TRNG: thermal noise, jitter, quantum) harvest physical entropy; Pseudorandom Generators (PRNG: deterministic expansion of a seed) stretch it. Rule: entropy in (TRNG) → stretch (CSPRNG) → never raw PRNG (rand(), LCG predictable from a few outputs).

\text{Security} \le \min(\text{algorithm bits}, \text{seed entropy bits})

A 256-bit key grown from a 32-bit seed gives only 32-bit security.

2. PRNG vs CSPRNG (Exam Table)

Property	Plain PRNG (LCG, Mersenne)	CSPRNG (CTR-DRBG, Hash-DRBG, ChaCha20-DRBG)
Next-bit test	Fails (state recoverable: LCG from 3 outputs)	Passes — next bit unpredictable from all previous
Seed recovery	Easy (Mersenne state from 624 outputs)	Infeasible (one-way update)
Backtracking	Old outputs recoverable after state leak	Resistant (state update one-way)
Prediction	Future outputs computable	Resistant with reseeding
Use	Simulations, Monte Carlo	Keys, nonces, IVs, salts

LCG break sketch: with $x_{n+1} = ax_n + c \bmod m$ , three consecutive outputs expose the $(a, c, m)$ structure — the textbook predict-rand() exercise. Debian OpenSSL 2008 fiasco (commented-out entropy line left only 32,767 possible keys; mass revocation) is the cautionary tale.

3. How Real Systems Generate (Linux + NIST)

Linux: getrandom() and /dev/urandom — ChaCha20-based CSPRNG seeded from an entropy pool (interrupt timings, jitter, RDRAND mixed in); blocks only until the initial seed exists at early boot; never use rand() or random() for keys.
NIST SP 800-90A DRBGs: Hash-DRBG, HMAC-DRBG, CTR-DRBG follow instantiate(seed) → generate → reseed, with internal $(V, C)$ state and a backtracking-resistant update $V := f(V)$ after each call. Reseed with fresh entropy (TRNG) periodically and after every fork or VM snapshot (snapshot-restore repeats state, so reseeding is mandatory).
Hardware: RDRAND and RDSEED (Intel), TPM RNG, phone sensor and thermal sources — mixed (XOR) into the pool, never the sole source (audit caution after the Dual-EC-DRBG backdoor).

4. Nonce and IV Discipline (Where Exams Bite)

Reuse kills: CTR nonce repeat gives a two-time pad ( $C_1 \oplus C_2 = P_1 \oplus P_2$ ); GCM nonce repeat leaks the authentication key; ECDSA nonce ( $k$ ) repeat or bias leaks the private key (PS3 Sony 2010 used a fixed $k$ ; the fix is RFC 6979 deterministic $k = HMAC(d, m)$ ).
Rules: key = 128–256 fresh entropy bits; nonce = unique (counter or 96-bit random with birthday check); CBC IV = unpredictable random (BEAST lesson); salt = at least 128-bit random per password; seed files reseeded per boot and per container.
Testing: monobit, poker, runs (FIPS 140 legacy), SP 800-90B entropy estimation, TestU01 and Dieharder suites — statistical only; unpredictability needs design review, not just tests.

Exam Points

Entropy-bound formula + Debian 2008 story — 2-mark opener with moral.
PRNG-vs-CSPRNG table (next-bit, backtracking, LCG and Mersenne breaks) — 5-mark core.
Linux getrandom and NIST DRBG instantiate–generate–reseed cycle.
Nonce-reuse kill list (CTR, GCM, ECDSA and PS3) + RFC 6979 fix.

Random Number Generation