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