svn commit: r366620 - in head/sys: conf dev/random/fenestrasX
Conrad Meyer
cem at FreeBSD.org
Sat Oct 10 21:46:01 UTC 2020
Author: cem
Date: Sat Oct 10 21:45:59 2020
New Revision: 366620
URL: https://svnweb.freebsd.org/changeset/base/366620
Log:
Add "Fenestras X" alternative /dev/random implementation
Fortuna remains the default; no functional change to GENERIC.
Big picture:
- Scalable entropy generation with per-CPU, buffered local generators.
- "Push" system for reseeding child generators when root PRNG is
reseeded. (Design can be extended to arc4random(9) and userspace
generators.)
- Similar entropy pooling system to Fortuna, but starts with a single
pool to quickly bootstrap as much entropy as possible early on.
- Reseeding from pooled entropy based on time schedule. The time
interval starts small and grows exponentially until reaching a cap.
Again, the goal is to have the RNG state depend on as much entropy as
possible quickly, but still periodically incorporate new entropy for
the same reasons as Fortuna.
Notable design choices in this implementation that differ from those
specified in the whitepaper:
- Blake2B instead of SHA-2 512 for entropy pooling
- Chacha20 instead of AES-CTR DRBG
- Initial seeding. We support more platforms and not all of them use
loader(8). So we have to grab the initial entropy sources in kernel
mode instead, as much as possible. Fortuna didn't have any mechanism
for this aside from the special case of loader-provided previous-boot
entropy, so most of these sources remain TODO after this commit.
Reviewed by: markm
Approved by: csprng (markm)
Differential Revision: https://reviews.freebsd.org/D22837
Added:
head/sys/dev/random/fenestrasX/
head/sys/dev/random/fenestrasX/fx_brng.c (contents, props changed)
head/sys/dev/random/fenestrasX/fx_brng.h (contents, props changed)
head/sys/dev/random/fenestrasX/fx_hash.h (contents, props changed)
head/sys/dev/random/fenestrasX/fx_main.c (contents, props changed)
head/sys/dev/random/fenestrasX/fx_pool.c (contents, props changed)
head/sys/dev/random/fenestrasX/fx_pool.h (contents, props changed)
head/sys/dev/random/fenestrasX/fx_priv.h (contents, props changed)
head/sys/dev/random/fenestrasX/fx_rng.c (contents, props changed)
head/sys/dev/random/fenestrasX/fx_rng.h (contents, props changed)
Modified:
head/sys/conf/NOTES
head/sys/conf/files
head/sys/conf/options
Modified: head/sys/conf/NOTES
==============================================================================
--- head/sys/conf/NOTES Sat Oct 10 18:22:12 2020 (r366619)
+++ head/sys/conf/NOTES Sat Oct 10 21:45:59 2020 (r366620)
@@ -2772,6 +2772,8 @@ options RCTL
options MAXFILES=999
# Random number generator
+# Alternative algorithm.
+#options RANDOM_FENESTRASX
# Allow the CSPRNG algorithm to be loaded as a module.
#options RANDOM_LOADABLE
# Select this to allow high-rate but potentially expensive
Modified: head/sys/conf/files
==============================================================================
--- head/sys/conf/files Sat Oct 10 18:22:12 2020 (r366619)
+++ head/sys/conf/files Sat Oct 10 21:45:59 2020 (r366620)
@@ -722,7 +722,7 @@ contrib/zstd/lib/decompress/zstd_decompress_block.c op
compile-with "${ZSTD_C} ${ZSTD_DECOMPRESS_BLOCK_FLAGS}"
contrib/zstd/lib/decompress/huf_decompress.c optional zstdio compile-with ${ZSTD_C}
# Blake 2
-contrib/libb2/blake2b-ref.c optional crypto | ipsec | ipsec_support \
+contrib/libb2/blake2b-ref.c optional crypto | ipsec | ipsec_support | !random_loadable random_fenestrasx \
compile-with "${NORMAL_C} -I$S/crypto/blake2 -Wno-cast-qual -DSUFFIX=_ref -Wno-unused-function"
contrib/libb2/blake2s-ref.c optional crypto | ipsec | ipsec_support \
compile-with "${NORMAL_C} -I$S/crypto/blake2 -Wno-cast-qual -DSUFFIX=_ref -Wno-unused-function"
@@ -2820,7 +2820,14 @@ rt2860.fw optional rt2860fw | ralfw \
dev/random/random_infra.c standard
dev/random/random_harvestq.c standard
dev/random/randomdev.c optional !random_loadable
-dev/random/fortuna.c optional !random_loadable
+dev/random/fenestrasX/fx_brng.c optional !random_loadable random_fenestrasx
+dev/random/fenestrasX/fx_main.c optional !random_loadable random_fenestrasx \
+ compile-with "${NORMAL_C} -I$S/crypto/blake2"
+dev/random/fenestrasX/fx_pool.c optional !random_loadable random_fenestrasx \
+ compile-with "${NORMAL_C} -I$S/crypto/blake2"
+dev/random/fenestrasX/fx_rng.c optional !random_loadable random_fenestrasx \
+ compile-with "${NORMAL_C} -I$S/crypto/blake2"
+dev/random/fortuna.c optional !random_loadable !random_fenestrasx
dev/random/hash.c optional !random_loadable
dev/rccgpio/rccgpio.c optional rccgpio gpio
dev/re/if_re.c optional re
Modified: head/sys/conf/options
==============================================================================
--- head/sys/conf/options Sat Oct 10 18:22:12 2020 (r366619)
+++ head/sys/conf/options Sat Oct 10 21:45:59 2020 (r366620)
@@ -966,6 +966,8 @@ RACCT_DEFAULT_TO_DISABLED opt_global.h
RCTL opt_global.h
# Random number generator(s)
+# Alternative RNG algorithm.
+RANDOM_FENESTRASX opt_global.h
# With this, no entropy processor is loaded, but the entropy
# harvesting infrastructure is present. This means an entropy
# processor may be loaded as a module.
Added: head/sys/dev/random/fenestrasX/fx_brng.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/sys/dev/random/fenestrasX/fx_brng.c Sat Oct 10 21:45:59 2020 (r366620)
@@ -0,0 +1,295 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * Copyright (c) 2019 Conrad Meyer <cem at FreeBSD.org>
+ *
+ * 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 AUTHOR 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 AUTHOR 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.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <sys/param.h>
+#include <sys/fail.h>
+#include <sys/limits.h>
+#include <sys/lock.h>
+#include <sys/kernel.h>
+#include <sys/malloc.h>
+#include <sys/mutex.h>
+#include <sys/random.h>
+#include <sys/sdt.h>
+#include <sys/sysctl.h>
+#include <sys/systm.h>
+
+#include <machine/cpu.h>
+
+#include <dev/random/randomdev.h>
+#include <dev/random/random_harvestq.h>
+#include <dev/random/uint128.h>
+
+#include <dev/random/fenestrasX/fx_brng.h>
+#include <dev/random/fenestrasX/fx_priv.h>
+#include <dev/random/fenestrasX/fx_rng.h>
+
+/*
+ * Implementation of a buffered RNG, described in § 1.2-1.4 of the whitepaper.
+ */
+
+/*
+ * Initialize a buffered rng instance (either the static root instance, or a
+ * per-cpu instance on the heap. Both should be zero initialized before this
+ * routine.
+ */
+void
+fxrng_brng_init(struct fxrng_buffered_rng *rng)
+{
+ fxrng_rng_init(&rng->brng_rng, rng == &fxrng_root);
+
+ /* I.e., the buffer is empty. */
+ rng->brng_avail_idx = sizeof(rng->brng_buffer);
+
+ /*
+ * It is fine and correct for brng_generation and brng_buffer to be
+ * zero values.
+ *
+ * brng_prf and brng_generation must be initialized later.
+ * Initialization is special for the root BRNG. PCPU child instances
+ * use fxrng_brng_produce_seed_data_internal() below.
+ */
+}
+
+/*
+ * Directly reseed the root BRNG from a first-time entropy source,
+ * incorporating the existing BRNG state. The main motivation for doing so "is
+ * to ensure that as soon as an entropy source produces data, PRNG output
+ * depends on the data from that source." (§ 3.1)
+ *
+ * The root BRNG is locked on entry and initial keying (brng_generation > 0)
+ * has already been performed. The root BRNG is unlocked on return.
+ */
+void
+fxrng_brng_src_reseed(const struct harvest_event *event)
+{
+ struct fxrng_buffered_rng *rng;
+
+ rng = &fxrng_root;
+ FXRNG_BRNG_ASSERT(rng);
+ ASSERT_DEBUG(rng->brng_generation > 0, "root RNG not seeded");
+
+ fxrng_rng_src_reseed(&rng->brng_rng, event);
+ FXRNG_BRNG_ASSERT(rng);
+
+ /*
+ * Bump root generation (which is costly) to force downstream BRNGs to
+ * reseed and quickly incorporate the new entropy. The intuition is
+ * that this tradeoff is worth it because new sources show up extremely
+ * rarely (limiting cost) and if they can contribute any entropy to a
+ * weak state, we want to propagate it to all generators ASAP.
+ */
+ rng->brng_generation++;
+ atomic_store_rel_64(&fxrng_root_generation, rng->brng_generation);
+ FXRNG_BRNG_UNLOCK(rng);
+}
+
+/*
+ * Reseed a brng from some amount of pooled entropy (determined in fx_pool.c by
+ * fxent_timer_reseed_npools). For initial seeding, we pool entropy in a
+ * single pool and use this API as well (fxrng_alg_seeded).
+ */
+void
+fxrng_brng_reseed(const void *entr, size_t sz)
+{
+ struct fxrng_buffered_rng *rng;
+
+ rng = &fxrng_root;
+ FXRNG_BRNG_LOCK(rng);
+
+ fxrng_rng_reseed(&rng->brng_rng, (rng->brng_generation > 0), entr, sz);
+ FXRNG_BRNG_ASSERT(rng);
+
+ rng->brng_generation++;
+ atomic_store_rel_64(&fxrng_root_generation, rng->brng_generation);
+ FXRNG_BRNG_UNLOCK(rng);
+}
+
+/*
+ * Grab some bytes off an initialized, current generation RNG.
+ *
+ * (Does not handle reseeding if our generation is stale.)
+ *
+ * Locking protocol is a bit odd. The RNG is locked on entrance, but the lock
+ * is dropped on exit. This avoids holding a lock during expensive and slow
+ * RNG generation.
+ */
+static void
+fxrng_brng_getbytes_internal(struct fxrng_buffered_rng *rng, void *buf,
+ size_t nbytes)
+{
+
+ FXRNG_BRNG_ASSERT(rng);
+
+ /* Make the zero request impossible for the rest of the logic. */
+ if (__predict_false(nbytes == 0)) {
+ FXRNG_BRNG_UNLOCK(rng);
+ goto out;
+ }
+
+ /* Fast/easy case: Use some bytes from the buffer. */
+ if (rng->brng_avail_idx + nbytes <= sizeof(rng->brng_buffer)) {
+ memcpy(buf, &rng->brng_buffer[rng->brng_avail_idx], nbytes);
+ explicit_bzero(&rng->brng_buffer[rng->brng_avail_idx], nbytes);
+ rng->brng_avail_idx += nbytes;
+ FXRNG_BRNG_UNLOCK(rng);
+ goto out;
+ }
+
+ /* Buffer case: */
+ if (nbytes < sizeof(rng->brng_buffer)) {
+ size_t rem;
+
+ /* Drain anything left in the buffer first. */
+ if (rng->brng_avail_idx < sizeof(rng->brng_buffer)) {
+ rem = sizeof(rng->brng_buffer) - rng->brng_avail_idx;
+ ASSERT_DEBUG(nbytes > rem, "invariant");
+
+ memcpy(buf, &rng->brng_buffer[rng->brng_avail_idx], rem);
+
+ buf = (uint8_t*)buf + rem;
+ nbytes -= rem;
+ ASSERT_DEBUG(nbytes != 0, "invariant");
+ }
+
+ /*
+ * Partial fill from first buffer, have to rekey and generate a
+ * new buffer to do the rest.
+ */
+ fxrng_rng_genrandom_internal(&rng->brng_rng, rng->brng_buffer,
+ sizeof(rng->brng_buffer), false);
+ FXRNG_BRNG_ASSERT(rng);
+ rng->brng_avail_idx = 0;
+
+ memcpy(buf, &rng->brng_buffer[rng->brng_avail_idx], nbytes);
+ explicit_bzero(&rng->brng_buffer[rng->brng_avail_idx], nbytes);
+ rng->brng_avail_idx += nbytes;
+ FXRNG_BRNG_UNLOCK(rng);
+ goto out;
+ }
+
+ /* Large request; skip the buffer. */
+ fxrng_rng_genrandom_internal(&rng->brng_rng, buf, nbytes, true);
+
+out:
+ FXRNG_BRNG_ASSERT_NOT(rng);
+ return;
+}
+
+/*
+ * API to get a new key for a downstream RNG. Returns the new key in 'buf', as
+ * well as the generator's reseed_generation.
+ *
+ * 'rng' is locked on entry and unlocked on return.
+ *
+ * Only valid after confirming the caller's seed version or reseed_generation
+ * matches roots (or we are root). (For now, this is only used to reseed the
+ * per-CPU generators from root.)
+ */
+void
+fxrng_brng_produce_seed_data_internal(struct fxrng_buffered_rng *rng,
+ void *buf, size_t keysz, uint64_t *seed_generation)
+{
+ FXRNG_BRNG_ASSERT(rng);
+ ASSERT_DEBUG(keysz == FX_CHACHA20_KEYSIZE, "keysz: %zu", keysz);
+
+ *seed_generation = rng->brng_generation;
+ fxrng_brng_getbytes_internal(rng, buf, keysz);
+ FXRNG_BRNG_ASSERT_NOT(rng);
+}
+
+/*
+ * Read from an allocated and initialized buffered BRNG. This a high-level
+ * API, but doesn't handle PCPU BRNG allocation.
+ *
+ * BRNG is locked on entry. It is unlocked on return.
+ */
+void
+fxrng_brng_read(struct fxrng_buffered_rng *rng, void *buf, size_t nbytes)
+{
+ uint8_t newkey[FX_CHACHA20_KEYSIZE];
+
+ FXRNG_BRNG_ASSERT(rng);
+
+ /* Fast path: there hasn't been a global reseed since last read. */
+ if (rng->brng_generation == atomic_load_acq_64(&fxrng_root_generation))
+ goto done_reseeding;
+
+ ASSERT(rng != &fxrng_root, "root rng inconsistent seed version");
+
+ /*
+ * Slow path: We need to rekey from the parent BRNG to incorporate new
+ * entropy material.
+ *
+ * Lock order is always root -> percpu.
+ */
+ FXRNG_BRNG_UNLOCK(rng);
+ FXRNG_BRNG_LOCK(&fxrng_root);
+ FXRNG_BRNG_LOCK(rng);
+
+ /*
+ * If we lost the reseeding race when the lock was dropped, don't
+ * duplicate work.
+ */
+ if (__predict_false(rng->brng_generation ==
+ atomic_load_acq_64(&fxrng_root_generation))) {
+ FXRNG_BRNG_UNLOCK(&fxrng_root);
+ goto done_reseeding;
+ }
+
+ fxrng_brng_produce_seed_data_internal(&fxrng_root, newkey,
+ sizeof(newkey), &rng->brng_generation);
+
+ FXRNG_BRNG_ASSERT_NOT(&fxrng_root);
+ FXRNG_BRNG_ASSERT(rng);
+
+ fxrng_rng_setkey(&rng->brng_rng, newkey, sizeof(newkey));
+ explicit_bzero(newkey, sizeof(newkey));
+
+ /*
+ * A reseed invalidates any previous buffered contents. Here, we
+ * forward the available index to the end of the buffer, i.e., empty.
+ * Requests that would use the buffer (< 128 bytes) will refill its
+ * contents on demand.
+ *
+ * It is explicitly ok that we do not zero out any remaining buffer
+ * bytes; they will never be handed out to callers, and they reveal
+ * nothing about the reseeded key (which came from the root BRNG).
+ * (§ 1.3)
+ */
+ rng->brng_avail_idx = sizeof(rng->brng_buffer);
+
+done_reseeding:
+ if (rng != &fxrng_root)
+ FXRNG_BRNG_ASSERT_NOT(&fxrng_root);
+ FXRNG_BRNG_ASSERT(rng);
+
+ fxrng_brng_getbytes_internal(rng, buf, nbytes);
+ FXRNG_BRNG_ASSERT_NOT(rng);
+}
Added: head/sys/dev/random/fenestrasX/fx_brng.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/sys/dev/random/fenestrasX/fx_brng.h Sat Oct 10 21:45:59 2020 (r366620)
@@ -0,0 +1,66 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * Copyright (c) 2019 Conrad Meyer <cem at FreeBSD.org>
+ *
+ * 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 AUTHOR 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 AUTHOR 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.
+ *
+ * $FreeBSD$
+ */
+#pragma once
+
+#include <dev/random/fenestrasX/fx_rng.h>
+
+#define FXRNG_BUFRNG_SZ 128
+
+/*
+ * An object representing a buffered random number generator with forward
+ * secrecy (aka "fast-key-erasure").
+ *
+ * There is a single static root instance of this object associated with the
+ * entropy harvester, as well as additional instances per CPU, lazily allocated
+ * in NUMA-local memory, seeded from output of the root generator.
+ */
+struct fxrng_buffered_rng {
+ struct fxrng_basic_rng brng_rng;
+#define FXRNG_BRNG_LOCK(brng) mtx_lock(&(brng)->brng_rng.rng_lk)
+#define FXRNG_BRNG_UNLOCK(brng) mtx_unlock(&(brng)->brng_rng.rng_lk)
+#define FXRNG_BRNG_ASSERT(brng) mtx_assert(&(brng)->brng_rng.rng_lk, MA_OWNED)
+#define FXRNG_BRNG_ASSERT_NOT(brng) \
+ mtx_assert(&(brng)->brng_rng.rng_lk, MA_NOTOWNED)
+
+ /* Entropy reseed generation ("seed version"). */
+ uint64_t brng_generation;
+
+ /* Buffered output for quick access by small requests. */
+ uint8_t brng_buffer[FXRNG_BUFRNG_SZ];
+ uint8_t brng_avail_idx;
+};
+
+void fxrng_brng_init(struct fxrng_buffered_rng *);
+void fxrng_brng_produce_seed_data_internal(struct fxrng_buffered_rng *, void *,
+ size_t, uint64_t *seed_generation);
+void fxrng_brng_read(struct fxrng_buffered_rng *, void *, size_t);
+
+void fxrng_brng_reseed(const void *, size_t);
+struct harvest_event;
+void fxrng_brng_src_reseed(const struct harvest_event *);
Added: head/sys/dev/random/fenestrasX/fx_hash.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/sys/dev/random/fenestrasX/fx_hash.h Sat Oct 10 21:45:59 2020 (r366620)
@@ -0,0 +1,72 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * Copyright (c) 2019 Conrad Meyer <cem at FreeBSD.org>
+ *
+ * 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 AUTHOR 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 AUTHOR 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.
+ *
+ * $FreeBSD$
+ */
+#pragma once
+
+#include <dev/random/fenestrasX/fx_priv.h>
+#define blake2b_init blake2b_init_ref
+#define blake2b_update blake2b_update_ref
+#define blake2b_final blake2b_final_ref
+#include <contrib/libb2/blake2.h>
+
+#define FXRNG_HASH_SZ BLAKE2B_OUTBYTES /* 64 */
+
+/*
+ * Wrappers for hash function abstraction.
+ */
+struct fxrng_hash {
+ blake2b_state state;
+};
+
+static inline void
+fxrng_hash_init(struct fxrng_hash *h)
+{
+ int rc;
+
+ rc = blake2b_init(&h->state, FXRNG_HASH_SZ);
+ ASSERT(rc == 0, "blake2b_init");
+}
+
+static inline void
+fxrng_hash_update(struct fxrng_hash *h, const void *buf, size_t sz)
+{
+ int rc;
+
+ rc = blake2b_update(&h->state, buf, sz);
+ ASSERT(rc == 0, "blake2b_update");
+}
+
+static inline void
+fxrng_hash_finish(struct fxrng_hash *h, uint8_t buf[static FXRNG_HASH_SZ], size_t sz)
+{
+ int rc;
+
+ rc = blake2b_final(&h->state, buf, sz);
+ ASSERT(rc == 0, "blake2b_final(sz=%zu)", sz);
+ explicit_bzero(h, sizeof(*h));
+}
Added: head/sys/dev/random/fenestrasX/fx_main.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/sys/dev/random/fenestrasX/fx_main.c Sat Oct 10 21:45:59 2020 (r366620)
@@ -0,0 +1,274 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * Copyright (c) 2019 Conrad Meyer <cem at FreeBSD.org>
+ *
+ * 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 AUTHOR 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 AUTHOR 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.
+ */
+
+/*
+ * This random algorithm is derived in part from the "Windows 10 random number
+ * generation infrastructure" whitepaper published by Niels Ferguson and
+ * Microsoft: https://aka.ms/win10rng
+ *
+ * It is also inspired by DJB's writing on buffered key-erasure PRNGs:
+ * https://blog.cr.yp.to/20170723-random.html
+ *
+ * The Windows 10 RNG bears some similarity to Fortuna, which Ferguson was also
+ * involved with. Notable differences include:
+ * - Extended to multi-CPU design
+ * - Extended to pre-buffer some PRNG output
+ * - Pool-based reseeding is solely time-based (rather than on-access w/
+ * pacing)
+ * - Extended to specify efficient userspace design
+ * - Always-available design (requires the equivalent of loader(8) for all
+ * boots; probably relatively easy given the limited platforms Windows 10
+ * supports)
+ *
+ * Some aspects of the design document I found confusing and may have
+ * misinterpreted:
+ * - Relationship between root PRNG seed version and periodic reseed pool use.
+ * I interpreted these as separate sequences. The root PRNG seed version is
+ * bumped both by the periodic pool based reseed, and also special
+ * conditions such as the first time an entropy source provides entropy. I
+ * don't think first-time entropy sources should cause us to skip an entropy
+ * pool reseed.
+ * - Initial seeding. The paper is pretty terse on the subject. My
+ * interpretation of the document is that the Windows RNG infrastructure
+ * relies on the loader(8)-provided material for initial seeding and either
+ * ignores or doesn't start entropy sources until after that time. So when
+ * the paper says that first-time entropy source material "bypasses the
+ * pools," the root PRNG state already has been keyed for the first time and
+ * can generate 256 bits, mix it with the first-time entropy, and reseed
+ * immediately.
+ *
+ * Some notable design choices in this implementation divergent from that
+ * specified in the document above:
+ * - Blake2b instead of SHA-2 512 for entropy pooling
+ * - Chacha20 instead of AES-CTR DRBG for PRF
+ * - Initial seeding. We treat the 0->1 seed version (brng_generation) edge
+ * as the transition from blocked to unblocked. That edge is also the first
+ * time the key of the root BRNG's PRF is set. We perform initial seeding
+ * when the first request for entropy arrives.
+ * • As a result: Entropy callbacks prior to this edge do not have a keyed
+ * root PRNG, so bypassing the pools is kind of meaningless. Instead,
+ * they feed into pool0. (They also do not set the root PRNG key or bump
+ * the root PRNG seed version.)
+ * • Entropy callbacks after the edge behave like the specification.
+ * • All one-off sources are fed into pool0 and the result used to seed the
+ * root BRNG during the initial seed step.
+ * • All memory needed for initial seeding must be preallocated or static or
+ * fit on the stack; random reads can occur in nonsleepable contexts and
+ * we cannot allocate M_WAITOK. (We also cannot fail to incorporate any
+ * present one-off source, to the extent it is in the control of
+ * software.)
+ * - Timer interval reseeding. We also start the timer-based reseeding at
+ * initial seed, but unlike the design, our initial seed is some time after
+ * load (usually within the order of micro- or milliseconds due to
+ * stack_guard on x86, but conceivably later if nothing reads from random for
+ * a while).
+ *
+ * Not yet implemented, not in scope, or todo:
+ * - arc4random(9) injection/replacement
+ * - Userspace portions -- shared page, like timehands vdso?
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <sys/param.h>
+#include <sys/domainset.h>
+#include <sys/fail.h>
+#include <sys/limits.h>
+#include <sys/lock.h>
+#include <sys/kernel.h>
+#include <sys/malloc.h>
+#include <sys/mutex.h>
+#include <sys/random.h>
+#include <sys/sdt.h>
+#include <sys/smp.h>
+#include <sys/sysctl.h>
+#include <sys/systm.h>
+
+#include <machine/cpu.h>
+
+#include <vm/vm.h>
+#include <vm/vm_param.h>
+#include <vm/vm_page.h>
+#include <vm/vm_phys.h>
+#include <vm/vm_pagequeue.h>
+
+#include <dev/random/randomdev.h>
+#include <dev/random/random_harvestq.h>
+#include <dev/random/uint128.h>
+
+#include <dev/random/fenestrasX/fx_brng.h>
+#include <dev/random/fenestrasX/fx_hash.h>
+#include <dev/random/fenestrasX/fx_pool.h>
+#include <dev/random/fenestrasX/fx_priv.h>
+#include <dev/random/fenestrasX/fx_rng.h>
+
+struct fxrng_buffered_rng fxrng_root;
+uint64_t __read_mostly fxrng_root_generation;
+DPCPU_DEFINE_STATIC(struct fxrng_buffered_rng *, fxrng_brng);
+
+/*
+ * Top-level read API from randomdev. Responsible for NOWAIT-allocating
+ * per-cpu NUMA-local BRNGs, if needed and satisfiable; subroutines handle
+ * reseeding if the local BRNG is stale and rekeying when necessary. In
+ * low-memory conditions when a local BRNG cannot be allocated, the request is
+ * simply forwarded to the root BRNG.
+ *
+ * It is a precondition is that the root BRNG initial seeding has completed and
+ * the root generation number >0.
+ */
+static void
+fxrng_alg_read(uint8_t *output, size_t nbytes)
+{
+ struct fxrng_buffered_rng **pcpu_brng_p, *rng, *tmp;
+ struct pcpu *pcpu;
+
+ pcpu = get_pcpu();
+
+ /*
+ * The following statement directly accesses an implementation detail
+ * of DPCPU, but the macros cater only to pinned threads; we want to
+ * operate on our initial CPU, without pinning, *even if* we migrate.
+ */
+ pcpu_brng_p = _DPCPU_PTR(pcpu->pc_dynamic, fxrng_brng);
+
+ rng = (void *)atomic_load_acq_ptr((uintptr_t *)pcpu_brng_p);
+
+ /*
+ * Usually the pcpu BRNG has already been allocated, but we do it
+ * on-demand and need to check first. BRNGs are never deallocated and
+ * are valid as soon as the pointer is initialized.
+ */
+ if (__predict_false(rng == NULL)) {
+ uint8_t newkey[FX_CHACHA20_KEYSIZE];
+ struct domainset *ds;
+ int domain;
+
+ domain = pcpu->pc_domain;
+
+ /*
+ * Allocate pcpu BRNGs off-domain on weird NUMA machines like
+ * AMD Threadripper 2990WX, which has 2 NUMA nodes without
+ * local memory controllers. The PREF policy is automatically
+ * converted to something appropriate when domains are empty.
+ * (FIXED is not.)
+ *
+ * Otherwise, allocate strictly CPU-local memory. The
+ * rationale is this: if there is a memory shortage such that
+ * PREF policy would fallback to RR, we have no business
+ * wasting memory on a faster BRNG. So, use a FIXED domainset
+ * policy. If we cannot allocate, that's fine! We fall back
+ * to invoking the root BRNG.
+ */
+ if (VM_DOMAIN_EMPTY(domain))
+ ds = DOMAINSET_PREF(domain);
+ else
+ ds = DOMAINSET_FIXED(domain);
+
+ rng = malloc_domainset(sizeof(*rng), M_ENTROPY, ds,
+ M_NOWAIT | M_ZERO);
+ if (rng == NULL) {
+ /* Relatively easy case: fall back to root BRNG. */
+ rng = &fxrng_root;
+ goto have_valid_rng;
+ }
+
+ fxrng_brng_init(rng);
+
+ /*
+ * The root BRNG is always up and available. Requests are
+ * always satisfiable. This is a design invariant.
+ */
+ ASSERT_DEBUG(atomic_load_acq_64(&fxrng_root_generation) != 0,
+ "%s: attempting to seed child BRNG when root hasn't "
+ "been initialized yet.", __func__);
+
+ FXRNG_BRNG_LOCK(&fxrng_root);
+#ifdef WITNESS
+ /* Establish lock order root->pcpu for WITNESS. */
+ FXRNG_BRNG_LOCK(rng);
+ FXRNG_BRNG_UNLOCK(rng);
+#endif
+ fxrng_brng_produce_seed_data_internal(&fxrng_root, newkey,
+ sizeof(newkey), &rng->brng_generation);
+ FXRNG_BRNG_ASSERT_NOT(&fxrng_root);
+
+ fxrng_rng_setkey(&rng->brng_rng, newkey, sizeof(newkey));
+ explicit_bzero(newkey, sizeof(newkey));
+
+ /*
+ * We have a valid RNG. Try to install it, or grab the other
+ * one if we lost the race.
+ */
+ tmp = NULL;
+ while (tmp == NULL)
+ if (atomic_fcmpset_ptr((uintptr_t *)pcpu_brng_p,
+ (uintptr_t *)&tmp, (uintptr_t)rng))
+ goto have_valid_rng;
+
+ /*
+ * We lost the race. There's nothing sensitive about
+ * our BRNG's PRF state, because it will never be used
+ * for anything and the key doesn't expose any
+ * information about the parent (root) generator's
+ * state -- it has already rekeyed. The generation
+ * number is public, and a zero counter isn't sensitive.
+ */
+ free(rng, M_ENTROPY);
+ /*
+ * Use the winner's PCPU BRNG.
+ */
+ rng = tmp;
+ }
+
+have_valid_rng:
+ /* At this point we have a valid, initialized and seeded rng pointer. */
+ FXRNG_BRNG_LOCK(rng);
+ fxrng_brng_read(rng, output, nbytes);
+ FXRNG_BRNG_ASSERT_NOT(rng);
+}
+
+static void
+fxrng_init_alg(void *dummy __unused)
+{
+ DPCPU_ZERO(fxrng_brng);
+ fxrng_brng_init(&fxrng_root);
+ fxrng_pools_init();
+}
+SYSINIT(random_alg, SI_SUB_RANDOM, SI_ORDER_SECOND, fxrng_init_alg, NULL);
+
+/*
+ * Public visibility struct referenced directly by other parts of randomdev.
+ */
+const struct random_algorithm random_alg_context = {
+ .ra_ident = "fenestrasX",
+ .ra_pre_read = (void (*)(void))nullop,
+ .ra_read = fxrng_alg_read,
+ .ra_seeded = fxrng_alg_seeded,
+ .ra_event_processor = fxrng_event_processor,
+ .ra_poolcount = FXRNG_NPOOLS,
+};
Added: head/sys/dev/random/fenestrasX/fx_pool.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/sys/dev/random/fenestrasX/fx_pool.c Sat Oct 10 21:45:59 2020 (r366620)
@@ -0,0 +1,615 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * Copyright (c) 2019 Conrad Meyer <cem at FreeBSD.org>
+ *
+ * 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 AUTHOR 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 AUTHOR 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.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <sys/param.h>
+#include <sys/domainset.h>
+#include <sys/fail.h>
+#include <sys/limits.h>
+#include <sys/lock.h>
+#include <sys/kernel.h>
+#include <sys/malloc.h>
+#include <sys/mutex.h>
+#include <sys/queue.h>
+#include <sys/random.h>
+#include <sys/sdt.h>
+#include <sys/sysctl.h>
+#include <sys/systm.h>
+#include <sys/taskqueue.h>
+
+#include <machine/atomic.h>
+#include <machine/smp.h>
+
+#include <dev/random/randomdev.h>
+#include <dev/random/random_harvestq.h>
+
+#include <dev/random/fenestrasX/fx_brng.h>
+#include <dev/random/fenestrasX/fx_hash.h>
+#include <dev/random/fenestrasX/fx_pool.h>
+#include <dev/random/fenestrasX/fx_priv.h>
+
+/*
+ * Timer-based reseed interval growth factor and limit in seconds. (§ 3.2)
+ */
+#define FXENT_RESSED_INTVL_GFACT 3
+#define FXENT_RESEED_INTVL_MAX 3600
+
+/*
+ * Pool reseed schedule. Initially, only pool 0 is active. Until the timer
+ * interval reaches INTVL_MAX, only pool 0 is used.
+ *
+ * After reaching INTVL_MAX, pool k is either activated (if inactive) or used
+ * (if active) every 3^k timer reseeds. (§ 3.3)
+ *
+ * (Entropy harvesting only round robins across active pools.)
+ */
+#define FXENT_RESEED_BASE 3
+
+/*
+ * Number of bytes from high quality sources to allocate to pool 0 before
+ * normal round-robin allocation after each timer reseed. (§ 3.4)
+ */
+#define FXENT_HI_SRC_POOL0_BYTES 32
+
+/*
+ * § 3.1
+ *
+ * Low sources provide unconditioned entropy, such as mouse movements; high
+ * sources are assumed to provide high-quality random bytes. Pull sources are
+ * those which can be polled, i.e., anything randomdev calls a "random_source."
+ *
+ * In the whitepaper, low sources are pull. For us, at least in the existing
+ * design, low-quality sources push into some global ring buffer and then get
+ * forwarded into the RNG by a thread that continually polls. Presumably their
+ * design batches low entopy signals in some way (SHA512?) and only requests
+ * them dynamically on reseed. I'm not sure what the benefit is vs feeding
+ * into the pools directly.
+ */
+enum fxrng_ent_access_cls {
+ FXRNG_PUSH,
+ FXRNG_PULL,
+};
+enum fxrng_ent_source_cls {
+ FXRNG_HI,
+ FXRNG_LO,
+ FXRNG_GARBAGE,
+};
+struct fxrng_ent_cls {
+ enum fxrng_ent_access_cls entc_axx_cls;
+ enum fxrng_ent_source_cls entc_src_cls;
+};
+
+static const struct fxrng_ent_cls fxrng_hi_pull = {
+ .entc_axx_cls = FXRNG_PULL,
+ .entc_src_cls = FXRNG_HI,
+};
+static const struct fxrng_ent_cls fxrng_hi_push = {
+ .entc_axx_cls = FXRNG_PUSH,
+ .entc_src_cls = FXRNG_HI,
+};
+static const struct fxrng_ent_cls fxrng_lo_push = {
+ .entc_axx_cls = FXRNG_PUSH,
+ .entc_src_cls = FXRNG_LO,
+};
+static const struct fxrng_ent_cls fxrng_garbage = {
+ .entc_axx_cls = FXRNG_PUSH,
+ .entc_src_cls = FXRNG_GARBAGE,
+};
+
+/*
+ * This table is a mapping of randomdev's current source abstractions to the
+ * designations above; at some point, if the design seems reasonable, it would
+ * make more sense to pull this up into the abstraction layer instead.
+ */
+static const struct fxrng_ent_char {
+ const struct fxrng_ent_cls *entc_cls;
+} fxrng_ent_char[ENTROPYSOURCE] = {
+ [RANDOM_CACHED] = {
+ .entc_cls = &fxrng_hi_push,
+ },
+ [RANDOM_ATTACH] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_KEYBOARD] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_MOUSE] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_NET_TUN] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_NET_ETHER] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_NET_NG] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_INTERRUPT] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_SWI] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_FS_ATIME] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_UMA] = {
+ .entc_cls = &fxrng_lo_push,
+ },
+ [RANDOM_PURE_OCTEON] = {
+ .entc_cls = &fxrng_hi_push, /* Could be made pull. */
+ },
+ [RANDOM_PURE_SAFE] = {
+ .entc_cls = &fxrng_hi_push,
+ },
+ [RANDOM_PURE_GLXSB] = {
+ .entc_cls = &fxrng_hi_push,
+ },
+ [RANDOM_PURE_HIFN] = {
+ .entc_cls = &fxrng_hi_push,
+ },
+ [RANDOM_PURE_RDRAND] = {
+ .entc_cls = &fxrng_hi_pull,
+ },
+ [RANDOM_PURE_NEHEMIAH] = {
+ .entc_cls = &fxrng_hi_pull,
+ },
+ [RANDOM_PURE_RNDTEST] = {
+ .entc_cls = &fxrng_garbage,
+ },
+ [RANDOM_PURE_VIRTIO] = {
+ .entc_cls = &fxrng_hi_pull,
+ },
+ [RANDOM_PURE_BROADCOM] = {
+ .entc_cls = &fxrng_hi_push,
+ },
+ [RANDOM_PURE_CCP] = {
+ .entc_cls = &fxrng_hi_pull,
+ },
+ [RANDOM_PURE_DARN] = {
+ .entc_cls = &fxrng_hi_pull,
+ },
+ [RANDOM_PURE_TPM] = {
+ .entc_cls = &fxrng_hi_push,
+ },
+ [RANDOM_PURE_VMGENID] = {
+ .entc_cls = &fxrng_hi_push,
+ },
+};
+
+/* Useful for single-bit-per-source state. */
+BITSET_DEFINE(fxrng_bits, ENTROPYSOURCE);
+
+/* XXX Borrowed from not-yet-committed D22702. */
+#ifndef BIT_TEST_SET_ATOMIC_ACQ
+#define BIT_TEST_SET_ATOMIC_ACQ(_s, n, p) \
+ (atomic_testandset_acq_long( \
+ &(p)->__bits[__bitset_word((_s), (n))], (n)) != 0)
+#endif
+#define FXENT_TEST_SET_ATOMIC_ACQ(n, p) \
+ BIT_TEST_SET_ATOMIC_ACQ(ENTROPYSOURCE, n, p)
+
+/* For special behavior on first-time entropy sources. (§ 3.1) */
+static struct fxrng_bits __read_mostly fxrng_seen;
+
+/* For special behavior for high-entropy sources after a reseed. (§ 3.4) */
+_Static_assert(FXENT_HI_SRC_POOL0_BYTES <= UINT8_MAX, "");
+static uint8_t __read_mostly fxrng_reseed_seen[ENTROPYSOURCE];
+
+/* Entropy pools. Lock order is ENT -> RNG(root) -> RNG(leaf). */
+static struct mtx fxent_pool_lk;
+MTX_SYSINIT(fx_pool, &fxent_pool_lk, "fx entropy pool lock", MTX_DEF);
+#define FXENT_LOCK() mtx_lock(&fxent_pool_lk)
*** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
More information about the svn-src-head
mailing list