\documentclass{beamer} \usepackage{amsmath} \usepackage{graphicx} \newcommand{\defn}[1]{\textbf{#1}} \newcommand{\NetBSD}{NetBSD} \newcommand{\devrandom}{\texttt{/dev/random}} \newcommand{\devurandom}{\texttt{/dev/urandom}} \newcommand{\devxrandom}{\texttt{/dev/u?random}} \title{The New \NetBSD\ Entropy Subsystem} \author{Taylor `Riastradh' Campbell \\ \texttt{campbell@mumble.net} \\ \texttt{riastradh@NetBSD.org}} \date{EuroBSDcon 2021 \\ nowhere and everywhere (it's a global pandemic) \\ September 20, 2021} \begin{document} \frame{\titlepage} \begin{frame} \frametitle{NetBSD entropy pool data flow} \includegraphics[width=0.8\paperwidth]{pools-entropy.eps} \end{frame} \begin{frame} \frametitle{Computers need unpredictable secrets} \begin{itemize} \item HTTPS, SSH, etc., need long-term secret keys to prevent impersonation of servers and clients. \item HTTPS, SSH, etc., need short-term secret keys to prevent forgery and eavesdropping in sessions. \item Operating systems need ephemeral secrets to swap volatile secrets onto nonvolatile media without exposing them to future theft. \end{itemize} \end{frame} \begin{frame} \frametitle{What does `unpredictable' mean?} \begin{itemize} \item Adversary wants to impersonate, forge, eavesdrop, etc., by guessing secrets. \item Adversary has incomplete information---a state of knowledge. \item Adversary knows \emph{process} used to choose secrets (and protocol---HTTPS, SSH, etc.), but not the secrets themselves. \end{itemize} \end{frame} \begin{frame} \frametitle{Quantifying unpredictability} \begin{itemize} \item Language of probability theory. \item A probability distribution represents a state of knowledge about an unknown process outcome by assigning a weight to every possible outcome. \item Example: Fair coin toss $C$, possible outcomes are `heads' or `tails'. \begin{itemize} \item $\Pr[C = \text{heads}] = 1/2$ \item $\Pr[C = \text{tails}] = 1/2$ \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{Quantifying unpredictability} \begin{itemize} \item Example: Sum $S$ of two die rolls, possible outcomes are 2 through 12. \begin{itemize} \item $\Pr[S = 2] = 1/36$ \item $\Pr[S = 3] = 2/36 = 1/18$ \item $\Pr[S = 4] = 3/36 = 1/12$ \item $\vdots$ \item $\Pr[S = 12] = 1/36$ \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{Quantifying unpredictability} \begin{itemize} \item Adversary wins prize if they guess the secret (and then impersonate, forge, eavesdrop, etc.). \item What's adversary's probability of success for best strategy? \item Example: Fair coin toss: 1/2, doesn't make a difference if adversary's strategy is to guess heads or guess tails. \item Example: Sum of two die rolls: 1/6, if they guess 7; all other outcomes have lower probability. \end{itemize} \end{frame} \begin{frame} \frametitle{Quantifying unpredictability} \begin{itemize} \item \defn{Entropy} is a numeric summary of a probability distribution, or of a process whose outcomes follow a probability distribution. \begin{itemize} \item \emph{Not} a property of any particular value like `\texttt{hunter2}' or `\texttt{correct horse battery staple}'! \end{itemize} \item Many kinds of entropy (Shannon, Hartley, Reny\'i, min) but mainly one relevant to cryptography: min-entropy. \item \defn{Min-entropy} of a probability distribution is the negative log of the adversary's best chance of success at guessing the secret, i.e., the negative log of the probability of the most probable outcome: \[ H_\infty(P) = -\log \max_x P(x). \] \item (All logarithms in base 2, in units of bits.) \end{itemize} \end{frame} \begin{frame} \frametitle{Quantifying unpredictability} \begin{itemize} \item Min-entropy of fair coin toss: 1 bit. \item Min-entropy of die roll: $\log_2 1/6 = {\sim}2.5$ bits. \item Min-entropy of sum of two die rolls: $\log_2 1/6 = {\sim}2.5$ bits. \begin{itemize} \item Same as one die roll even though there are almost twice as many possible outcomes! \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{Computers and unpredictability} \begin{itemize} \item Computers are usually very predictable. \begin{itemize} \item (Software engineers in the audience furiously debugging bugs that are obviously impossible situations may dispute this.) \end{itemize} \item But we need to maximize unpredictability for secrets! \end{itemize} \end{frame} \begin{frame} \frametitle{Computers and unpredictability} \begin{itemize} \item Need device drivers to make observations of unpredictable physical phenomena unknown to adversaries. \item Example: driver for device with Geiger--M\"uller tube pointed at an alpha emitter to count ionizing events. \item Example: driver for bored human flipping coins and entering outcomes. \end{itemize} \end{frame} \begin{frame} \frametitle{Computers and unpredictability} More realistic examples: jitter between clocks. \begin{itemize} \item Common example: Ring oscillator---two circuits on a die clocked independently, one flipping bits in a loop and the other sampling the first. \begin{itemize} \item Most devices advertised as HWRNGs on systems-on-a-chip are built out of ring oscillatrs. \end{itemize} \item Half-example: Interrupt timings---hardware peripherals `sampling' CPU cycle counter. \begin{itemize} \item Difficult to \emph{confidently assess} entropy of distribution. \item Can adversary control network packet timings? \item Can adversary guess keystroke timings? \end{itemize} \item Non-example: Periodic timer interrupt \emph{driven by the same clock as} the CPU cycle counter. \begin{itemize} \item Zero entropy---deterministic relation between clocks, no jitter! \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{Uniformity} \begin{itemize} \item Physical systems tend to have very nonuniform distributions: the possible outcomes have different probabilities. \begin{itemize} \item Geiger counts are Poisson distributed (or, durations between are exponentially distributed). \item Consecutive samples of ring oscillators are not independent. \item Samples of multiple ring oscillators in parallel, with related clocks, are not independent. \item Even honest coin tosses have small biases! \end{itemize} \item Cryptography tends to want uniform distributions. \begin{itemize} \item Modern cryptography can turn a short 256-bit seed with uniform distribution into an essentially arbitrarily long stream of output that appears just as uniform---adversary has no hope of telling it apart from uniform. \item (Note: No cryptographic justification for `entropy depletion'---256 secret bits is enough, period. But it can be useful for testing.) \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{What an operating system does, roughly} So an operating system (on an otherwise essentially deterministic computer) needs to hash \emph{enough} samples from physical systems together into uniformly distributed seeds for cryptography, to produce output from \texttt{/dev/urandom} or similar. \end{frame} \begin{frame} \frametitle{Iterative-guessing attacks} \begin{itemize} \item Suppose physical samples come in: $s_1, s_2, s_3, \dots$ \item Each sample is from a process with \emph{low} min-entropy, say 32 bits. \item 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 the internet. \item Software repeatedly does this for many HTTPS queries, thereby exposing some functions $f_1 = H(s_1)$, $f_2 = H(s_1, s_2)$, $f_3 = H(s_1, s_2, s_3)$, $\dots$, of the unpredictable physical samples. \begin{itemize} \item (Here, $H$ produces \texttt{/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.) \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{Iterative-guessing attacks} \begin{itemize} \item Recall the min-entropy of the process producing $s_1$ had was only 32 bits. \item So, the adversary can probably perform a \emph{feasible} brute-force search (cost around $2^{32}$) to recover $s_1$, using knowledge of $f_1 = H(s_1)$ to confirm a guess. \item Then, knowing what $s_1$ was but not $s_2$, the adversary can do a brute-force search to recover $s_2$, using knowledge of $f_2 = H(s_1, s_2)$ to confirm a guess. \item 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. \end{itemize} \end{frame} \begin{frame} \frametitle{Iterative-guessing attacks} So an operating system should avoid exposing samples piecemeal---it needs to group them into batches with \emph{enough} aggregate entropy from all the sources that a brute-force search is totally infeasible. \end{frame} \begin{frame} \frametitle{Performance issues in sampling} \begin{itemize} \item Want to gather as many samples as possible to get lots of entropy. \item But incorporating samples costs computation and has some latency. \item So we gather samples into per-CPU pools---no interprocessor communication to take a sample, \emph{except} early at boot if we've definitely not yet had 256 bits of entropy so far. \item And during interrupts we store samples in a per-CPU buffer to be processed, and just drop additional samples if the buffer is fill, to avoid high interrupt latency. \end{itemize} \end{frame} \begin{frame} \frametitle{Performance issues in /dev/urandom and (re)seeding} \begin{itemize} \item \texttt{/dev/urandom} output is drawn from per-CPU PRNG state for scalability \item Don't want every batch of samples to trigger cross-call activity if nobody's actually using each PRNG \item Global entropy epoch counter enables lazy-reseed in chains of PRNGs (like Windows does now, according to their whitepaper!) \end{itemize} \end{frame} \begin{frame} \frametitle{What to do if there's not enough entropy and you need a key?} \begin{itemize} \item For machines with on-board HWRNGs (x86 RDRAND/RDSEED, ARMv8.5-RNG RNDRRS, many newer SoCs): not a concern. \item If the operator has stored a seed on disk, NetBSD automatically updates it on boot, on shutdown, and daily. \item For other machines, well\dots \end{itemize} \end{frame} \begin{frame}[fragile] \frametitle{What to do if there's not enough entropy and you need a key?} \begin{itemize} \item If no HWRNG and no seed, traditional answer is: block key generation! \begin{quotation}\scriptsize\noindent \begin{verbatim} $ 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 the disks) during the prime generation; this gives the random number generator a better chance to gain enough entropy. \end{verbatim} \end{quotation} \item Very annoying on servers! (Even more annoying when `entropy depletion' is still in play.) \end{itemize} \end{frame} \begin{frame} \frametitle{What to do if there's not enough entropy and you need a key?} \begin{itemize} \item But does blocking at the moment of key generation \emph{ever} make sense? \item Historically, it did, under the premise that the OS would essentially just make up an idea of the entropy of the underlying process by examining consecutive differences of samples! \item But NetBSD (and FIPS these days!) asks that any estimate be based on knowledge of how the device works, so it is necessarily driver-specific. \item Can't guarantee nonzero entropy---and thus an end to blocking---this way; e.g., timer interrupt clocked by the same clock as CPU cycle counter has zero entropy!. \item Network appliances might seem like bricks if ssh-keygen blocks first startup this way---serious usability issues invite security-destroying workarounds. \end{itemize} \end{frame} \begin{frame} \frametitle{What to do if there's not enough entropy and you need a key?} \begin{itemize} \item Experience with blocking \texttt{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. \item So we try to get the message out other ways: \begin{itemize} \item offer option in installer to furnish seed \item warn operator in daily security report if not enough entropy \item one-liner in motd with reference to \url{https://man.NetBSD.org/entropy.7} man page \end{itemize} But we need to be careful to avoid warning fatigue! \item Might remove failed \texttt{getrandom} experiment (only in HEAD so far) and instead adopt never-blocks \texttt{getentropy} from OpenBSD and like POSIX is likely to adopt soon. (Discussion ongoing.) \end{itemize} \end{frame} \begin{frame} \frametitle{Cryptographic choices} \begin{itemize} \item Entropy pool: Keccak-p[1600,24] sponge duplex% \footnote{Guido Bertoni, Joan daemen, Micha\"el Peeters, and Gilles Van Assche, `Sponge-Based Pseudo-Random Number Generators', in Stefan Mangard and Fran\c ois-Xavier Standaert, eds., Cryptographic Hardware and Embedded Systems---CHES 2010, Springer LNCS 6225, pp. 33--47, \url{https://link.springer.com/chapter/10.1007/978-3-642-15031-9_3}, \url{https://keccak.team/files/SpongePRNG.pdf}} \begin{itemize} \item 200-byte state \item \texttt{feed(s)} enters a sample into the state \item \texttt{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 recovered again \item No entropy loss from samples (unlike, e.g., naive hashing with SHA-256): any sample can be recovered from knowledge of state, all other samples, and all outputs \item Security closely related to security of SHA-3 \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{Cryptographic choices} \begin{itemize} \item \texttt{/dev/urandom} pseudorandom number generator: NIST SP~800-90A Hash\_DRBG with SHA-256. \begin{itemize} \item Of the NIST SP~800-90A constructions, simplest security theorem relative to security of the hash function \item SHA-256 naturally avoids timing side channels unlike AES \item Used to use CTR\_DRBG with AES-128 until timing attacks published\footnote{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, \url{https://eprint.iacr.org/2019/1996}} \item (NetBSD kernel AES code has since been rewritten to eliminate timing side channels and a similar theorem has had a much more difficult proof exhibited for CTR\_DRBG, so could go back to that now) \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{Cryptographic choices} Why both Keccak duplex and Hash\_DRBG? \begin{itemize} \item Make it easier to approach FIPSy certificationy stuff (not actually done)---nobody ever got fired for choosing US federal government crypto. \item FIPS is (or was; things may be changing now) less picky about conditioning components than about DRBGs. \end{itemize} \end{frame} \begin{frame} \frametitle{Fin} Questions? \end{frame} \end{document}