The New NetBSD Entropy Subsystem
Taylor ‘Riastradh’ Campbell
campbell@mumble.net
riastradh@NetBSD.org

EuroBSDcon 2021
nowhere and everywhere (it’s a global pandemic)
September 20, 2021

NetBSD entropy pool data flow
cpu0

cpu1

samples

cpu2interrupt sources
samples

pool

pool

globalcpu3/dev/urandom
getrandom
outputs
Hash_DRBG (prng)

samples

poolpoolsamplesComputers need unpredictable secrets

I HTTPS, SSH, etc., need long-term secret keys to prevent
impersonation of servers and clients.
I HTTPS, SSH, etc., need short-term secret keys to prevent
forgery and eavesdropping in sessions.
I Operating systems need ephemeral secrets to swap volatile
secrets onto nonvolatile media without exposing them tofuture theft.

What does ‘unpredictable’ mean?

I Adversary wants to impersonate, forge, eavesdrop, etc., byguessing secrets.
I Adversary has incomplete information—a state of knowledge.
I Adversary knows process used to choose secrets (andprotocol—HTTPS, SSH, etc.), but not the secrets themselves.

Quantifying unpredictability

I Language of probability theory.
I A probability distribution represents a state of knowledge
about an unknown process outcome by assigning a weight toevery possible outcome.
I Example: Fair coin toss C , possible outcomes are ‘heads’ or‘tails’.
I Pr[C = heads] = 1/2
I Pr[C = tails] = 1/2

Quantifying unpredictability

I Example: Sum S of two die rolls, possible outcomes are 2
through 12.
I Pr[S = 2] = 1/36
I Pr[S = 3] = 2/36 = 1/18
I Pr[S = 4] = 3/36 = 1/12.
I ..
I Pr[S = 12] = 1/36

Quantifying unpredictabilityI Adversary wins prize if they guess the secret (and thenimpersonate, forge, eavesdrop, etc.).
I What’s adversary’s probability of success for best strategy?
I Example: Fair coin toss: 1/2, doesn’t make a difference ifadversary’s strategy is to guess heads or guess tails.
I Example: Sum of two die rolls: 1/6, if they guess 7; all otheroutcomes have lower probability.

Quantifying unpredictability
I Entropy is a numeric summary of a probability distribution, orof a process whose outcomes follow a probability distribution.
I Not a property of any particular value like ‘hunter2’ or‘correct horse battery staple’ !

I Many kinds of entropy (Shannon, Hartley, Renyı́, min) but
mainly one relevant to cryptography: min-entropy.
I Min-entropy of a probability distribution is the negative logof the adversary’s best chance of success at guessing thesecret, i.e., the negative log of the probability of the mostprobable outcome:H∞ (P) = − log max P(x).
x

I (All logarithms in base 2, in units of bits.)

Quantifying unpredictability

I Min-entropy of fair coin toss: 1 bit.
I Min-entropy of die roll: log2 1/6 = ∼2.5 bits.
I Min-entropy of sum of two die rolls: log2 1/6 = ∼2.5 bits.
I Same as one die roll even though there are almost twice as
many possible outcomes!

Computers and unpredictability

I Computers are usually very predictable.
I (Software engineers in the audience furiously debugging bugs
that are obviously impossible situations may dispute this.)

I But we need to maximize unpredictability for secrets!

Computers and unpredictability

I Need device drivers to make observations of unpredictablephysical phenomena unknown to adversaries.
I Example: driver for device with Geiger–Müller tube pointed at
an alpha emitter to count ionizing events.
I Example: driver for bored human flipping coins and enteringoutcomes.

Computers and unpredictability
More realistic examples: jitter between clocks.
I Common example: Ring oscillator—two circuits on a die
clocked independently, one flipping bits in a loop and theother sampling the first.
I Most devices advertised as HWRNGs on systems-on-a-chip arebuilt out of ring oscillatrs.

I Half-example: Interrupt timings—hardware peripherals‘sampling’ CPU cycle counter.
I Difficult to confidently assess entropy of distribution.
I Can adversary control network packet timings?
I Can adversary guess keystroke timings?

I Non-example: Periodic timer interrupt driven by the same
clock as the CPU cycle counter.
I Zero entropy—deterministic relation between clocks, no jitter!

Uniformity
I Physical systems tend to have very nonuniform distributions:the possible outcomes have different probabilities.
I Geiger counts are Poisson distributed (or, durations between
are exponentially distributed).
I Consecutive samples of ring oscillators are not independent.
I Samples of multiple ring oscillators in parallel, with related
clocks, are not independent.
I Even honest coin tosses have small biases!

I Cryptography tends to want uniform distributions.
I Modern cryptography can turn a short 256-bit seed withuniform distribution into an essentially arbitrarily long streamof output that appears just as uniform—adversary has no hopeof telling it apart from uniform.
I (Note: No cryptographic justification for ‘entropy
depletion’—256 secret bits is enough, period. But it can be
useful for testing.)

What an operating system does, roughly

So an operating system (on an otherwise essentially deterministiccomputer) needs to hash enough samples from physical systems
together into uniformly distributed seeds for cryptography, toproduce output from /dev/urandom or similar.

Iterative-guessing attacks
I Suppose physical samples come in: s1 , s2 , s3 , . . .
I Each sample is from a process with low min-entropy, say 32bits.
I Suppose an application immediately tries to do cryptography
with what we have so far—e.g., generates a Diffie–Hellman
secret for an HTTPS query, and exposes the public key on theinternet.
I Software repeatedly does this for many HTTPS queries,
thereby exposing some functions f1 = H(s1 ), f2 = H(s1 , s2 ),f3 = H(s1 , s2 , s3 ), . . . , of the unpredictable physical samples.
I (Here, H produces /dev/urandom output, generates a DH key
pair from it, and returns the public part; the details aren’t
important here—but are known to the adversary.)

