xref: /freebsd/sys/dev/random/fenestrasX/fx_pool.c (revision 93b02f69a6f6ffb833227c2fd56d48daac128156)

/*-
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Copyright (c) 2019 Conrad Meyer <cem@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/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>
#include <dev/random/fenestrasX/fx_pub.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_CALLOUT] = {
		.entc_cls = &fxrng_lo_push,
	},
	[RANDOM_RANDOMDEV] = {
		.entc_cls = &fxrng_lo_push,
	},
	[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_RDSEED] = {
		.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,
	},
	[RANDOM_PURE_QUALCOMM] = {
		.entc_cls = &fxrng_hi_pull,
	},
	[RANDOM_PURE_ARMV8] = {
		.entc_cls = &fxrng_hi_pull,
	},
	[RANDOM_PURE_ARM_TRNG] = {
		.entc_cls = &fxrng_hi_pull,
	},
};

/* 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)
#define	FXENT_UNLOCK()		mtx_unlock(&fxent_pool_lk)
#define	FXENT_ASSERT(rng)	mtx_assert(&fxent_pool_lk, MA_OWNED)
#define	FXENT_ASSERT_NOT(rng)	mtx_assert(&fxent_pool_lk, MA_NOTOWNED)
static struct fxrng_hash fxent_pool[FXRNG_NPOOLS];
static unsigned __read_mostly fxent_nactpools = 1;
static struct timeout_task fxent_reseed_timer;
static int __read_mostly fxent_timer_ready;

/*
 * Track number of bytes of entropy harvested from high-quality sources prior
 * to initial keying.  The idea is to collect more jitter entropy when fewer
 * high-quality bytes were available and less if we had other good sources.  We
 * want to provide always-on availability but don't necessarily have *any*
 * great sources on some platforms.
 *
 * Like fxrng_ent_char: at some point, if the design seems reasonable, it would
 * make more sense to pull this up into the abstraction layer instead.
 *
 * Jitter entropy is unimplemented for now.
 */
static unsigned long fxrng_preseed_ent;

void
fxrng_pools_init(void)
{
	size_t i;

	for (i = 0; i < nitems(fxent_pool); i++)
		fxrng_hash_init(&fxent_pool[i]);
}

static inline bool
fxrng_hi_source(enum random_entropy_source src)
{
	return (fxrng_ent_char[src].entc_cls->entc_src_cls == FXRNG_HI);
}

/*
 * A racy check that this high-entropy source's event should contribute to
 * pool0 on the basis of per-source byte count.  The check is racy for two
 * reasons:
 *   - Performance: The vast majority of the time, we've already taken 32 bytes
 *     from any present high quality source and the racy check lets us avoid
 *     dirtying the cache for the global array.
 *   - Correctness: It's fine that the check is racy.  The failure modes are:
 *     • False positive: We will detect when we take the lock.
 *     • False negative: We still collect the entropy; it just won't be
 *       preferentially placed in pool0 in this case.
 */
static inline bool
fxrng_hi_pool0_eligible_racy(enum random_entropy_source src)
{
	return (atomic_load_acq_8(&fxrng_reseed_seen[src]) <
	    FXENT_HI_SRC_POOL0_BYTES);
}

/*
 * Top level entropy processing API from randomdev.
 *
 * Invoked by the core randomdev subsystem both for preload entropy, "push"
 * sources (like interrupts, keyboard, etc) and pull sources (RDRAND, etc).
 */
