RND(4)                  NetBSD Kernel Interfaces Manual                 RND(4)

NAME
     rnd -- random number generator

DESCRIPTION
     The /dev/random and /dev/urandom devices generate bytes randomly with
     uniform distribution.  Every read from them is independent.

     /dev/urandom  Never blocks.

     /dev/random   Sometimes blocks.  Will block early at boot if the system's
                   state is known to be predictable.

     Applications should read from /dev/urandom when they need randomly gener-
     ated data, e.g. key material for cryptography or seeds for simulations.

     Systems should be engineered to judiciously read at least once from
     /dev/random at boot before running any services that talk to the internet
     or otherwise require cryptography, in order to avoid generating keys pre-
     dictably.

     /dev/random may block at any time, so programs that read from it must be
     prepared to handle blocking.  Interactive programs that block due to
     reads from /dev/random can be especially frustrating.

     If interrupted by a signal, reads from either /dev/random or /dev/urandom
     may return short, so programs that handle signals must be prepared to
     retry reads.

     Writing to either /dev/random or /dev/urandom influences subsequent out-
     put of both devices, guaranteed to take effect at next open.

     If you have a coin in your pocket, you can flip it 256 times and feed the
     outputs to /dev/random to guarantee your system is in a state that nobody
     but you and the bored security guard watching the surveillance camera in
     your office can guess:

         % echo tthhhhhthhhththtthhhhthtththttth... > /dev/random

     (Sequence generated from a genuine US quarter dollar, guaranteed random.)

SECURITY MODEL
     The rnd subsystem provides the following security properties against two
     different classes of attackers, provided that there is enough entropy
     from entropy sources not seen by attackers:

            An attacker who has seen some outputs and can supply some entropy
             sources' inputs to the operating system cannot predict past or
             future unseen outputs.

            An attacker who has seen the entire state of the machine cannot
             predict past outputs.

     One `output' means a single read, no matter how short it is.

     `Cannot predict' means it is conjectured of the cryptography in
     /dev/random that any computationally bounded attacker who tries to dis-
     tinguish outputs from uniform random cannot do more than negligibly bet-
     ter than uniform random guessing.

ENTROPY
     The operating system contiuously makes observations of hardware devices,
     such as network packet timings, disk seek delays, and keystrokes.  The
     observations are combined into a seed for a cryptographic pseudorandom
     number generator (PRNG) which is used to generate the outputs of both
     /dev/random and /dev/urandom.

     An attacker may be able to guess with nonnegligible chance of success
     what your last keystroke was, but guessing every observation the operat-
     ing system may have made is more difficult.  The difficulty of the best
     strategy at guessing a random variable is analyzed as the -log_2 of the
     highest probability of any outcome, measured in bits, and called its
     min-entropy, or entropy for short in cryptography.  For example:
            A fair coin toss has one bit of entropy.
            A fair (six-sided) die roll has a little over 2.5 bits of
             entropy.
            A string of two independent fair coin tosses has two bits of
             entropy.
            The toss of a pair of fair coins that are glued together has one
             bit of entropy.
            A uniform random distribution with n possibilities has log_2 n
             bits of entropy.
            An utterance from an accounting troll who always says `nine' has
             zero bits of entropy.

     Note that entropy is a property of an observable physical process, not of
     a particular sample obtained by observing it.  There are also kinds of
     entropy in information theory other than min-entropy, including the more
     well-known Shannon entropy, but they are not relevant here.

     Hardware devices that the operating system monitors for observations are
     called entropy sources, and the observations are combined into an entropy
     pool.  The rndctl(8) command queries information about entropy sources
     and the entropy pool, and can control which entropy sources the operating
     system uses or ignores.

     256 bits of entropy is typically considered intractible to guess with
     classical computers and with current models of the capabilities of quan-
     tum computers.

     Systems with nonvolatile storage should store a secret from /dev/urandom
     on disk during installation or shutdown, and feed it back during boot, so
     that the work the operating system has done to gather entropy -- includ-
     ing the work its operator may have done to flip a coin! -- can be saved
     from one boot to the next, and so that newly installed systems are not
     vulnerable to generating cryptographic keys predictably.

     The boot loaders in some NetBSD ports support a command to load a seed
     from disk before the kernel has started.  For those that don't, the
     rndctl(8) command can do it once userland has started, for example by
     setting ``rndctl=YES'' in /etc/rc.conf; see rc.conf(5).

LIMITATIONS
     Some people worry about recovery from state compromise -- that is, ensur-
     ing that even if an attacker sees the entire state of the operating sys-
     tem, then the attacker will be unable to predict any new future outputs
     as long as the operating system gathers fresh entropy quickly enough.

     But if an attacker has seen the entire state of your machine, refreshing
     entropy is probably the least of your worries, so we do not address that
     threat model here.

     The rnd subsystem does not automatically defend against hardware collud-
     ing with an attacker to influence entropy sources based on the state of
     the operating system.

     For example, a PCI device or CPU instruction for random number generation
     which has no side channel to an attacker other than the /dev/urandom
     device could be bugged to observe all other entropy sources, and to care-
     fully craft `observations' that cause a certain number of bits of
     /dev/urandom output to be ciphertext that either is predictable to an
     attacker or conveys a message to an attacker.

     No amount of scrutiny by the system's operator could detect this.  The
     only way to prevent this attack would be for the operator to disable all
     entropy sources that may be colluding with an attacker.  If you're not
     sure which ones are not, you can always disable all of them and fall back
     to the coin in your pocket.

