Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sys/sys Rewrite entropy subsystem.
details: https://anonhg.NetBSD.org/src/rev/70734ac83b95
branches: trunk
changeset: 931744:70734ac83b95
user: riastradh <riastradh%NetBSD.org@localhost>
date: Thu Apr 30 03:28:18 2020 +0000
description:
Rewrite entropy subsystem.
Primary goals:
1. Use cryptography primitives designed and vetted by cryptographers.
2. Be honest about entropy estimation.
3. Propagate full entropy as soon as possible.
4. Simplify the APIs.
5. Reduce overhead of rnd_add_data and cprng_strong.
6. Reduce side channels of HWRNG data and human input sources.
7. Improve visibility of operation with sysctl and event counters.
Caveat: rngtest is no longer used generically for RND_TYPE_RNG
rndsources. Hardware RNG devices should have hardware-specific
health tests. For example, checking for two repeated 256-bit outputs
works to detect AMD's 2019 RDRAND bug. Not all hardware RNGs are
necessarily designed to produce exactly uniform output.
ENTROPY POOL
- A Keccak sponge, with test vectors, replaces the old LFSR/SHA-1
kludge as the cryptographic primitive.
- `Entropy depletion' is available for testing purposes with a sysctl
knob kern.entropy.depletion; otherwise it is disabled, and once the
system reaches full entropy it is assumed to stay there as far as
modern cryptography is concerned.
- No `entropy estimation' based on sample values. Such `entropy
estimation' is a contradiction in terms, dishonest to users, and a
potential source of side channels. It is the responsibility of the
driver author to study the entropy of the process that generates
the samples.
- Per-CPU gathering pools avoid contention on a global queue.
- Entropy is occasionally consolidated into global pool -- as soon as
it's ready, if we've never reached full entropy, and with a rate
limit afterward. Operators can force consolidation now by running
sysctl -w kern.entropy.consolidate=1.
- rndsink(9) API has been replaced by an epoch counter which changes
whenever entropy is consolidated into the global pool.
. Usage: Cache entropy_epoch() when you seed. If entropy_epoch()
has changed when you're about to use whatever you seeded, reseed.
. Epoch is never zero, so initialize cache to 0 if you want to reseed
on first use.
. Epoch is -1 iff we have never reached full entropy -- in other
words, the old rnd_initial_entropy is (entropy_epoch() != -1) --
but it is better if you check for changes rather than for -1, so
that if the system estimated its own entropy incorrectly, entropy
consolidation has the opportunity to prevent future compromise.
- Sysctls and event counters provide operator visibility into what's
happening:
. kern.entropy.needed - bits of entropy short of full entropy
. kern.entropy.pending - bits known to be pending in per-CPU pools,
can be consolidated with sysctl -w kern.entropy.consolidate=1
. kern.entropy.epoch - number of times consolidation has happened,
never 0, and -1 iff we have never reached full entropy
CPRNG_STRONG
- A cprng_strong instance is now a collection of per-CPU NIST
Hash_DRBGs. There are only two in the system: user_cprng for
/dev/urandom and sysctl kern.?random, and kern_cprng for kernel
users which may need to operate in interrupt context up to IPL_VM.
(Calling cprng_strong in interrupt context does not strike me as a
particularly good idea, so I added an event counter to see whether
anything actually does.)
- Event counters provide operator visibility into when reseeding
happens.
INTEL RDRAND/RDSEED, VIA C3 RNG (CPU_RNG)
- Unwired for now; will be rewired in a subsequent commit.
diffstat:
common/lib/libc/Makefile.inc | 3 +-
distrib/sets/lists/comp/mi | 8 +-
share/man/man4/rnd.4 | 361 +++-
share/man/man9/Makefile | 4 +-
share/man/man9/rnd.9 | 434 +++--
share/man/man9/rndsink.9 | 147 -
sys/arch/amd64/conf/RNDVERBOSE | 24 -
sys/dev/files.dev | 4 +-
sys/dev/random.c | 437 +++++
sys/dev/rnd_private.h | 70 -
sys/dev/rndpseudo.c | 578 -------
sys/kern/files.kern | 6 +-
sys/kern/init_main.c | 20 +-
sys/kern/kern_entropy.c | 2102 +++++++++++++++++++++++++++
sys/kern/kern_rndpool.c | 289 ---
sys/kern/kern_rndq.c | 1727 ----------------------
sys/kern/kern_rndsink.c | 254 ---
sys/kern/subr_autoconf.c | 9 +-
sys/kern/subr_cprng.c | 733 +++------
sys/kern/subr_prf.c | 78 +-
sys/lib/libkern/Makefile.libkern | 5 +-
sys/lib/libkern/entpool.c | 754 +++++++++
sys/lib/libkern/entpool.h | 79 +
sys/rump/dev/lib/librnd/Makefile | 4 +-
sys/rump/dev/lib/librnd/rnd_component.c | 33 +-
sys/rump/librump/rumpkern/Makefile.rumpkern | 6 +-
sys/rump/librump/rumpkern/emul.c | 6 +-
sys/rump/librump/rumpkern/rump.c | 9 +-
sys/sys/cprng.h | 14 +-
sys/sys/entropy.h | 59 +
sys/sys/rndpool.h | 38 +-
sys/sys/rndsink.h | 53 -
sys/sys/rndsource.h | 110 +-
33 files changed, 4258 insertions(+), 4200 deletions(-)
diffs (truncated from 9214 to 300 lines):
diff -r d1617317bc02 -r 70734ac83b95 common/lib/libc/Makefile.inc
--- a/common/lib/libc/Makefile.inc Thu Apr 30 03:27:15 2020 +0000
+++ b/common/lib/libc/Makefile.inc Thu Apr 30 03:28:18 2020 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.inc,v 1.19 2019/06/04 15:07:55 hannken Exp $
+# $NetBSD: Makefile.inc,v 1.20 2020/04/30 03:28:18 riastradh Exp $
.include <bsd.own.mk>
@@ -45,3 +45,4 @@
.if defined(COMMON_ARCHSUBDIR)
CPPFLAGS+=-I${COMMON_ARCHDIR}/string
.endif
+CPPFLAGS+=-I${COMMON_DIR}/hash/sha3
diff -r d1617317bc02 -r 70734ac83b95 distrib/sets/lists/comp/mi
--- a/distrib/sets/lists/comp/mi Thu Apr 30 03:27:15 2020 +0000
+++ b/distrib/sets/lists/comp/mi Thu Apr 30 03:28:18 2020 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.2322 2020/04/26 18:53:31 thorpej Exp $
+# $NetBSD: mi,v 1.2323 2020/04/30 03:28:18 riastradh Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
./etc/mtree/set.comp comp-sys-root
@@ -11814,7 +11814,7 @@
./usr/share/man/cat9/rnd_attach_source.0 comp-sys-catman .cat
./usr/share/man/cat9/rnd_detach_source.0 comp-sys-catman .cat
./usr/share/man/cat9/rnd_extract_data.0 comp-sys-catman .cat
-./usr/share/man/cat9/rndsink.0 comp-sys-catman .cat
+./usr/share/man/cat9/rndsink.0 comp-obsolete obsolete
./usr/share/man/cat9/rootconf.0 comp-sys-catman .cat
./usr/share/man/cat9/round_page.0 comp-sys-catman .cat
./usr/share/man/cat9/rounddown.0 comp-sys-catman .cat
@@ -19744,7 +19744,7 @@
./usr/share/man/html9/rnd_attach_source.html comp-sys-htmlman html
./usr/share/man/html9/rnd_detach_source.html comp-sys-htmlman html
./usr/share/man/html9/rnd_extract_data.html comp-sys-htmlman html
-./usr/share/man/html9/rndsink.html comp-sys-htmlman html
+./usr/share/man/html9/rndsink.html comp-obsolete obsolete
./usr/share/man/html9/rootconf.html comp-sys-htmlman html
./usr/share/man/html9/round_page.html comp-sys-htmlman html
./usr/share/man/html9/rounddown.html comp-sys-htmlman html
@@ -27855,7 +27855,7 @@
./usr/share/man/man9/rnd_attach_source.9 comp-sys-man .man
./usr/share/man/man9/rnd_detach_source.9 comp-sys-man .man
./usr/share/man/man9/rnd_extract_data.9 comp-sys-man .man
-./usr/share/man/man9/rndsink.9 comp-sys-man .man
+./usr/share/man/man9/rndsink.9 comp-obsolete obsolete
./usr/share/man/man9/rootconf.9 comp-sys-man .man
./usr/share/man/man9/round_page.9 comp-sys-man .man
./usr/share/man/man9/rounddown.9 comp-sys-man .man
diff -r d1617317bc02 -r 70734ac83b95 share/man/man4/rnd.4
--- a/share/man/man4/rnd.4 Thu Apr 30 03:27:15 2020 +0000
+++ b/share/man/man4/rnd.4 Thu Apr 30 03:28:18 2020 +0000
@@ -1,6 +1,6 @@
-.\" $NetBSD: rnd.4,v 1.28 2019/09/04 05:37:06 wiz Exp $
+.\" $NetBSD: rnd.4,v 1.29 2020/04/30 03:28:18 riastradh Exp $
.\"
-.\" Copyright (c) 2014 The NetBSD Foundation, Inc.
+.\" Copyright (c) 2014-2019 The NetBSD Foundation, Inc.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to The NetBSD Foundation
@@ -30,9 +30,11 @@
.Dd September 3, 2019
.Dt RND 4
.Os
+.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh NAME
.Nm rnd
.Nd random number generator
+.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh DESCRIPTION
The
.Pa /dev/random
@@ -93,6 +95,7 @@
.Pp
(Sequence generated from a genuine US quarter dollar, guaranteed
random.)
+.\"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
.Sh SECURITY MODEL
The
.Nm
@@ -119,6 +122,7 @@
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
@@ -163,8 +167,11 @@
has zero bits of entropy.
.El
.Pp
-Note that entropy is a property of an observable physical process, not
-of a particular sample obtained by observing it.
+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.
@@ -199,11 +206,12 @@
For those that don't, the
.Xr rndctl 8
command can do it once userland has started, for example by setting
-.Dq Va random_seed=YES
+.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
@@ -238,6 +246,7 @@
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
@@ -383,6 +392,74 @@
.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
@@ -394,84 +471,71 @@
.Pa /dev/urandom
devices.)
.Pp
-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.
-.\" XXX Finish this description so it is implementable.
-.Pp
-When a user process opens
-.Pa /dev/random
-or
-.Pa /dev/urandom
-and first reads from it, the kernel draws from the entropy pool to seed
-a cryptographic pseudorandom number generator, the NIST Hash_DRBG
-(hash-based deterministic random bit generator) with SHA-256 as the
-hash function, and uses that to generate data.
+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 ,
+and the in-kernel
+.Xr cprng 9
+subsystem are extracted from the global pool.
.Pp
-To draw a seed from the entropy pool, the kernel
-.Bl -bullet -offset abcd -compact
-.It
-computes the SHA-1 hash of the entropy pool,
-.It
-feeds the SHA-1 hash word-by-word back into the entropy pool like an
-entropy source, and
-.It
-yields the xor of bytes
-.Pf 0.. Fa n
-with bytes
-.Fa n Ns +0.. Ns Fa n Ns Pf + Fa n
-of the hash, where
-.Fa n
-is
-.Dv RND_ENTROPY_THRESHOLD
-(currently 10).
-.El
-The kernel repeats the process, concatenating the results, until it has
-filled the seed.
+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
-For each entropy source, the kernel estimates based on the previous
-samples how much entropy the source is providing in each new sample.
-The kernel maintains a count of the
-.Sq amount of entropy
-or
-.Sq number of bits of entropy
-in the pool.
-Each sample
-.Sq credits
-to the amount of entropy.
-Every time the kernel draws a PRNG seed from the entropy pool, it
-.Sq debits
-from the amount of entropy.
+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 ready 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
-Every open from
-.Pa /dev/urandom
-seeds an independent PRNG which is reseeded at the convenience of the
-kernel after a billion requests for output.
-Reads from
+.Em Short
+reads from
.Pa /dev/urandom
Home |
Main Index |
Thread Index |
Old Index