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
fxrng_brng_init(struct fxrng_buffered_rng * rng)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
fxrng_brng_src_reseed(const struct harvest_event * event)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
fxrng_brng_reseed(const void * entr,size_t sz)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
fxrng_vdso_sysinit(void * dummy __unused)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
fxrng_brng_getbytes_internal(struct fxrng_buffered_rng * rng,void * buf,size_t nbytes)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
fxrng_brng_produce_seed_data_internal(struct fxrng_buffered_rng * rng,void * buf,size_t keysz,uint64_t * seed_generation)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
fxrng_brng_read(struct fxrng_buffered_rng * rng,void * buf,size_t nbytes)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