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