1.\" $NetBSD: rnd.4,v 1.22 2015/04/13 22:23:54 riastradh Exp $ 2.\" 3.\" Copyright (c) 2014 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" This code is derived from software contributed to The NetBSD Foundation 7.\" by Taylor R. Campbell. 8.\" 9.\" Redistribution and use in source and binary forms, with or without 10.\" modification, are permitted provided that the following conditions 11.\" are met: 12.\" 1. Redistributions of source code must retain the above copyright 13.\" notice, this list of conditions and the following disclaimer. 14.\" 2. Redistributions in binary form must reproduce the above copyright 15.\" notice, this list of conditions and the following disclaimer in the 16.\" documentation and/or other materials provided with the distribution. 17.\" 18.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 19.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 20.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 21.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 22.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28.\" POSSIBILITY OF SUCH DAMAGE. 29.\" 30.Dd November 16, 2014 31.Dt RND 4 32.Os 33.Sh NAME 34.Nm rnd 35.Nd random number generator 36.Sh DESCRIPTION 37The 38.Pa /dev/random 39and 40.Pa /dev/urandom 41devices generate bytes randomly with uniform distribution. 42Every read from them is independent. 43.Bl -tag -width /dev/urandom 44.It Pa /dev/urandom 45Never blocks. 46.It Pa /dev/random 47Sometimes blocks. 48Will block early at boot if the system's state is known to be 49predictable. 50.El 51.Pp 52Applications should read from 53.Pa /dev/urandom 54when they need randomly generated data, e.g. key material for 55cryptography or seeds for simulations. 56.Pp 57Systems should be engineered to judiciously read at least once from 58.Pa /dev/random 59at boot before running any services that talk to the internet or 60otherwise require cryptography, in order to avoid generating keys 61predictably. 62.Pp 63.Pa /dev/random 64may block at any time, so programs that read from it must be prepared 65to handle blocking. 66Interactive programs that block due to reads from 67.Pa /dev/random 68can be especially frustrating. 69.Pp 70If interrupted by a signal, reads from either 71.Pa /dev/random 72or 73.Pa /dev/urandom 74may return short, so programs that handle signals must be prepared to 75retry reads. 76.Pp 77Writing to either 78.Pa /dev/random 79or 80.Pa /dev/urandom 81influences subsequent output of both devices, guaranteed to take 82effect at next open. 83.Pp 84If you have a coin in your pocket, you can flip it 256 times and feed 85the outputs to 86.Pa /dev/random 87to guarantee your system is in a state that nobody but you and the 88bored security guard watching the surveillance camera in your office 89can guess: 90.Bd -literal -offset abcd 91% echo tthhhhhthhhththtthhhhthtththttth... > /dev/random 92.Ed 93.Pp 94(Sequence generated from a genuine US quarter dollar, guaranteed 95random.) 96.Sh SECURITY MODEL 97The 98.Nm 99subsystem provides the following security properties against two 100different classes of attackers, provided that there is enough entropy 101from entropy sources not seen by attackers: 102.Bl -bullet -offset abcd 103.It 104An attacker who has seen some outputs and can supply some entropy 105sources' inputs to the operating system cannot predict past or future 106unseen outputs. 107.It 108An attacker who has seen the entire state of the machine cannot predict 109past outputs. 110.El 111.Pp 112One 113.Sq output 114means a single read, no matter how short it is. 115.Pp 116.Sq Cannot predict 117means it is conjectured of the cryptography in 118.Fa /dev/random 119that any computationally bounded attacker who tries to distinguish 120outputs from uniform random cannot do more than negligibly better than 121uniform random guessing. 122.Sh ENTROPY 123The operating system contiuously makes observations of hardware 124devices, such as network packet timings, disk seek delays, and 125keystrokes. 126The observations are combined into a seed for a cryptographic 127pseudorandom number generator (PRNG) which is used to generate the 128outputs of both 129.Pa /dev/random 130and 131.Pa /dev/urandom . 132.Pp 133An attacker may be able to guess with nonnegligible chance of success 134what your last keystroke was, but guessing every observation the 135operating system may have made is more difficult. 136The difficulty of the best strategy at guessing a random variable is 137analyzed as the -log_2 of the highest probability of any outcome, 138measured in bits, and called its 139.Em min-entropy , 140or 141.Em entropy 142for short in cryptography. 143For example: 144.Bl -bullet -offset abcd -compact 145.It 146A fair coin toss has one bit of entropy. 147.It 148A fair (six-sided) die roll has a little over 2.5 bits of entropy. 149.It 150A string of two independent fair coin tosses has two bits of entropy. 151.It 152The toss of a pair of fair coins that are glued together has one bit of 153entropy. 154.It 155A uniform random distribution with 156.Fa n 157possibilities has log_2 158.Fa n 159bits of entropy. 160.It 161An utterance from an accounting troll who always says 162.Sq nine 163has zero bits of entropy. 164.El 165.Pp 166Note that entropy is a property of an observable physical process, not 167of a particular sample obtained by observing it. 168There are also kinds of entropy in information theory other than 169min-entropy, including the more well-known Shannon entropy, but they 170are not relevant here. 171.Pp 172Hardware devices that the operating system monitors for observations 173are called 174.Em "entropy sources" , 175and the observations are combined into an 176.Em "entropy pool" . 177The 178.Xr rndctl 8 179command queries information about entropy sources and the entropy pool, 180and can control which entropy sources the operating system uses or 181ignores. 182.Pp 183256 bits of entropy is typically considered intractible to guess with 184classical computers and with current models of the capabilities of 185quantum computers. 186.Pp 187Systems with nonvolatile storage should store a secret from 188.Pa /dev/urandom 189on disk during installation or shutdown, and feed it back during boot, 190so that the work the operating system has done to gather entropy -- 191including the work its operator may have done to flip a coin! -- can be 192saved from one boot to the next, and so that newly installed systems 193are not vulnerable to generating cryptographic keys predictably. 194.Pp 195The boot loaders in some 196.Nx 197ports support a command to load a seed from disk before the 198kernel has started. 199For those that don't, the 200.Xr rndctl 8 201command can do it once userland has started, for example by setting 202.Dq Va rndctl=YES 203in 204.Pa /etc/rc.conf ; 205see 206.Xr rc.conf 5 . 207.Sh LIMITATIONS 208Some people worry about recovery from state compromise -- that is, 209ensuring that even if an attacker sees the entire state of the 210operating system, then the attacker will be unable to predict any new 211future outputs as long as the operating system gathers fresh entropy 212quickly enough. 213.Pp 214But if an attacker has seen the entire state of your machine, 215refreshing entropy is probably the least of your worries, so we do not 216address that threat model here. 217.Pp 218The 219.Nm 220subsystem does 221.Em not 222automatically defend against hardware colluding with an attacker to 223influence entropy sources based on the state of the operating system. 224.Pp 225For example, a PCI device or CPU instruction for random number 226generation which has no side channel to an attacker other than the 227.Pa /dev/urandom 228device could be bugged to observe all other entropy sources, and to 229carefully craft 230.Sq observations 231that cause a certain number of bits of 232.Pa /dev/urandom 233output to be ciphertext that either is predictable to an attacker or 234conveys a message to an attacker. 235.Pp 236No amount of scrutiny by the system's operator could detect this. 237The only way to prevent this attack would be for the operator to 238disable all entropy sources that may be colluding with an attacker. 239If you're not sure which ones are not, you can always disable all of 240them and fall back to the coin in your pocket. 241.Sh IOCTLS 242The 243.Pa /dev/random 244and 245.Pa /dev/urandom 246devices support a number of ioctls, defined in the 247.In sys/rndio.h 248header file, for querying and controlling the entropy pool. 249.Pp 250Since timing between hardware events contributes to the entropy pool, 251statistics about the entropy pool over time may serve as a side channel 252for the state of the pool, so access to such statistics is restricted 253to the super-user and should be used with caution. 254.Pp 255Several ioctls are concerned with particular entropy sources, described 256by the following structure: 257.Bd -literal 258typedef struct { 259 char name[16]; /* symbolic name */ 260 uint32_t total; /* estimate of entropy provided */ 261 uint32_t type; /* RND_TYPE_* value */ 262 uint32_t flags; /* RND_FLAG_* mask */ 263} rndsource_t; 264 265#define RND_TYPE_UNKNOWN 266#define RND_TYPE_DISK /* disk device */ 267#define RND_TYPE_ENV /* environment sensor (temp, fan, &c.) */ 268#define RND_TYPE_NET /* network device */ 269#define RND_TYPE_POWER /* power events */ 270#define RND_TYPE_RNG /* hardware RNG */ 271#define RND_TYPE_SKEW /* clock skew */ 272#define RND_TYPE_TAPE /* tape drive */ 273#define RND_TYPE_TTY /* tty device */ 274#define RND_TYPE_VM /* virtual memory faults */ 275 276#define RND_TYPE_MAX /* value of highest-numbered type */ 277 278#define RND_FLAG_COLLECT_TIME /* use timings of samples */ 279#define RND_FLAG_COLLECT_VALUE /* use values of samples */ 280#define RND_FLAG_ESTIMATE_TIME /* estimate entropy of timings */ 281#define RND_FLAG_ESTIMATE_VALUE /* estimate entropy of values */ 282#define RND_FLAG_NO_COLLECT /* ignore samples from this */ 283#define RND_FLAG_NO_ESTIMATE /* do not estimate entropy */ 284.Ed 285.Pp 286The following ioctls are supported: 287.Bl -tag -width abcd 288.It Dv RNDGETENTCNT Pq Vt uint32_t 289Return the number of bits of entropy the system is estimated to have. 290.It Dv RNDGETSRCNUM Pq Vt rndstat_t 291.Bd -literal 292typedef struct { 293 uint32_t start; 294 uint32_t count; 295 rndsource_t source[RND_MAXSTATCOUNT]; 296} rndstat_t; 297.Ed 298.Pp 299Fill the 300.Fa sources 301array with information about up to 302.Fa count 303entropy sources, starting at 304.Fa start . 305The actual number of sources described is returned in 306.Fa count . 307At most 308.Dv RND_MAXSTATCOUNT 309sources may be requested at once. 310.It Dv RNDGETSRCNAME Pq Vt rndstat_name_t 311.Bd -literal 312typedef struct { 313 char name[16]; 314 rndsource_t source; 315} rndstat_name_t; 316.Ed 317.Pp 318Fill 319.Fa source 320with information about the entropy source named 321.Fa name , 322or fail with 323.Dv ENOENT 324if there is none. 325.It Dv RNDCTL Pq Vt rndctl_t 326.Bd -literal 327typedef struct { 328 char name[16]; 329 uint32_t type; 330 uint32_t flags; 331 uint32_t mask; 332} rndctl_t; 333.Ed 334.Pp 335For each entropy source of the type 336.Fa type , 337or if 338.Fa type 339is 340.Li 0xff 341then for the entropy source named 342.Fa name , 343replace the flags in 344.Fa mask 345by 346.Fa flags . 347.It Dv RNDADDDATA Pq Vt rnddata_t 348.Bd -literal 349typedef struct { 350 uint32_t len; 351 uint32_t entropy; 352 unsigned char data[RND_SAVEWORDS * sizeof(uint32_t)]; 353} rnddata_t; 354.Ed 355.Pp 356Feed 357.Fa len 358bytes of data to the entropy pool. 359The sample is expected to have been drawn with at least 360.Fa entropy 361bits of entropy. 362.Pp 363This ioctl can be used only once per boot. 364It is intended for a system that saves entropy to disk on shutdown and 365restores it on boot, so that the system can immediately be 366unpredictable without having to wait to gather entropy. 367.Pp 368This ioctl is the only way for userland to directly change the system's 369entropy estimate. 370.It Dv RNDGETPOOLSTAT Pq Vt rndpoolstat_t 371.Bd -literal 372typedef struct { 373 uint32_t poolsize; /* size of each LFSR in pool */ 374 uint32_t threshold; /* no. bytes of pool hash returned */ 375 uint32_t maxentropy; /* total size of pool in bits */ 376 uint32_t added; /* no. bits of entropy ever added */ 377 uint32_t curentropy; /* current entropy `balance' */ 378 uint32_t discarded; /* no. bits dropped when pool full */ 379 uint32_t generated; /* no. bits yielded by pool while 380 curentropy is zero */ 381} rndpoolstat_t; 382.Ed 383.Pp 384Return various statistics about entropy. 385.El 386.Sh IMPLEMENTATION NOTES 387(This section describes the current implementation of the 388.Nm 389subsystem at the time of writing. 390It may be out-of-date by the time you read it, and nothing in here 391should be construed as a guarantee about the behaviour of the 392.Pa /dev/random 393and 394.Pa /dev/urandom 395devices.) 396.Pp 397Samples from entropy sources are fed 32 bits at a time into the entropy 398pool, which is an array of 4096 bits, or 128 32-bit words, representing 39932 linear feedback shift registers each 128 bits long. 400.\" XXX Finish this description so it is implementable. 401.Pp 402When a user process opens 403.Pa /dev/random 404or 405.Pa /dev/urandom 406and first reads from it, the kernel draws from the entropy pool to seed 407a cryptographic pseudorandom number generator, the NIST CTR_DRBG 408(counter-mode deterministic random bit generator) with AES-128 as the 409block cipher, and uses that to generate data. 410.Pp 411To draw a seed from the entropy pool, the kernel 412.Bl -bullet -offset abcd -compact 413.It 414computes the SHA-1 hash of the entropy pool, 415.It 416feeds the SHA-1 hash word-by-word back into the entropy pool like an 417entropy source, and 418.It 419yields the xor of bytes 420.Pf 0.. Fa n 421with bytes 422.Fa n Ns +0.. Ns Fa n Ns Pf + Fa n 423of the hash, where 424.Fa n 425is 426.Dv RND_ENTROPY_THRESHOLD 427(currently 10). 428.El 429The kernel repeats the process, concatenating the results, until it has 430filled the seed. 431.Pp 432For each entropy source, the kernel estimates based on the previous 433samples how much entropy the source is providing in each new sample. 434The kernel maintains a count of the 435.Sq amount of entropy 436or 437.Sq number of bits of entropy 438in the pool. 439Each sample 440.Sq credits 441to the amount of entropy. 442Every time the kernel draws a PRNG seed from the entropy pool, it 443.Sq debits 444from the amount of entropy. 445.Pp 446Every open from 447.Pa /dev/urandom 448seeds an independent PRNG which is reseeded at the convenience of the 449kernel after a billion requests for output. 450Reads from 451.Pa /dev/urandom 452never block, even if the kernel estimates its state to be totally 453predictable. 454.Pp 455Every open from 456.Pa /dev/random 457seeds an independent PRNG which is reseeded after every 16 bytes of 458output. 459Reads from 460.Pa /dev/random 461block if the PRNG needs to be (re)seeded and the kernel's entropy 462estimate is too low. 463.Pp 464It is possible to fool the kernel's entropy estimator, in which case 465reads from 466.Pa /dev/random 467may return immediately even if the kernel is in a totally predictable 468state. 469.Pp 470Writes to 471.Pa /dev/random 472and 473.Pa /dev/urandom 474devices do not change the kernel's entropy estimate. 475.Sh FILES 476.Bl -tag -width /dev/urandom -compact 477.It Pa /dev/random 478Uniform random byte source. 479May block. 480.It Pa /dev/urandom 481Uniform random byte source. 482Never blocks. 483.El 484.Sh SEE ALSO 485.Xr arc4random 3 , 486.Xr rndctl 8 , 487.Xr cprng 9 488.Rs 489.%A Elaine Barker 490.%A John Kelsey 491.%T Recommendation for Random Number Generation Using Deterministic Random Bit Generators 492.%D January 2012 493.%I National Institute of Standards and Technology 494.%O NIST Special Publication 800-90A 495.%U http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf 496.Re 497.Rs 498.%A Daniel J. Bernstein 499.%T Entropy Attacks! 500.%D 2014-02-05 501.%U http://blog.cr.yp.to/20140205-entropy.html 502.Re 503.Rs 504.%A Nadia Heninger 505.%A Zakir Durumeric 506.%A Eric Wustrow 507.%A J. Alex Halderman 508.%T Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices 509.%B Proceedings of the 21st USENIX Security Symposium 510.%I USENIX 511.%D August 2012 512.%P 205-220 513.%U https://www.usenix.org/conference/usenixsecurity12/technical-sessions/presentation/heninger 514.%U https://factorable.net/ 515.Re 516.Sh HISTORY 517The 518.Pa /dev/random 519and 520.Pa /dev/urandom 521devices first appeared in 522.Nx 1.3 . 523.Sh AUTHORS 524The 525.Nm 526subsystem was first implemented by 527.An Michael Graff Aq Mt explorer@flame.org , 528and was then largely rewritten by 529.An Thor Lancelot Simon Aq Mt tls@NetBSD.org 530with later contributions by 531.An Taylor R. Campbell Aq Mt riastradh@NetBSD.org . 532.Sh BUGS 533There is no way to disable all entropy sources, in this and subsequent 534boots and no matter what USB devices you plug in against your mother's 535sage advice, in order to defend against the colluding hardware attack. 536.Pp 537The implementation confuses the number of bits in the entropy pool's 538physical representation, as a set of 32 128-bit LFSRs, with the number 539of bits of entropy that a system needs in order to be unpredictable, so 540even if entropy estimates were accurate and high, it takes unreasonably 541long for 542.Pa /dev/random 543to stop blocking. 544.Pp 545Many people are confused about what 546.Pa /dev/random 547and 548.Pa /dev/urandom 549mean. 550Unfortunately, no amount of software engineering can fix that. 551.Sh ENTROPY ACCOUNTING 552The entropy accounting described here is not grounded in any 553cryptography theory. 554It is done because it was always done, and because it gives people a 555warm fuzzy feeling about information theory. 556.Pp 557The folklore is that every 558.Fa n Ns -bit 559output of 560.Fa /dev/random 561is not merely indistinguishable from uniform random to a 562computationally bounded attacker, but information-theoretically is 563independent and has 564.Fa n 565bits of entropy even to a computationally 566.Em unbounded 567attacker -- that is, an attacker who can recover AES keys, compute 568SHA-1 preimages, etc. 569This property is not provided, nor was it ever provided in any 570implementation of 571.Fa /dev/random 572known to the author. 573.Pp 574This property would require that, after each read, the system discard 575all measurements from hardware in the entropy pool and begin anew. 576All work done to make the system unpredictable would be thrown out, and 577the system would immediately become predictable again. 578Reverting the system to being predictable every time a process reads 579from 580.Fa /dev/random 581would give attackers a tremendous advantage in predicting future 582outputs, especially if they can fool the entropy estimator, e.g. by 583sending carefully timed network packets. 584.Pp 585If you filled your entropy pool by flipping a coin 256 times, you would 586have to flip it again 256 times for the next output, and so on. 587In that case, if you really want information-theoretic guarantees, you 588might as well take 589.Fa /dev/random 590out of the picture and use your coin flips verbatim. 591.Pp 592On the other hand, every cryptographic protocol in practice, including 593HTTPS, SSH, PGP, etc., expands short secrets deterministically into 594long streams of bits, and their security relies on conjectures that a 595computationally bounded attacker cannot distinguish the long streams 596from uniform random. 597If we couldn't do that for 598.Fa /dev/random , 599it would be hopeless to assume we could for HTTPS, SSH, PGP, etc. 600.Pp 601History is littered with examples of broken entropy sources and failed 602system engineering for random number generators. 603Nobody has ever reported distinguishing AES ciphertext from uniform 604random without side channels, nor reported computing SHA-1 preimages 605faster than brute force. 606The folklore information-theoretic defence against computationally 607unbounded attackers replaces system engineering that successfully 608defends against realistic threat models by imaginary theory that 609defends only against fantasy threat models. 610