Iterative-guessing attacks

I Recall the min-entropy of the process producing s1 had wasonly 32 bits.
I So, the adversary can probably perform a feasible brute-force
search (cost around 232 ) to recover s1 , using knowledge of
f1 = H(s1 ) to confirm a guess.
I Then, knowing what s1 was but not s2 , the adversary can do abrute-force search to recover s2 , using knowledge of
f2 = H(s1 , s2 ) to confirm a guess.
I Lather, rinse, repeat, and the adversary can forge or eavesdrop
on the whole session indefinitely this way—the new samples
don’t help if the adversary can catch up incrementally.

Iterative-guessing attacks

So an operating system should avoid exposing samples
piecemeal—it needs to group them into batches with enoughaggregate entropy from all the sources that a brute-force search is
totally infeasible.

Performance issues in sampling

I Want to gather as many samples as possible to get lots ofentropy.
I But incorporating samples costs computation and has somelatency.
I So we gather samples into per-CPU pools—no interprocessor
communication to take a sample, except early at boot if we’ve
definitely not yet had 256 bits of entropy so far.
I And during interrupts we store samples in a per-CPU buffer tobe processed, and just drop additional samples if the buffer isfill, to avoid high interrupt latency.

Performance issues in /dev/urandom and (re)seeding

I /dev/urandom output is drawn from per-CPU PRNG state
for scalability
I Don’t want every batch of samples to trigger cross-callactivity if nobody’s actually using each PRNG
I Global entropy epoch counter enables lazy-reseed in chains ofPRNGs (like Windows does now, according to theirwhitepaper!)What to do if there’s not enough entropy and you need akey?

I For machines with on-board HWRNGs (x86RDRAND/RDSEED, ARMv8.5-RNG RNDRRS, many newerSoCs): not a concern.
I If the operator has stored a seed on disk, NetBSD
automatically updates it on boot, on shutdown, and daily.
I For other machines, well. . .

What to do if there’s not enough entropy and you need akey?

I If no HWRNG and no seed, traditional answer is: block keygeneration!
$ gpg --gen-key...
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize thedisks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.

I Very annoying on servers! (Even more annoying when‘entropy depletion’ is still in play.)What to do if there’s not enough entropy and you need akey?
I But does blocking at the moment of key generation ever makesense?
I Historically, it did, under the premise that the OS would
essentially just make up an idea of the entropy of theunderlying process by examining consecutive differences ofsamples!
I But NetBSD (and FIPS these days!) asks that any estimate
be based on knowledge of how the device works, so it isnecessarily driver-specific.
I Can’t guarantee nonzero entropy—and thus an end toblocking—this way; e.g., timer interrupt clocked by the same
clock as CPU cycle counter has zero entropy!.
I Network appliances might seem like bricks if ssh-keygen blocksfirst startup this way—serious usability issues invite
security-destroying workarounds.

What to do if there’s not enough entropy and you need akey?
I Experience with blocking getrandom system call in NetBSD,
along with meaningful entropy estimates, has been
negative—causes weird hangs in places that make no sense
and gives no useful feedback.
I So we try to get the message out other ways:
I offer option in installer to furnish seed
I warn operator in daily security report if not enough entropy
I one-liner in motd with reference tohttps://man.NetBSD.org/entropy.7 man page

But we need to be careful to avoid warning fatigue!
I Might remove failed getrandom experiment (only in HEAD sofar) and instead adopt never-blocks getentropy fromOpenBSD and like POSIX is likely to adopt soon. (Discussionongoing.)

Cryptographic choices
I Entropy pool: Keccak-p[1600,24] sponge duplex1
I 200-byte state
I feed(s) enters a sample into the state
I fetch(L) returns an L-byte string from the state affected by
all inputs and erases part of the state so it can’t be recoveredagainI No entropy loss from samples (unlike, e.g., naive hashing withSHA-256): any sample can be recovered from knowledge ofstate, all other samples, and all outputs
I Security closely related to security of SHA-3

1Guido Bertoni, Joan daemen, Michaël Peeters, and Gilles Van Assche,‘Sponge-Based Pseudo-Random Number Generators’, in Stefan Mangard andFrano̧is-Xavier Standaert, eds., Cryptographic Hardware and Embedded
Systems—CHES 2010, Springer LNCS 6225, pp. 33–47,
https://link.springer.com/chapter/10.1007/978-3-642-15031-9_3,
https://keccak.team/files/SpongePRNG.pdf

Cryptographic choices
I /dev/urandom pseudorandom number generator: NISTSP 800-90A Hash DRBG with SHA-256.
I Of the NIST SP 800-90A constructions, simplest security
theorem relative to security of the hash function
I SHA-256 naturally avoids timing side channels unlike AES
I Used to use CTR DRBG with AES-128 until timing attacks
published2
I (NetBSD kernel AES code has since been rewritten toeliminate timing side channels and a similar theorem has had amuch more difficult proof exhibited for CTR DRBG, so could
go back to that now)

2

Shaanan Cohney, Andrew Kwong, Shachar Paz, Daniel Genkin, Nadia
Heninger, Eyal Ronen, and Yuval Yarom, ‘Pseudorandom Black Swans: Cache
Attacks on CTR DRBG’, Cryptology ePrint Archive, Report 2019/996,
https://eprint.iacr.org/2019/1996

Cryptographic choices

Why both Keccak duplex and Hash DRBG?
I Make it easier to approach FIPSy certificationy stuff (notactually done)—nobody ever got fired for choosing US federal
government crypto.
I FIPS is (or was; things may be changing now) less pickyabout conditioning components than about DRBGs.

FinQuestions?