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 } 317