void
fxrng_event_processor(struct harvest_event *event)
{
	enum random_entropy_source src;
	unsigned pool;
	bool first_time, first_32;

	src = event->he_source;

	ASSERT_DEBUG(event->he_size <= sizeof(event->he_entropy),
	    "%s: he_size: %u > sizeof(he_entropy): %zu", __func__,
	    (unsigned)event->he_size, sizeof(event->he_entropy));

	/*
	 * Zero bytes of source entropy doesn't count as observing this source
	 * for the first time.  We still harvest the counter entropy.
	 */
	first_time = event->he_size > 0 &&
	    !FXENT_TEST_SET_ATOMIC_ACQ(src, &fxrng_seen);
	if (__predict_false(first_time)) {
		/*
		 * "The first time [any source] provides entropy, it is used to
		 * directly reseed the root PRNG.  The entropy pools are
		 * bypassed." (§ 3.1)
		 *
		 * Unlike Windows, we cannot rely on loader(8) seed material
		 * being present, so we perform initial keying in the kernel.
		 * We use brng_generation 0 to represent an unkeyed state.
		 *
		 * Prior to initial keying, it doesn't make sense to try to mix
		 * the entropy directly with the root PRNG state, as the root
		 * PRNG is unkeyed.  Instead, we collect pre-keying dynamic
		 * entropy in pool0 and do not bump the root PRNG seed version
		 * or set its key.  Initial keying will incorporate pool0 and
		 * bump the brng_generation (seed version).
		 *
		 * After initial keying, we do directly mix in first-time
		 * entropy sources.  We use the root BRNG to generate 32 bytes
		 * and use fxrng_hash to mix it with the new entropy source and
		 * re-key with the first 256 bits of hash output.
		 */
		FXENT_LOCK();
		FXRNG_BRNG_LOCK(&fxrng_root);
		if (__predict_true(fxrng_root.brng_generation > 0)) {
			/* Bypass the pools: */
			FXENT_UNLOCK();
			fxrng_brng_src_reseed(event);
			FXRNG_BRNG_ASSERT_NOT(&fxrng_root);
			return;
		}

		/*
		 * Keying the root PRNG requires both FXENT_LOCK and the PRNG's
		 * lock, so we only need to hold on to the pool lock to prevent
		 * initial keying without this entropy.
		 */
		FXRNG_BRNG_UNLOCK(&fxrng_root);

		/* Root PRNG hasn't been keyed yet, just accumulate event. */
		fxrng_hash_update(&fxent_pool[0], &event->he_somecounter,
		    sizeof(event->he_somecounter));
		fxrng_hash_update(&fxent_pool[0], event->he_entropy,
		    event->he_size);

		if (fxrng_hi_source(src)) {
			/* Prevent overflow. */
			if (fxrng_preseed_ent <= ULONG_MAX - event->he_size)
				fxrng_preseed_ent += event->he_size;
		}
		FXENT_UNLOCK();
		return;
	}
	/* !first_time */

	/*
	 * "The first 32 bytes produced by a high entropy source after a reseed
	 * from the pools is always put in pool 0." (§ 3.4)
	 *
	 * The first-32-byte tracking data in fxrng_reseed_seen is reset in
	 * fxent_timer_reseed_npools() below.
	 */
	first_32 = event->he_size > 0 &&
	    fxrng_hi_source(src) &&
	    atomic_load_acq_int(&fxent_nactpools) > 1 &&
	    fxrng_hi_pool0_eligible_racy(src);
	if (__predict_false(first_32)) {
		unsigned rem, seen;

		FXENT_LOCK();
		seen = fxrng_reseed_seen[src];
		if (seen == FXENT_HI_SRC_POOL0_BYTES)
			goto round_robin;

		rem = FXENT_HI_SRC_POOL0_BYTES - seen;
		rem = MIN(rem, event->he_size);

		fxrng_reseed_seen[src] = seen + rem;

		/*
		 * We put 'rem' bytes in pool0, and any remaining bytes are
		 * round-robin'd across other pools.
		 */
		fxrng_hash_update(&fxent_pool[0],
		    ((uint8_t *)event->he_entropy) + event->he_size - rem,
		    rem);
		if (rem == event->he_size) {
			fxrng_hash_update(&fxent_pool[0], &event->he_somecounter,
			    sizeof(event->he_somecounter));
			FXENT_UNLOCK();
			return;
		}

		/*
		 * If fewer bytes were needed than this even provied, We only
		 * take the last rem bytes of the entropy buffer and leave the
		 * timecounter to be round-robin'd with the remaining entropy.
		 */
		event->he_size -= rem;
		goto round_robin;
	}
	/* !first_32 */

	FXENT_LOCK();

round_robin:
	FXENT_ASSERT();
	pool = event->he_destination % fxent_nactpools;
	fxrng_hash_update(&fxent_pool[pool], event->he_entropy,
	    event->he_size);
	fxrng_hash_update(&fxent_pool[pool], &event->he_somecounter,
	    sizeof(event->he_somecounter));

	if (__predict_false(fxrng_hi_source(src) &&
	    atomic_load_acq_64(&fxrng_root_generation) == 0)) {
		/* Prevent overflow. */
		if (fxrng_preseed_ent <= ULONG_MAX - event->he_size)
			fxrng_preseed_ent += event->he_size;
	}
	FXENT_UNLOCK();
}

