The entropic principle/dev/u?random and NetBSD
Taylor ‘Riastradh’ Campbell
campbell@mumble.net
riastradh@NetBSD.org

EuroBSDcon 2014
Sofia, Bulgaria
September 28, 2014

Copyright (c) 2014, Taylor R. Campbell.
Verbatim copying and distribution of this entire article are permitted worldwide, without royalty, in any medium,provided this notice, and the copyright notice, are preserved.

Use /dev/urandom.

What is /dev/u?random?

I /dev/random and /dev/urandom are device files on allmodern Unix systems.
I Can’t predict what you will read from them.
I (Writes influence future reads.)
I Reading from /dev/random sometimes blocks.

Much cargo-cult voodoo surrounds /dev/u?random.

Unpredictability matters
I There are bad guys on the internet.
I They want to eavesdrop on our conversations.
I They want to intercept our conversations.

We need crypto to defend against this, and crypto needs
unpredictable secrets.
Photo copyright (c) by Kit Fox/Medill DC under CC-BY 2.0, cropped from original athttps://www.flickr.com/photos/medilldc/6797228431/

Unpredictability matters
What happens if you use crypto with predictable secrets?
I Smart cards generated keys for Taiwan’s national identity

database with broken RNGs leading to repeated andfactorable keys: http://smartfacts.cr.yp.to/
I Sony used ECDSA with a broken RNG to sign Playstation

firmware updates, revealing the signing key.
I Millions of embedded devices on the internet have private

RSA keys with factors in common generated from the same
RNG states: https://factorable.net/ (Mining Your P’sand Q’s).
I The NSA chose to backdoor the US’s pseudorandom numbergeneration standard, NIST SP800-90A, with Dual EC DRBG.

Security modelling

I APPLICATION: Generate bits with uniform distribution foruser programs.
I THREAT MODEL(S):
Attacker may read other bits from /dev/u?random.
Attacker may influence /dev/u?random.
I Attacker may compromise the kernel and get the internal stateof /dev/u?random.
II

I SECURITY PROPERTY: Attacker must not predict any

outputs not witnessed!
(Can’t attain the security property against attacker who
compromises the kernel, but some people worry about theoreticallyapproximating it for some reason.)Formalizing unpredictability

I Random variable X : observable physical system which cantake on possible values x0 , x1 , . . . , xn−1 .
I Probability that we observe X to have value x: Pr[X = x].
I Observation of X may not be predictable, but how do weformalize measuring how unpredictable?

Formalizing unpredictability: Shannon entropy
I Popular approach to measure unpredictability of X is Shannon

entropy, in units of bits:
X
H[X ] = −Pr[X = xi ] log2 Pr[X = xi ],igiving average bits of information per bit of observation of X .
I If X is drawn from {00, 01, 10, 11}, andPr[X = 00] = Pr[X = 11] = 1/2,Pr[X = 01] = Pr[X = 10] = 0,then H[X ] = 1, so since an observation of X has two bits, X
has half a bit of information per bit of observation.
I Guessing this is only as hard as guessing what a single coinflip was, not two coin flips in a row.

Formalizing unpredictability: not Shannon entropy

I Shannon entropy is no good for crypto: if there are 2255 + 1