IOCTLS
     The /dev/random and /dev/urandom devices support a number of ioctls,
     defined in the <sys/rnd.h> header file, for querying and controlling the
     entropy pool.

     Since timing between hardware events contributes to the entropy pool,
     statistics about the entropy pool over time may serve as a side channel
     for the state of the pool, so access to such statistics is restricted to
     the super-user and should be used with caution.

     Several ioctls are concerned with particular entropy sources, described
     by the following structure:

     typedef struct {
             char            name[16];       /* symbolic name */
             uint32_t        total;          /* estimate of entropy provided */
             uint32_t        type;           /* RND_TYPE_* value */
             uint32_t        flags;          /* RND_FLAG_* mask */
     } rndsource_t;

     #define RND_TYPE_UNKNOWN
     #define RND_TYPE_DISK           /* disk device */
     #define RND_TYPE_ENV            /* environment sensor (temp, fan, &c.) */
     #define RND_TYPE_NET            /* network device */
     #define RND_TYPE_POWER          /* power events */
     #define RND_TYPE_RNG            /* hardware RNG */
     #define RND_TYPE_SKEW           /* clock skew */
     #define RND_TYPE_TAPE           /* tape drive */
     #define RND_TYPE_TTY            /* tty device */
     #define RND_TYPE_VM             /* virtual memory faults */

     #define RND_TYPE_MAX            /* value of highest-numbered type */

     #define RND_FLAG_COLLECT_TIME           /* use timings of samples */
     #define RND_FLAG_COLLECT_VALUE          /* use values of samples */
     #define RND_FLAG_ESTIMATE_TIME          /* estimate entropy of timings */
     #define RND_FLAG_ESTIMATE_VALUE         /* estimate entropy of values */
     #define RND_FLAG_NO_COLLECT             /* ignore samples from this */
     #define RND_FLAG_NO_ESTIMATE            /* do not estimate entropy */

     The following ioctls are supported:

     RNDGETENTCNT (uint32_t)
           Return the number of bits of entropy the system is estimated to
           have.

     RNDGETSRCNUM (rndstat_t)

           typedef struct {
                   uint32_t        start;
                   uint32_t        count;
                   rndsource_t     source[RND_MAXSTATCOUNT];
           } rndstat_t;

           Fill the sources array with information about up to count entropy
           sources, starting at start.  The actual number of sources described
           is returned in count.  At most RND_MAXSTATCOUNT sources may be
           requested at once.

     RNDGETSRCNAME (rndstat_name_t)

           typedef struct {
                   char            name[16];
                   rndsource_t     source;
           } rndstat_name_t;

           Fill source with information about the entropy source named name,
           or fail with ENOENT if there is none.

     RNDCTL (rndctl_t)

           typedef struct {
                   char            name[16];
                   uint32_t        type;
                   uint32_t        flags;
                   uint32_t        mask;
           } rndctl_t;

           For each entropy source of the type type, or if type is 0xff then
           for the entropy source named name, replace the flags in mask by
           flags.

     RNDADDDATA (rnddata_t)

           typedef struct {
                   uint32_t        len;
                   uint32_t        entropy;
                   unsigned char   data[RND_SAVEWORDS * sizeof(uint32_t)];
           } rnddata_t;

           Feed len bytes of data to the entropy pool.  The sample is expected
           to have been drawn with at least entropy bits of entropy.

           This ioctl can be used only once per boot.  It is intended for a
           system that saves entropy to disk on shutdown and restores it on
           boot, so that the system can immediately be unpredictable without
           having to wait to gather entropy.

           This ioctl is the only way for userland to directly change the sys-
           tem's entropy estimate.

     RNDGETPOOLSTAT (rndpoolstat_t)

           typedef struct {
                   uint32_t poolsize;      /* size of each LFSR in pool */
                   uint32_t threshold;     /* no. bytes of pool hash returned */
                   uint32_t maxentropy;    /* total size of pool in bits */
                   uint32_t added;         /* no. bits of entropy ever added */
                   uint32_t curentropy;    /* current entropy `balance' */
                   uint32_t discarded;     /* no. bits dropped when pool full */
                   uint32_t generated;     /* no. bits yielded by pool while
                                              curentropy is zero */
           } rndpoolstat_t;

           Return various statistics about entropy.

