.\"	$NetBSD: rnd.4,v 1.40 2022/03/20 18:19:57 riastradh Exp $
.\"
.\" Copyright (c) 2014-2020 The NetBSD Foundation, Inc.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to The NetBSD Foundation
.\" by Taylor R. Campbell.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
.\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
.\" POSSIBILITY OF SUCH DAMAGE.
.\"
.Dd May 1, 2020
.Dt RND 4
.Os
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh NAME
.Nm rnd
.Nd random number generator
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh DESCRIPTION
The
.Pa /dev/random
and
.Pa /dev/urandom
devices generate bytes randomly with uniform distribution.
Every read from them is independent.
.Bl -tag -width /dev/urandom
.It Pa /dev/urandom
Never blocks.
.It Pa /dev/random
Sometimes blocks.
Will block early at boot if the system's state is known to be
predictable.
.El
.Pp
Applications should read from
.Pa /dev/urandom ,
or the
.Xr sysctl 7
variable
.Li kern.arandom ,
when they need randomly generated data, e.g. key material for
cryptography or seeds for simulations.
(The
.Xr sysctl 7
variable
.Li kern.arandom
is limited to 256 bytes per read, but is otherwise equivalent to
reading from
.Pa /dev/urandom
and always works even in a
.Xr chroot 8
environment without requiring a populated
.Pa /dev
tree and without opening a file descriptor, so
.Li kern.arandom
may be preferable to use in libraries.)
.Pp
Systems should be engineered to judiciously read at least once from
.Pa /dev/random
at boot before running any services that talk to the internet or
otherwise require cryptography, in order to avoid generating keys
predictably.
.Pa /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
.Pa /dev/random
can be especially frustrating.
.Pp
If interrupted by a signal, reads from either
.Pa /dev/random
or
.Pa /dev/urandom
may return short, so programs that handle signals must be prepared to
retry reads.
.Pp
Writing to either
.Pa /dev/random
or
.Pa /dev/urandom
influences subsequent output 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
.Pa /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:
.Bd -literal -offset abcd
% echo tthhhhhthhhththtthhhhthtththttth... > /dev/random
.Ed
.Pp
(Sequence generated from a genuine US quarter dollar, guaranteed
random.)
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh SECURITY MODEL
The
.Nm
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:
.Bl -bullet -offset abcd
.It
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.
.It
An attacker who has seen the entire state of the machine cannot predict
past outputs.
.El
.Pp
One
.Sq output
means a single read, no matter how short it is.
.Pp
.Sq Cannot predict
means it is conjectured of the cryptography in
.Fa /dev/random
that any computationally bounded attacker who tries to distinguish
outputs from uniform random cannot do more than negligibly better than
uniform random guessing.
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh ENTROPY
The operating system continuously 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
.Pa /dev/random
and
.Pa /dev/urandom .
.Pp
An attacker may be able to guess with nonnegligible chance of success
what your last keystroke was, but guessing every observation the
operating 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
.Em min-entropy ,
or
.Em entropy
for short in cryptography.
For example:
.Bl -bullet -offset abcd -compact
.It
A fair coin toss has one bit of entropy.
.It
A fair (six-sided) die roll has a little over 2.5 bits of entropy.
.It
A string of two independent fair coin tosses has two bits of entropy.
.It
The toss of a pair of fair coins that are glued together has one bit of
entropy.
.It
A uniform random distribution with
.Fa n
possibilities has log_2
.Fa n
bits of entropy.
.It
An utterance from an accounting troll who always says
.Sq nine
has zero bits of entropy.
.El
.Pp
Note that entropy is a property of an observable physical process, like
a coin toss, or of a state of knowledge about that physical process; it
is not a property of a specific sample obtained by observing it, like
the string
.Sq tthhhhht .
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.
.Pp
Hardware devices that the operating system monitors for observations
are called
.Em "entropy sources" ,
and the observations are combined into an
.Em "entropy pool" .
The
.Xr rndctl 8
command queries information about entropy sources and the entropy pool,
and can control which entropy sources the operating system uses or
ignores.
.Pp
256 bits of entropy is typically considered intractable to guess with
classical computers and with current models of the capabilities of
quantum computers.
.Pp
Systems with nonvolatile storage should store a secret from
.Pa /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 \(em
including the work its operator may have done to flip a coin! \(em can be
saved from one boot to the next, and so that newly installed systems
are not vulnerable to generating cryptographic keys predictably.
.Pp
The boot loaders in some
.Nx
ports support a command to load a seed from disk before the
kernel has started.
For those that don't, the
.Xr rndctl 8
command can do it once userland has started, for example by setting
.Dq Li random_seed=YES
in
.Pa /etc/rc.conf ,
which is enabled by default; see
.Xr rc.conf 5 .
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh LIMITATIONS
Some people worry about recovery from state compromise \(em that is,
ensuring that even if an attacker sees the entire state of the
operating system, then the attacker will be unable to predict any new
future outputs as long as the operating system gathers fresh entropy
quickly enough.
.Pp
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.
.Pp
The
.Nm
subsystem does
.Em not
automatically defend against hardware colluding with an attacker to
influence entropy sources based on the state of the operating system.
.Pp
For example, a PCI device or CPU instruction for random number
generation which has no side channel to an attacker other than the
.Pa /dev/urandom
device could be bugged to observe all other entropy sources, and to
carefully craft
.Sq observations
that cause a certain number of bits of
.Pa /dev/urandom
output to be ciphertext that either is predictable to an attacker or
conveys a message to an attacker.
.Pp
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.
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh IOCTLS
The
.Pa /dev/random
and
.Pa /dev/urandom
devices support a number of ioctls, defined in the
.In sys/rndio.h
header file, for querying and controlling the entropy pool.
.Pp
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.
.Pp
Several ioctls are concerned with particular entropy sources, described
by the following structure:
.Bd -literal
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 */
.Ed
.Pp
The following ioctls are supported:
.Bl -tag -width abcd
.It Dv RNDGETENTCNT Pq Vt uint32_t
Return the number of bits of entropy the system is estimated to have.
.It Dv RNDGETSRCNUM Pq Vt rndstat_t
.Bd -literal
typedef struct {
	uint32_t	start;
	uint32_t	count;
	rndsource_t	source[RND_MAXSTATCOUNT];
} rndstat_t;
.Ed
.Pp
Fill the
.Fa sources
array with information about up to
.Fa count
entropy sources, starting at
.Fa start .
The actual number of sources described is returned in
.Fa count .
At most
.Dv RND_MAXSTATCOUNT
sources may be requested at once.
.It Dv RNDGETSRCNAME Pq Vt rndstat_name_t
.Bd -literal
typedef struct {
	char		name[16];
	rndsource_t	source;
} rndstat_name_t;
.Ed
.Pp
Fill
.Fa source
with information about the entropy source named
.Fa name ,
or fail with
.Dv ENOENT
if there is none.
.It Dv RNDCTL Pq Vt rndctl_t
.Bd -literal
typedef struct {
	char		name[16];
	uint32_t	type;
	uint32_t	flags;
	uint32_t	mask;
} rndctl_t;
.Ed
.Pp
For each entropy source of the type
.Fa type ,
or if
.Fa type
is
.Li 0xff
then for the entropy source named
.Fa name ,
replace the flags in
.Fa mask
by
.Fa flags .
.It Dv RNDADDDATA Pq Vt rnddata_t
.Bd -literal
typedef struct {
	uint32_t	len;
	uint32_t	entropy;
	unsigned char	data[RND_SAVEWORDS * sizeof(uint32_t)];
} rnddata_t;
.Ed
.Pp
Feed
.Fa len
bytes of data to the entropy pool.
The sample is expected to have been drawn with at least
.Fa entropy
bits of entropy.
.Pp
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.
.It Dv RNDGETPOOLSTAT Pq Vt rndpoolstat_t
.Bd -literal
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;
.Ed
.Pp
Return various statistics about entropy.
.El
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh SYSCTLS
The following
.Xr sysctl 8
variables provided by
.Nm
can be set by privileged users:
.Bl -tag -width abcd
.It Dv kern.entropy.collection Pq Vt bool
(Default on.)
Enables entering data into the entropy pool.
If disabled, no new data can be entered into the entropy pool, whether
by device drivers, by writes to
.Pa /dev/random
or
.Pa /dev/urandom ,
or by the
.Dv RNDADDDATA
ioctl.
.It Dv kern.entropy.depletion Pq Vt bool
(Default off.)
Enables
.Sq entropy depletion ,
meaning that even after attaining full entropy, the kernel subtracts
the number of bits read out of the entropy pool from its estimate of
the system entropy.
This is not justified by modern cryptography \(em an adversary will
never guess the 256-bit secret in a Keccak sponge no matter how much
output from the sponge they see \(em but may be useful for testing.
.It Dv kern.entropy.consolidate Pq Vt int
Trigger for entropy consolidation: executing
.Dl # sysctl -w kern.entropy.consolidate=1
causes the system to consolidate pending entropy from per-CPU pools
into the global pool, and waits until done.
.El
.Pp
The following read-only
.Xr sysctl 8
variables provide information to privileged users about the state of
the entropy pool:
.Bl -tag -width abcd
.It Dv kern.entropy.needed Pq Vt unsigned int
Number of bits of entropy the system is waiting for in the global pool
before reads from
.Pa /dev/random
will return without blocking.
When zero, the system is considered to have full entropy.
.It Dv kern.entropy.pending Pq Vt unsigned int
Number of bits of entropy pending in per-CPU pools.
This is the amount of entropy that will be contributed to the global
pool at the next consolidation, such as from triggering
.Dv kern.entropy.consolidate .
.It Dv kern.entropy.epoch Pq Vt unsigned int
Number of times system has reached full entropy, or entropy has been
consolidated with
.Dv kern.entropy.consolidate ,
as an unsigned 32-bit integer.
Consulted inside the kernel by subsystems such as
.Xr cprng 9
to decide whether to reseed.
Initially set to 2^32 \- 1
.Pq i.e., Li "(unsigned)\-1"
meaning the system has never reached full entropy and the entropy has
never been consolidated; never again set to 2^32 \- 1.
Never zero, so applications can initialize a cache of the epoch to zero
to ensure they reseed the next time they check whether it is different
from the stored epoch.
.El
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh IMPLEMENTATION NOTES
(This section describes the current implementation of the
.Nm
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 behaviour of the
.Pa /dev/random
and
.Pa /dev/urandom
devices.)
.Pp
Device drivers gather samples from entropy sources and absorb them into
a collection of per-CPU Keccak sponges called
.Sq entropy pools
using the
.Xr rnd 9
kernel API.
The device driver furnishes an estimate for the entropy of the sampling
process, under the assumption that each sample is independent.
When the estimate of entropy pending among the per-CPU entropy pools
reaches a threshold of 256 bits, the entropy is drawn from the per-CPU
pools and consolidated into a global pool.
Keys for
.Pa /dev/random ,
.Pa /dev/urandom ,
.Li kern.arandom ,
and the in-kernel
.Xr cprng 9
subsystem are extracted from the global pool.
.Pp
Early after boot, before CPUs have been detected, device drivers
instead enter directly into the global pool.
If anything in the system extracts data from the pool before the
threshold has been reached at least once, the system will print a
warning to the console and reset the entropy estimate to zero.
The reason for resetting the entropy estimate to zero in this case is
that an adversary who can witness output from the pool with partial
entropy \(em say, 32 bits \(em can undergo a feasible brute force
search to ascertain the complete state of the pool; as such, the
entropy of the adversary's state of knowledge about the pool is zero.
.Pp
If the operator is confident that the drivers' estimates of the entropy
of the sampling processes are too conservative, the operator can issue
.Dl # sysctl -w kern.entropy.consolidate=1
to force consolidation into the global pool.
The operator can also fool the system into thinking it has more entropy
than it does by feeding data from
.Pa /dev/urandom
into
.Pa /dev/random ,
but this voids the security model and should be limited to testing
purposes.
.Pp
.Em Short
reads from
.Pa /dev/urandom
are served by a persistent per-CPU Hash_DRBG instance that is
reseeded from the entropy pool after any entropy consolidation.
Reads from
.Pa /dev/random
and
.Em long
reads from
.Pa /dev/urandom
are served by a temporary Hash_DRBG seeded from the entropy pool on
each read.
.Pp
When
.Sq entropy depletion
is enabled by
setting the sysctl variable
.Dv kern.entropy.depletion Ns Li \&=1 ,
every read from
.Pa /dev/random
is limited to 256 bits, since reading more than that would nearly
always block again.
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh FILES
.Bl -tag -width /dev/urandom -compact
.It Pa /dev/random
Uniform random byte source.
May block.
.It Pa /dev/urandom
Uniform random byte source.
Never blocks.
.El
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh DIAGNOSTICS
The
.Nm
subsystem may print the following warnings to the console likely
indicating security issues:
.Bl -diag -offset indent
.It WARNING: system needs entropy for security; see entropy(7)
A process tried to draw from the entropy pool before enough inputs from
reliable entropy sources have been entered.
.Pp
The entropy may be low enough that an adversary who sees the output
could guess the state of the pool by brute force, so in this event the
system resets its estimate of entropy to none.
.Pp
This message is rate-limited to happen no more often than once per
minute, so if you want to make sure it is gone you should consult
.Dv kern.entropy.needed
to confirm it is zero.
.El
.Pp
The
.Nm
subsystem may print any of various messages about obtaining an entropy
seed from the bootloader to diagnose saving and loading seeds on disk:
.Bl -diag -offset indent
.It entropy: entering seed from bootloader with N bits of entropy
The bootloader provided an entropy seed to the kernel, which recorded
an estimate of N bits of entropy in the process that generated it.
.It entropy: no seed from bootloader
The bootloader did not provide an entropy seed to the kernel before
starting the kernel.
This does not necessarily indicate a problem; not all bootloaders
support the option, and the
.Xr rc.conf 5
setting
.Li random_seed=YES
can serve instead.
.It entropy: invalid seed length N, expected sizeof(rndsave_t) = M
The bootloader provided an entropy seed of the wrong size to the
kernel.
This may indicate a bug in
.Xr rndctl 8 .
The seed will be ignored.
.It entropy: invalid seed checksum
The entropy seed provided by the bootloader was malformed.
The seed will be entered into the entropy pool, but it will be
considered to contribute no entropy.
.It entropy: double-seeded by bootloader
A buggy bootloader tried to provide an entropy seed more than once to
the kernel.
Subsequent seeds will be entered into the entropy pool, but they will
be considered to contribute no entropy.
.It entropy: ready
The system has full entropy for the first time.
.El
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh SEE ALSO
.Xr arc4random 3 ,
.Xr entropy 7 ,
.Xr rndctl 8 ,
.Xr cprng 9 ,
.Xr rnd 9
.Rs
.%A Elaine Barker
.%A John Kelsey
.%T Recommendation for Random Number Generation Using Deterministic Random Bit Generators
.%D June 2015
.%Q United States Department of Commerce
.%I National Institute of Standards and Technology
.%O NIST Special Publication 800-90A, Revision 1
.%U https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final
.Re
.Rs
.%A Meltem S\(:onmez Turan
.%A Elaine Barker
.%A John Kelsey
.%A Kerry A. McKay
.%A Mary L. Baish
.%A Mike Boyle
.%T Recommendations for the Entropy Sources Used for Random Bit Generation
.%D January 2018
.%Q United States Department of Commerce
.%I National Institute of Standards and Technology
.%O NIST Special Publication 800-90B
.%U https://csrc.nist.gov/publications/detail/sp/800-90b/final
.Re
.Rs
.%A Daniel J. Bernstein
.%T Entropy Attacks!
.%D 2014-02-05
.%U http://blog.cr.yp.to/20140205-entropy.html
.Re
.Rs
.%A Nadia Heninger
.%A Zakir Durumeric
.%A Eric Wustrow
.%A J. Alex Halderman
.%T Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices
.%B Proceedings of the 21st USENIX Security Symposium
.%I USENIX
.%D August 2012
.%P 205-220
.%U https://www.usenix.org/conference/usenixsecurity12/technical-sessions/presentation/heninger
.%U https://factorable.net/
.Re
.Rs
.%A Edwin T. Jaynes
.%B Probability Theory: The Logic of Science
.%I Cambridge University Press
.%D 2003
.%U https://bayes.wustl.edu/
.Re
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh HISTORY
The
.Pa /dev/random
and
.Pa /dev/urandom
devices first appeared in
.Nx 1.3 .
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh AUTHORS
.An -nosplit
The
.Nm
subsystem was first implemented by
.An Michael Graff Aq Mt explorer@flame.org ,
was then largely rewritten by
.An Thor Lancelot Simon Aq Mt tls@NetBSD.org ,
and was most recently largely rewritten by
.An Taylor R. Campbell Aq Mt riastradh@NetBSD.org .
.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh BUGS
Many people are confused about what
.Pa /dev/random
and
.Pa /dev/urandom
mean.
Unfortunately, no amount of software engineering can fix that.