possibilities for X , and(
1/2,Pr[X = x] =1/2256

if x = ‘hunter2’;
otherwise,(1)then H[X ] ≈ 128, but I don’t have to try 2127 possibilities
before I can probably guess your password — I have a pretty
good guess what it is!

Formalizing unpredictability: min-entropy

I Crypto instead uses min-entropy:

H∞ [X ] = − max log2 Pr[X = xi ].
i(2)I Min-entropy estimates the difficulty of the best strategy atguessing X .
I If X is drawn uniformly from k-bit strings, then H∞ [X ] = k,which is as good as you can get!
I Standard crypto practice is to use uniform distributions withk = 128 or k = 256 for key material.

/dev/u?random as random variable

I Kernel’s job is to make the random variable of reading k bitsfrom /dev/u?random have k bits of entropy.
I How does it choose the bits?
I Computer programs (single-threaded) are supposed to be

deterministic!

Entropy sources

I Computers make nondeterministic observations: clock skew,

network packets, keyboard input, disk seek times.
% gpg --gen-key...
Please bang on the keyboard like a monkey
to ensure there’s enough entropy!
I These entropy sources are random variables with highly

nonuniform distribution.
I Attacker may influence them: send regular network packets,bang on the keyboard like a robot, &c.

Entropy pooling and distribution

I Kernel combines entropy sources with crypto magic called

entropy extractors.
I Kernel uses output as seed for deterministic pseudorandom

number generator when you read from /dev/u?random.

What if there’s not much entropy?

I Your system autogenerated sshd keys from /dev/u?random

before you’ve had a chance to bang on the keyboard like amonkey!
I Keys are predictable! Bad guys can guess them and log in!

Even Debian is laughing at you! How do we prevent this?

What if there’s not much entropy?

I Naı̈ve answer: wait until system is unpredictable enough.
I /dev/random traditionally estimates how much entropy thesystem has observed, and blocks until it reaches a threshold.
I Use it as an ‘unpredictability barrier’: read once from/dev/random and once it unblocks, use /dev/urandom togenerate keys.
I /dev/urandom never blocks: whatever has been fed into theentropy pool, the kernel uses it to seed a pseudorandom
number generator and generate output.

What if there’s not much entropy?

Problem: Can’t say whether a state is unpredictable. Can only say
whether a process is unpredictable.
(Obligatory Dilbert reference.)
http://dilbert.com/strips/comic/2001-10-25/(Dilbert meets the accounting department’s random number generator, a troll who only says ‘nine’ over and overagain. Scott Adams won’t let me include his strip verbatim for this noncommercial use without paying him money.)

Estimating this is a hard problem! No good solution. Typicalapproaches are ad hoc.

Running out of entropy?

I /dev/random also traditionally blocks sometimes long afterboot.
I Original theory was if you read too much from it you run outof entropy, so you’d better wait for more.
I But entropy is not a scarce resource like oil.
I Entropy is a property of a physical process.
I So why block after boot?

Topping off the entropy tankI /dev/random blocking after boot is still useful!
I If you use it as an unpredictability barrier, you keep yourblocking code paths exercised.
I If you use it to generate keys always, you will notice when yourapplication blocks — instead of being told two years from now
that it doesn’t work on an embedded system you never evenheard of because it doesn’t have enough entropy at boot!
I But most applications just need /dev/urandom.

What if there is no entropy?

I What if there are no entropy sources?
I No disk, no mouse, no keyboard, no monkey.
I Kernel is totally deterministic: can’t be unpredictable.
I Can’t usefully serve /dev/u?random.
I Example: embedded appliances (Mining P’s & Q’s).
I Solution: save entropy from the factory installer onto small(32-byte) nonvolatile storage on install and shutdown, restore
on boot.
I This system engineering avoids need for /dev/random as

unpredictability barrier.

Exotic threat models

I Attacker can influence network packet timings? (Easy.)
I Attacker can influence keytrokes and timings?
I Attacker can compromise your CPU? (Paranoid view of Intelrdrand!)Good entropy extractors thwart manipulation of one entropy sourceor another.

Hardware random number generators

I PCI devices: HIFN 7751, Broadcom BCM58xx.
I SoC on-board devices: Broadcom BCM2385 (Raspberry Pi).
I CPU instructions: Intel rdrand, VIA PadLock.

Hardware random number generators

I . . . The coin in your trouser pocket:% echo hhhtttthhththttthhht...

>> /dev/random

NetBSD
Current code written mainly by Thor Lancelot Simon and me.
I /dev/u?random uses per-open or per-CPU pseudorandom

number generator state, so it scales.
I Kernel uses slow NIST CTR DRBG with AES-128 for key

material and /dev/u?random: attacker must never predict
unseen outputs.
I Kernel uses fast ChaCha8 without backtracking resistance fornon-key material, e.g. NFS transaction ids: attacker must notpredict new outputs ahead of time, but may predict old ones.
I Userland arc4random(3) API soon to be reimplemented withper-thread state and ChaCha8 instead of global RC4.
I (Let me know if you’ve heard of arc4random(3) being used

for key material! I wouldn’t recommend it!)Questions?

(Use /dev/urandom!)Appendix: Entropy game!

http://www.loper-os.org/bad-at-entropy/manmach.html

My password manager:{ tr -cd ’[:graph:]’ < /dev/urandom | head -c 20; } | \scrypt enc /dev/stdin password.scrypt