IMPLEMENTATION NOTES
     (This section describes the current implementation of the rnd subsystem
     at the time of writing.  It may be out-of-date by the time you read it,
     and nothing in here should be construed as a guarantee about the behav-
     iour of the /dev/random and /dev/urandom devices.)

     Samples from entropy sources are fed 32 bits at a time into the entropy
     pool, which is an array of 4096 bits, or 128 32-bit words, representing
     32 linear feedback shift registers each 128 bits long.

     When a user process opens /dev/random or /dev/urandom and first reads
     from it, the kernel draws from the entropy pool to seed a cryptographic
     pseudorandom number generator, the NIST CTR_DRBG (counter-mode determin-
     istic random bit generator) with AES-128 as the block cipher, and uses
     that to generate data.

     To draw a seed from the entropy pool, the kernel
            computes the SHA-1 hash of the entropy pool,
            feeds the SHA-1 hash word-by-word back into the entropy pool like
             an entropy source, and
            yields the xor of bytes 0..n with bytes n+0..n+n of the hash,
             where n is RND_ENTROPY_THRESHOLD (currently 10).
     The kernel repeats the process, concatenating the results, until it has
     filled the seed.

     For each entropy source, the kernel estimates based on the previous sam-
     ples how much entropy the source is providing in each new sample.  The
     kernel maintains a count of the `amount of entropy' or `number of bits of
     entropy' in the pool.  Each sample `credits' to the amount of entropy.
     Every time the kernel draws a PRNG seed from the entropy pool, it
     `debits' from the amount of entropy.

     Every open from /dev/urandom seeds an independent PRNG which is reseeded
     at the convenience of the kernel after a billion requests for output.
     Reads from /dev/urandom never block, even if the kernel estimates its
     state to be totally predictable.

     Every open from /dev/random seeds an independent PRNG which is reseeded
     after every 16 bytes of output.  Reads from /dev/random block if the PRNG
     needs to be (re)seeded and the kernel's entropy estimate is too low.

     It is possible to fool the kernel's entropy estimator, in which case
     reads from /dev/random may return immediately even if the kernel is in a
     totally predictable state.

     Writes to /dev/random and /dev/urandom devices do not change the kernel's
     entropy estimate.

FILES
     /dev/random   Uniform random byte source.  May block.
     /dev/urandom  Uniform random byte source.  Never blocks.

SEE ALSO
     arc4random(3), rndctl(8), cprng(9)

     Elaine Barker and John Kelsey, Recommendation for Random Number
     Generation Using Deterministic Random Bit Generators, National Institute
     of Standards and Technology,
     http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf, January
     2012, NIST Special Publication 800-90A.

     Daniel J. Bernstein, Entropy Attacks!,
     http://blog.cr.yp.to/20140205-entropy.html, 2014-02-05.

     Nadia Heninger, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman,
     "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network
     Devices", Proceedings of the 21st USENIX Security Symposium, USENIX,
     https://www.usenix.org/conference/usenixsecurity12/technical-
     sessions/presentation/heninger https://factorable.net/, 205-220, August
     2012.

HISTORY
     The /dev/random and /dev/urandom devices first appeared in NetBSD 1.3.

AUTHORS
     The rnd subsystem was first implemented by Michael Graff
     <explorer@flame.org>, and was then largely rewritten by
     Thor Lancelot Simon <tls@NetBSD.org> with later contributions by
     Taylor R. Campbell <riastradh@NetBSD.org>.

BUGS
     There is no way to disable all entropy sources, in this and subsequent
     boots and no matter what USB devices you plug in against your mother's
     sage advice, in order to defend against the colluding hardware attack.

     The implementation confuses the number of bits in the entropy pool's
     physical representation, as a set of 32 128-bit LFSRs, with the number of
     bits of entropy that a system needs in order to be unpredictable, so even
     if entropy estimates were accurate and high, it takes unreasonably long
     for /dev/random to stop blocking.

     Many people are confused about what /dev/random and /dev/urandom mean.
     Unfortunately, no amount of software engineering can fix that.

ENTROPY ACCOUNTING
     The entropy accounting described here is not grounded in any cryptography
     theory.  It is done because it was always done, and because it gives peo-
     ple a warm fuzzy feeling about information theory.

     The folklore is that every n-bit output of /dev/random is not merely
     indistinguishable from uniform random to a computationally bounded
     attacker, but information-theoretically is independent and has n bits of
     entropy even to a computationally unbounded attacker -- that is, an
     attacker who can recover AES keys, compute SHA-1 preimages, etc.  This
     property is not provided, nor was it ever provided in any implementation
     of /dev/random known to the author.

     This property would require that, after each read, the system discard all
     measurements from hardware in the entropy pool and begin anew.  All work
     done to make the system unpredictable would be thrown out, and the system
     would immediately become predictable again.  Reverting the system to
     being predictable every time a process reads from /dev/random would give
     attackers a tremendous advantage in predicting future outputs, especially
     if they can fool the entropy estimator, e.g. by sending carefully timed
     network packets.

     If you filled your entropy pool by flipping a coin 256 times, you would
     have to flip it again 256 times for the next output, and so on.  In that
     case, if you really want information-theoretic guarantees, you might as
     well take /dev/random out of the picture and use your coin flips verba-
     tim.

     On the other hand, every cryptographic protocol in practice, including
     HTTPS, SSH, PGP, etc., expands short secrets deterministically into long
     streams of bits, and their security relies on conjectures that a computa-
     tionally bounded attacker cannot distinguish the long streams from uni-
     form random.  If we couldn't do that for /dev/random, it would be hope-
     less to assume we could for HTTPS, SSH, PGP, etc.

     History is littered with examples of broken entropy sources and failed
     system engineering for random number generators.  Nobody has ever
     reported distinguishing AES ciphertext from uniform random without side
     channels, nor reported computing SHA-1 preimages faster than brute force.
     The folklore information-theoretic defence against computationally
     unbounded attackers replaces system engineering that successfully defends
     against realistic threat models by imaginary theory that defends only
     against fantasy threat models.

NetBSD 7.0                     November 16, 2014                    NetBSD 7.0

You can also request any man page by name and (optionally) by section:

Command: 
Section: 
Architecture: 
Collection: 
 

Use the DEFAULT collection to view manual pages for third-party software.


©1994 Man-cgi 1.15, Panagiotis Christias <christia@softlab.ntua.gr>
©1996-2015 Modified for NetBSD by Kimmo Suominen