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 */
64void
65fxrng_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 */
91void
92fxrng_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 */
122void
123fxrng_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 */
146static void
147fxrng_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}
153SYSINIT(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 */
164static void
165fxrng_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
221out:
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 */
236void
237fxrng_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 */
254void
255fxrng_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
309done_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