• what is a "random number"
• when you use them
• how to make them
• how to screw up

• my opinions
• math is elided
• theory is glossed over
• probably wrong stuff

• "uniform random variable"
• one of { min, ..., max } ("range")
• equal probability of each
• non-uniform random variable?

• uniform: coin, die roll, ...
• non-uniform: letters, heights, ...
• entropy:
  • log₂(# options)
  • entropy(random_u64()) = 64 bits
  • entropy(random_u64() % 8) = 3 bits

• computers are deterministic
• meaning: state S0 → state S1
• meaning: rand() in state S0 → state S1
• meaning: rand() in state S0 → V1
• aside: does a computer have 0 entropy?

• random: impossible to predict (*)
• pseudorandom: hard to predict?
  • ↪ how hard?
• RNG "strength" / "goodness"

(*): even with all info

• thermal noise
• various electrical effects
• chaotic systems
• Quantum ™
• open q: how random are these?
• → hardware RNG

• hardware to sample one of those things
• very slow
• "bad" randomness
• hard to assess
• sometimes not available
• ... or even present

• stateful object with a next() method

• stateful object with a next() method
• function : S → (V, S)

• stateful object with a next() method
• function : S → (V, S)
• S: "entropy pool"
  • initial S: "seed"
• V: value
  • "takes some entropy" from S (?)

• N_i uncorrelated to N_i+1
• N₀ ... N_i uncorrelated to N_i+1
• retain these properties for "a while"
  • note: all PRNGs are eventually periodic
  • → reseeding
• fast?

• const(S) → (N, S): N, N, N, ... (*)
• add1(S) → (S, S + 1): 0, 1, 2, ...
• direct(S) → (S₀, S_1...): S₀, S₁, ...

(*): prior art

• linear congruential generator (LCG)
• linear feedback shift register (LFSR)
  • shift-register generators
• counter-based generators
• more complex things

• lcg(S) → (S, (aS + c) % m)
• (a, c, m) tuple defines an LCG
• with good a, c, period is m - 1
• quality critically depends on (a, c, m)!
• see: RANDU (Knuth Vol 2 § 3.3.4)

• a = 65539, c = 0, m = 2³¹
• RANDU(S) → (S, 65539 * S mod 2³¹)
• 9S_n - 6S_{n + 1} + S_{n + 2} ≡ 0 mod 2³¹ (!)
• these form neat "planes" in 3d space
• oops... for science!

• S : a bit vector { S₀, S₁, ..., S_n }
• bit(S) → S_a ⊕ S_b ⊕ ... ("taps")
• update(S, v) → { v, S₀, ..., S_{n - 1} }
• lfsr(S) → (bit(S), update(S, bit(S)))
• { a, b, ... } defines the LFSR

• S : (seed, counter)
• counter((s, c)) → (f(s, c), (s, c + 1))
• what's f?
• example: "Squares"
• x = y = s * c, z = y + s
• x = x² + y; x = x² + z; x = x² + y

• [decades of research elided]
• Mersenne Twister
  • kind of a feedback shift register
  • very fast
  • very long period
  • quite high quality

• warning: math
• spectral test (for LCGs)
• statistics to the rescue
• Knuth Vol 2 § 3.3
• → diehard & dieharder
• "most runs mostly pass"

• recover MT state with a few hundred samples
• → reproduce its output
• same for many PRNGs
• dangerous property!
• idea: "cryptographically secure" PRNG

• csprng(S_i) → (V_i, S_i+1)
• given V₀, V₁, ..., V_n, can't predict V_{n + 1}
• → V_i doesn't "leak" state
• given S_i, can't recover V_i-k
• → state update is one-way

• S: (key K, counter C)
• mix(S, T): S_i → S'₀
• update(S): S_i → S_i+1
• extract(S): S_i → V_i
• update() and extract() are one-way

• us govt standard for "DRBGs"
• a few subtle security issues...
  • eg CTR block recurrence
• Dual_EC_DRBG scandal with NSA (!)
• others still in wide use

• the time
• timings: keyboard, disk, network
• how random is this stuff?
• sidechannels?
• magical amulets?? (special hardware)
• state of the art for decades

• RNG in the CPU hardware
• CTR-DRBG seeded off "hardware"
  • thermal / RF noise
• can you trust this?
• CrossTalk, Zen5 zero bug, NSA?

• arc4random(): RC4 key stream
• Fortuna: CTR-DRBG (ish) with AES
• Windows BCryptGenRandom(): CTR-DRBG with AES
• bssl RAND_bytes(): CTR-DRBG with AES
• linux kernel: CTR-DRBG with ChaCha20

• "entropy pool" (CSPRNG state)
• mix "everything" into this
  • attacker can't control all of it
  • any unknown input adds entropy
• generate out of it as needed

• /dev/random: "actual entropy"
• /dev/urandom: PRNG output
• "move the mouse around" / "type"
• random blocks, urandom doesn't
• q: when to use random?

• /dev/random: "actual entropy"
• /dev/urandom: PRNG output
• "move the mouse around" / "type"
• random blocks, urandom doesn't
• q: when to use random?
• a: never

• seed PRNG off kernel, use that
• CSPRNG ~always
  • unless you know perf is critical
• just use base::RandBytes() :)

• problem: fork() copies PRNG state
  • detect fork() and reseed

• problem: fork() copies PRNG state
  • detect fork() and reseed
• problem: VM snapshot copies PRNG state
  • reseed on every call?
  • ... if we can (RDRAND / etc)
  • ... or just give up

• CVE-2008-0166
• OpenSSL CSPRNG on Debian seeded with PID only
• → 32,767 possible output streams
• unnoticed for years
• ~all crypto broken on such systems
• CSPRNG only as good as seed

• DSA uses a random nonce
• non-random nonce → leak private key
• Sony did this
• → leaked root PS3 signing key!
• random quantities must be random

• N = pq (p, q random primes)
• N' = pq' or N' = p'q
• gcd(N, N') = p or q
• how??
  • bad or unseeded RNGs!
• routinely breaks 100ks of keys

• ANSI X9.31 CSPRNG
• X9.31 discloses full state if you have key...
• various Fortinet devices hardcoded key
• broke 100ks of keys

• Java SecureRandom default seed: 64 bits
• disclosed in 2013
• latent for... years?
• BitCoin keys from Android broken

• key schedule: key → longer key
• ... basically a CSPRNG
• output is biased
• → Fluhrer-Mantin-Shamir
• → break WEP for wifi
• arc4random() drops stream prefix

• from NIST SP 800-90A
• slow, weird CSPRNG
• NSA paid RSA Security to use it
• ... then used that use to standardize it
• widely considered likely backdoored
• rejected by everyone, later de-standardized

• rng failure cannot be tested for
• rng failure generally has no visible result
• these bugs can have unfixable consequences
  • leaked user data
  • decrypt-later

• use a good rng
• use big-enough random values
  • 128 or 256 bits
• use constructs that don't need one
• use bssl and //crypto
• talk to security

• Knuth Volume 2 3.3 for Math
• Cryptography Engineering Chapter 9 for Crypto
• [add yours here]