/*-
* SPDX-License-Identifier: BSD-2-Clause-FreeBSD
*
* 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.
*/
/*
* 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:
* - Various initial seeding sources we don't have yet
* - In particular, VM migration/copy detection
*/
#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_pub.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, uint64_t *seed_version_out)
{
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);
if (seed_version_out != NULL)
*seed_version_out = rng->brng_generation;
fxrng_brng_read(rng, output, nbytes);
FXRNG_BRNG_ASSERT_NOT(rng);
}
static void
fxrng_alg_read(uint8_t *output, size_t nbytes)
{
_fxrng_alg_read(output, nbytes, NULL);
}
/*
* External API for arc4random(9) to fetch new key material and associated seed
* version in chacha20_randomstir().
*/
void
read_random_key(void *output, size_t nbytes, uint64_t *seed_version_out)
{
/* Ensure _fxrng_alg_read invariant. */
if (__predict_false(atomic_load_acq_64(&fxrng_root_generation) == 0))
(void)fxrng_alg_seeded();
_fxrng_alg_read(output, nbytes, seed_version_out);
}
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,
};