sys/dev/random/fenestrasX/fx_brng.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2019 Conrad Meyer <cem@FreeBSD.org>
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  */
  27
  28 #include <sys/cdefs.h>
  29 __FBSDID("$FreeBSD$");
  30
  31 #include <sys/param.h>
  32 #include <sys/fail.h>
  33 #include <sys/limits.h>
  34 #include <sys/lock.h>
  35 #include <sys/kernel.h>
  36 #include <sys/malloc.h>
  37 #include <sys/mutex.h>
  38 #include <sys/random.h>
  39 #include <sys/sdt.h>
  40 #include <sys/sysctl.h>
  41 #include <sys/systm.h>
  42 #include <sys/vdso.h>
  43
  44 #include <machine/cpu.h>
  45
  46 #include <dev/random/randomdev.h>
  47 #include <dev/random/random_harvestq.h>
  48 #include <dev/random/uint128.h>
  49
  50 #include <dev/random/fenestrasX/fx_brng.h>
  51 #include <dev/random/fenestrasX/fx_priv.h>
  52 #include <dev/random/fenestrasX/fx_pub.h>
  53 #include <dev/random/fenestrasX/fx_rng.h>
  54
  55 /*
  56  * Implementation of a buffered RNG, described in § 1.2-1.4 of the whitepaper.
  57  */
  58
  59 /*
  60  * Initialize a buffered rng instance (either the static root instance, or a
  61  * per-cpu instance on the heap.  Both should be zero initialized before this
  62  * routine.
  63  */
  64 void
  65 fxrng_brng_init(struct fxrng_buffered_rng *rng)
  66 {
  67         fxrng_rng_init(&rng->brng_rng, rng == &fxrng_root);
  68
  69         /* I.e., the buffer is empty. */
  70         rng->brng_avail_idx = sizeof(rng->brng_buffer);
  71
  72         /*
  73          * It is fine and correct for brng_generation and brng_buffer to be
  74          * zero values.
  75          *
  76          * brng_prf and brng_generation must be initialized later.
  77          * Initialization is special for the root BRNG.  PCPU child instances
  78          * use fxrng_brng_produce_seed_data_internal() below.
  79          */
  80 }
  81
  82 /*
  83  * Directly reseed the root BRNG from a first-time entropy source,
  84  * incorporating the existing BRNG state.  The main motivation for doing so "is
  85  * to ensure that as soon as an entropy source produces data, PRNG output
  86  * depends on the data from that source." (§ 3.1)
  87  *
  88  * The root BRNG is locked on entry and initial keying (brng_generation > 0)
  89  * has already been performed.  The root BRNG is unlocked on return.
  90  */
  91 void
  92 fxrng_brng_src_reseed(const struct harvest_event *event)
  93 {
  94         struct fxrng_buffered_rng *rng;
  95
  96         rng = &fxrng_root;
  97         FXRNG_BRNG_ASSERT(rng);
  98         ASSERT_DEBUG(rng->brng_generation > 0, "root RNG not seeded");
  99
 100         fxrng_rng_src_reseed(&rng->brng_rng, event);
 101         FXRNG_BRNG_ASSERT(rng);
 102
 103         /*
 104          * Bump root generation (which is costly) to force downstream BRNGs to
 105          * reseed and quickly incorporate the new entropy.  The intuition is
 106          * that this tradeoff is worth it because new sources show up extremely
 107          * rarely (limiting cost) and if they can contribute any entropy to a
 108          * weak state, we want to propagate it to all generators ASAP.
 109          */
 110         rng->brng_generation++;
 111         atomic_store_rel_64(&fxrng_root_generation, rng->brng_generation);
 112         /* Update VDSO version. */
 113         fxrng_push_seed_generation(rng->brng_generation);
 114         FXRNG_BRNG_UNLOCK(rng);
 115 }
 116
 117 /*
 118  * Reseed a brng from some amount of pooled entropy (determined in fx_pool.c by
 119  * fxent_timer_reseed_npools).  For initial seeding, we pool entropy in a
 120  * single pool and use this API as well (fxrng_alg_seeded).
 121  */
 122 void
 123 fxrng_brng_reseed(const void *entr, size_t sz)
 124 {
 125         struct fxrng_buffered_rng *rng;
 126
 127         rng = &fxrng_root;
 128         FXRNG_BRNG_LOCK(rng);
 129
 130         fxrng_rng_reseed(&rng->brng_rng, (rng->brng_generation > 0), entr, sz);
 131         FXRNG_BRNG_ASSERT(rng);
 132
 133         rng->brng_generation++;
 134         atomic_store_rel_64(&fxrng_root_generation, rng->brng_generation);
 135         /* Update VDSO version. */
 136         fxrng_push_seed_generation(rng->brng_generation);
 137         FXRNG_BRNG_UNLOCK(rng);
 138 }
 139
 140 /*
 141  * Sysentvec and VDSO are initialized much later than SI_SUB_RANDOM.  When
 142  * they're online, go ahead and push an initial root seed version.
 143  * INIT_SYSENTVEC runs at SI_SUB_EXEC:SI_ORDER_ANY, and SI_ORDER_ANY is the
 144  * maximum value, so we must run at SI_SUB_EXEC+1.
 145  */
 146 static void
 147 fxrng_vdso_sysinit(void *dummy __unused)
 148 {
 149         FXRNG_BRNG_LOCK(&fxrng_root);
 150         fxrng_push_seed_generation(fxrng_root.brng_generation);
 151         FXRNG_BRNG_UNLOCK(&fxrng_root);
 152 }
 153 SYSINIT(fxrng_vdso, SI_SUB_EXEC + 1, SI_ORDER_ANY, fxrng_vdso_sysinit, NULL);
 154
 155 /*
 156  * Grab some bytes off an initialized, current generation RNG.
 157  *
 158  * (Does not handle reseeding if our generation is stale.)
 159  *
 160  * Locking protocol is a bit odd.  The RNG is locked on entrance, but the lock
 161  * is dropped on exit.  This avoids holding a lock during expensive and slow
 162  * RNG generation.
 163  */
 164 static void
 165 fxrng_brng_getbytes_internal(struct fxrng_buffered_rng *rng, void *buf,
 166     size_t nbytes)
 167 {
 168
 169         FXRNG_BRNG_ASSERT(rng);
 170
 171         /* Make the zero request impossible for the rest of the logic. */
 172         if (__predict_false(nbytes == 0)) {
 173                 FXRNG_BRNG_UNLOCK(rng);
 174                 goto out;
 175         }
 176
 177         /* Fast/easy case: Use some bytes from the buffer. */
 178         if (rng->brng_avail_idx + nbytes <= sizeof(rng->brng_buffer)) {
 179                 memcpy(buf, &rng->brng_buffer[rng->brng_avail_idx], nbytes);
 180                 explicit_bzero(&rng->brng_buffer[rng->brng_avail_idx], nbytes);
 181                 rng->brng_avail_idx += nbytes;
 182                 FXRNG_BRNG_UNLOCK(rng);
 183                 goto out;
 184         }
 185
 186         /* Buffer case: */
 187         if (nbytes < sizeof(rng->brng_buffer)) {
 188                 size_t rem;
 189
 190                 /* Drain anything left in the buffer first. */
 191                 if (rng->brng_avail_idx < sizeof(rng->brng_buffer)) {
 192                         rem = sizeof(rng->brng_buffer) - rng->brng_avail_idx;
 193                         ASSERT_DEBUG(nbytes > rem, "invariant");
 194
 195                         memcpy(buf, &rng->brng_buffer[rng->brng_avail_idx], rem);
 196
 197                         buf = (uint8_t*)buf + rem;
 198                         nbytes -= rem;
 199                         ASSERT_DEBUG(nbytes != 0, "invariant");
 200                 }
 201
 202                 /*
 203                  * Partial fill from first buffer, have to rekey and generate a
 204                  * new buffer to do the rest.
 205                  */
 206                 fxrng_rng_genrandom_internal(&rng->brng_rng, rng->brng_buffer,
 207                     sizeof(rng->brng_buffer), false);
 208                 FXRNG_BRNG_ASSERT(rng);
 209                 rng->brng_avail_idx = 0;
 210
 211                 memcpy(buf, &rng->brng_buffer[rng->brng_avail_idx], nbytes);
 212                 explicit_bzero(&rng->brng_buffer[rng->brng_avail_idx], nbytes);
 213                 rng->brng_avail_idx += nbytes;
 214                 FXRNG_BRNG_UNLOCK(rng);
 215                 goto out;
 216         }
 217
 218         /* Large request; skip the buffer. */
 219         fxrng_rng_genrandom_internal(&rng->brng_rng, buf, nbytes, true);
 220
 221 out:
 222         FXRNG_BRNG_ASSERT_NOT(rng);
 223         return;
 224 }
 225
 226 /*
 227  * API to get a new key for a downstream RNG.  Returns the new key in 'buf', as
 228  * well as the generator's reseed_generation.
 229  *
 230  * 'rng' is locked on entry and unlocked on return.
 231  *
 232  * Only valid after confirming the caller's seed version or reseed_generation
 233  * matches roots (or we are root).  (For now, this is only used to reseed the
 234  * per-CPU generators from root.)
 235  */
 236 void
 237 fxrng_brng_produce_seed_data_internal(struct fxrng_buffered_rng *rng,
 238     void *buf, size_t keysz, uint64_t *seed_generation)
 239 {
 240         FXRNG_BRNG_ASSERT(rng);
 241         ASSERT_DEBUG(keysz == FX_CHACHA20_KEYSIZE, "keysz: %zu", keysz);
 242
 243         *seed_generation = rng->brng_generation;
 244         fxrng_brng_getbytes_internal(rng, buf, keysz);
 245         FXRNG_BRNG_ASSERT_NOT(rng);
 246 }
 247
 248 /*
 249  * Read from an allocated and initialized buffered BRNG.  This a high-level
 250  * API, but doesn't handle PCPU BRNG allocation.
 251  *
 252  * BRNG is locked on entry.  It is unlocked on return.
 253  */
 254 void
 255 fxrng_brng_read(struct fxrng_buffered_rng *rng, void *buf, size_t nbytes)
 256 {
 257         uint8_t newkey[FX_CHACHA20_KEYSIZE];
 258
 259         FXRNG_BRNG_ASSERT(rng);
 260
 261         /* Fast path: there hasn't been a global reseed since last read. */
 262         if (rng->brng_generation == atomic_load_acq_64(&fxrng_root_generation))
 263                 goto done_reseeding;
 264
 265         ASSERT(rng != &fxrng_root, "root rng inconsistent seed version");
 266
 267         /*
 268          * Slow path: We need to rekey from the parent BRNG to incorporate new
 269          * entropy material.
 270          *
 271          * Lock order is always root -> percpu.
 272          */
 273         FXRNG_BRNG_UNLOCK(rng);
 274         FXRNG_BRNG_LOCK(&fxrng_root);
 275         FXRNG_BRNG_LOCK(rng);
 276
 277         /*
 278          * If we lost the reseeding race when the lock was dropped, don't
 279          * duplicate work.
 280          */
 281         if (__predict_false(rng->brng_generation ==
 282             atomic_load_acq_64(&fxrng_root_generation))) {
 283                 FXRNG_BRNG_UNLOCK(&fxrng_root);
 284                 goto done_reseeding;
 285         }
 286
 287         fxrng_brng_produce_seed_data_internal(&fxrng_root, newkey,
 288             sizeof(newkey), &rng->brng_generation);
 289
 290         FXRNG_BRNG_ASSERT_NOT(&fxrng_root);
 291         FXRNG_BRNG_ASSERT(rng);
 292
 293         fxrng_rng_setkey(&rng->brng_rng, newkey, sizeof(newkey));
 294         explicit_bzero(newkey, sizeof(newkey));
 295
 296         /*
 297          * A reseed invalidates any previous buffered contents.  Here, we
 298          * forward the available index to the end of the buffer, i.e., empty.
 299          * Requests that would use the buffer (< 128 bytes) will refill its
 300          * contents on demand.
 301          *
 302          * It is explicitly ok that we do not zero out any remaining buffer
 303          * bytes; they will never be handed out to callers, and they reveal
 304          * nothing about the reseeded key (which came from the root BRNG).
 305          * (§ 1.3)
 306          */
 307         rng->brng_avail_idx = sizeof(rng->brng_buffer);
 308
 309 done_reseeding:
 310         if (rng != &fxrng_root)
 311                 FXRNG_BRNG_ASSERT_NOT(&fxrng_root);
 312         FXRNG_BRNG_ASSERT(rng);
 313
 314         fxrng_brng_getbytes_internal(rng, buf, nbytes);
 315         FXRNG_BRNG_ASSERT_NOT(rng);
 316 }