/*
 * Top level "seeded" API/signal from randomdev.
 *
 * This is our warning that a request is coming: we need to be seeded.  In
 * fenestrasX, a request for random bytes _never_ fails.  "We (ed: ditto) have
 * observed that there are many callers that never check for the error code,
 * even if they are generating cryptographic key material." (§ 1.6)
 *
 * If we returned 'false', both read_random(9) and chacha20_randomstir()
 * (arc4random(9)) will blindly charge on with something almost certainly worse
 * than what we've got, or are able to get quickly enough.
 */
bool
fxrng_alg_seeded(void)
{
	uint8_t hash[FXRNG_HASH_SZ];
	sbintime_t sbt;

	/* The vast majority of the time, we expect to already be seeded. */
	if (__predict_true(atomic_load_acq_64(&fxrng_root_generation) != 0))
		return (true);

	/*
	 * Take the lock and recheck; only one thread needs to do the initial
	 * seeding work.
	 */
	FXENT_LOCK();
	if (atomic_load_acq_64(&fxrng_root_generation) != 0) {
		FXENT_UNLOCK();
		return (true);
	}
	/* XXX Any one-off initial seeding goes here. */

	fxrng_hash_finish(&fxent_pool[0], hash, sizeof(hash));
	fxrng_hash_init(&fxent_pool[0]);

	fxrng_brng_reseed(hash, sizeof(hash));
	FXENT_UNLOCK();

	randomdev_unblock();
	explicit_bzero(hash, sizeof(hash));

	/*
	 * This may be called too early for taskqueue_thread to be initialized.
	 * fxent_pool_timer_init will detect if we've already unblocked and
	 * queue the first timer reseed at that point.
	 */
	if (atomic_load_acq_int(&fxent_timer_ready) != 0) {
		sbt = SBT_1S;
		taskqueue_enqueue_timeout_sbt(taskqueue_thread,
		    &fxent_reseed_timer, -sbt, (sbt / 3), C_PREL(2));
	}
	return (true);
}

/*
 * Timer-based reseeds and pool expansion.
 */
static void
fxent_timer_reseed_npools(unsigned n)
{
	/*
	 * 64 * 8 => moderately large 512 bytes.  Could be static, as we are
	 * only used in a static context.  On the other hand, this is in
	 * threadqueue TASK context and we're likely nearly at top of stack
	 * already.
	 */
	uint8_t hash[FXRNG_HASH_SZ * FXRNG_NPOOLS];
	unsigned i;

	ASSERT_DEBUG(n > 0 && n <= FXRNG_NPOOLS, "n:%u", n);

	FXENT_ASSERT();
	/*
	 * Collect entropy from pools 0..n-1 by concatenating the output hashes
	 * and then feeding them into fxrng_brng_reseed, which will hash the
	 * aggregate together with the current root PRNG keystate to produce a
	 * new key.  It will also bump the global generation counter
	 * appropriately.
	 */
	for (i = 0; i < n; i++) {
		fxrng_hash_finish(&fxent_pool[i], hash + i * FXRNG_HASH_SZ,
		    FXRNG_HASH_SZ);
		fxrng_hash_init(&fxent_pool[i]);
	}

	fxrng_brng_reseed(hash, n * FXRNG_HASH_SZ);
	explicit_bzero(hash, n * FXRNG_HASH_SZ);

	/*
	 * "The first 32 bytes produced by a high entropy source after a reseed
	 * from the pools is always put in pool 0." (§ 3.4)
	 *
	 * So here we reset the tracking (somewhat naively given the majority
	 * of sources on most machines are not what we consider "high", but at
	 * 32 bytes it's smaller than a cache line), so the next 32 bytes are
	 * prioritized into pool0.
	 *
	 * See corresponding use of fxrng_reseed_seen in fxrng_event_processor.
	 */
	memset(fxrng_reseed_seen, 0, sizeof(fxrng_reseed_seen));
	FXENT_ASSERT();
}

static void
fxent_timer_reseed(void *ctx __unused, int pending __unused)
{
	static unsigned reseed_intvl_sec = 1;
	/* Only reseeds after FXENT_RESEED_INTVL_MAX is achieved. */
	static uint64_t reseed_number = 1;

	unsigned next_ival, i, k;
	sbintime_t sbt;

	if (reseed_intvl_sec < FXENT_RESEED_INTVL_MAX) {
		next_ival = FXENT_RESSED_INTVL_GFACT * reseed_intvl_sec;
		if (next_ival > FXENT_RESEED_INTVL_MAX)
			next_ival = FXENT_RESEED_INTVL_MAX;
		FXENT_LOCK();
		fxent_timer_reseed_npools(1);
		FXENT_UNLOCK();
	} else {
		/*
		 * The creation of entropy pools beyond 0 is enabled when the
		 * reseed interval hits the maximum. (§ 3.3)
		 */
		next_ival = reseed_intvl_sec;

		/*
		 * Pool 0 is used every reseed; pool 1..0 every 3rd reseed; and in
		 * general, pool n..0 every 3^n reseeds.
		 */
		k = reseed_number;
		reseed_number++;

		/* Count how many pools, from [0, i), to use for reseed. */
		for (i = 1; i < MIN(fxent_nactpools + 1, FXRNG_NPOOLS); i++) {
			if ((k % FXENT_RESEED_BASE) != 0)
				break;
			k /= FXENT_RESEED_BASE;
		}

		/*
		 * If we haven't activated pool i yet, activate it and only
		 * reseed from [0, i-1).  (§ 3.3)
		 */
		FXENT_LOCK();
		if (i == fxent_nactpools + 1) {
			fxent_timer_reseed_npools(fxent_nactpools);
			fxent_nactpools++;
		} else {
			/* Just reseed from [0, i). */
			fxent_timer_reseed_npools(i);
		}
		FXENT_UNLOCK();
	}

	/* Schedule the next reseed. */
	sbt = next_ival * SBT_1S;
	taskqueue_enqueue_timeout_sbt(taskqueue_thread, &fxent_reseed_timer,
	    -sbt, (sbt / 3), C_PREL(2));

	reseed_intvl_sec = next_ival;
}

static void
fxent_pool_timer_init(void *dummy __unused)
{
	sbintime_t sbt;

	TIMEOUT_TASK_INIT(taskqueue_thread, &fxent_reseed_timer, 0,
	    fxent_timer_reseed, NULL);

	if (atomic_load_acq_64(&fxrng_root_generation) != 0) {
		sbt = SBT_1S;
		taskqueue_enqueue_timeout_sbt(taskqueue_thread,
		    &fxent_reseed_timer, -sbt, (sbt / 3), C_PREL(2));
	}
	atomic_store_rel_int(&fxent_timer_ready, 1);
}
/* After taskqueue_thread is initialized in SI_SUB_TASKQ:SI_ORDER_SECOND. */
SYSINIT(fxent_pool_timer_init, SI_SUB_TASKQ, SI_ORDER_ANY,
    fxent_pool_timer_init, NULL);