2 * Copyright (c) 2000-2013 Mark R V Murray
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer
10 * in this position and unchanged.
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.
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD$");
32 #include "opt_random.h"
34 #include <sys/param.h>
35 #include <sys/kernel.h>
37 #include <sys/malloc.h>
38 #include <sys/mutex.h>
39 #include <sys/random.h>
40 #include <sys/sysctl.h>
41 #include <sys/systm.h>
43 #include <machine/cpu.h>
45 #include <crypto/rijndael/rijndael-api-fst.h>
46 #include <crypto/sha2/sha2.h>
48 #include <dev/random/hash.h>
49 #include <dev/random/randomdev.h>
50 #include <dev/random/random_adaptors.h>
51 #include <dev/random/random_harvestq.h>
52 #include <dev/random/uint128.h>
53 #include <dev/random/yarrow.h>
55 #include <sys/param.h>
56 #include <sys/types.h>
63 #include "unit_test.h"
65 #include <crypto/rijndael/rijndael-api-fst.h>
66 #include <crypto/sha2/sha2.h>
68 #include <dev/random/hash.h>
69 #include <dev/random/randomdev.h>
70 #include <dev/random/uint128.h>
71 #include <dev/random/yarrow.h>
74 #if !defined(RANDOM_YARROW) && !defined(RANDOM_FORTUNA)
76 #elif defined(RANDOM_YARROW) && defined(RANDOM_FORTUNA)
77 #error "Must define either RANDOM_YARROW or RANDOM_FORTUNA"
80 #if defined(RANDOM_YARROW)
82 #define TIMEBIN 16 /* max value for Pt/t */
87 /* This algorithm (and code) presumes that KEYSIZE is twice as large as BLOCKSIZE */
88 CTASSERT(BLOCKSIZE == sizeof(uint128_t));
89 CTASSERT(KEYSIZE == 2*BLOCKSIZE);
91 /* This is the beastie that needs protecting. It contains all of the
92 * state that we are excited about.
93 * Exactly one is instantiated.
95 static struct yarrow_state {
97 uint8_t byte[BLOCKSIZE];
100 struct randomdev_key key; /* K */
101 u_int gengateinterval; /* Pg */
102 u_int bins; /* Pt/t */
103 u_int outputblocks; /* count output blocks for gates */
104 u_int slowoverthresh; /* slow pool overthreshhold reseed count */
107 u_int bits; /* estimated bits of entropy */
108 } source[ENTROPYSOURCE];/* ... per source */
109 u_int thresh; /* pool reseed threshhold */
110 struct randomdev_hash hash; /* accumulated entropy */
111 } pool[2]; /* pool[0] is fast, pool[1] is slow */
115 uint8_t junk[KEYSIZE];
116 struct randomdev_hash hash;
120 /* The random_reseed_mtx mutex protects seeding and polling/blocking. */
121 static mtx_t random_reseed_mtx;
124 static struct sysctl_ctx_list random_clist;
125 RANDOM_CHECK_UINT(gengateinterval, 4, 64);
126 RANDOM_CHECK_UINT(bins, 2, 16);
127 RANDOM_CHECK_UINT(fastthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */
128 RANDOM_CHECK_UINT(slowthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */
129 RANDOM_CHECK_UINT(slowoverthresh, 1, 5);
131 static u_int harvest_destination[ENTROPYSOURCE];
134 static void generator_gate(void);
135 static void reseed(u_int);
138 random_yarrow_init_alg(void)
142 struct sysctl_oid *random_yarrow_o;
145 memset(yarrow_state.start_cache.junk, 0, KEYSIZE);
146 randomdev_hash_init(&yarrow_state.start_cache.hash);
148 /* Set up the lock for the reseed/gate state */
150 mtx_init(&random_reseed_mtx, "reseed mutex", NULL, MTX_DEF);
152 mtx_init(&random_reseed_mtx, mtx_plain);
155 /* Start unseeded, therefore blocked. */
156 yarrow_state.seeded = 0;
159 /* Yarrow parameters. Do not adjust these unless you have
160 * have a very good clue about what they do!
162 random_yarrow_o = SYSCTL_ADD_NODE(&random_clist,
163 SYSCTL_STATIC_CHILDREN(_kern_random),
164 OID_AUTO, "yarrow", CTLFLAG_RW, 0,
165 "Yarrow Parameters");
167 SYSCTL_ADD_PROC(&random_clist,
168 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
169 "gengateinterval", CTLTYPE_INT|CTLFLAG_RW,
170 &yarrow_state.gengateinterval, 10,
171 random_check_uint_gengateinterval, "I",
172 "Generation gate interval");
174 SYSCTL_ADD_PROC(&random_clist,
175 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
176 "bins", CTLTYPE_INT|CTLFLAG_RW,
177 &yarrow_state.bins, 10,
178 random_check_uint_bins, "I",
179 "Execution time tuner");
181 SYSCTL_ADD_PROC(&random_clist,
182 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
183 "fastthresh", CTLTYPE_INT|CTLFLAG_RW,
184 &yarrow_state.pool[0].thresh, (3*(BLOCKSIZE*8))/4,
185 random_check_uint_fastthresh, "I",
186 "Fast reseed threshold");
188 SYSCTL_ADD_PROC(&random_clist,
189 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
190 "slowthresh", CTLTYPE_INT|CTLFLAG_RW,
191 &yarrow_state.pool[1].thresh, (BLOCKSIZE*8),
192 random_check_uint_slowthresh, "I",
193 "Slow reseed threshold");
195 SYSCTL_ADD_PROC(&random_clist,
196 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
197 "slowoverthresh", CTLTYPE_INT|CTLFLAG_RW,
198 &yarrow_state.slowoverthresh, 2,
199 random_check_uint_slowoverthresh, "I",
200 "Slow over-threshold reseed");
203 yarrow_state.gengateinterval = 10;
204 yarrow_state.bins = 10;
205 yarrow_state.pool[FAST].thresh = (3*(BLOCKSIZE*8))/4;
206 yarrow_state.pool[SLOW].thresh = (BLOCKSIZE*8);
207 yarrow_state.slowoverthresh = 2;
209 /* Ensure that the first time we read, we are gated. */
210 yarrow_state.outputblocks = yarrow_state.gengateinterval;
212 /* Initialise the fast and slow entropy pools */
213 for (i = FAST; i <= SLOW; i++) {
214 randomdev_hash_init(&yarrow_state.pool[i].hash);
215 for (j = RANDOM_START; j < ENTROPYSOURCE; j++)
216 yarrow_state.pool[i].source[j].bits = 0U;
219 /* Clear the counter */
220 uint128_clear(&yarrow_state.counter.whole);
224 random_yarrow_deinit_alg(void)
227 mtx_destroy(&random_reseed_mtx);
228 memset(&yarrow_state, 0, sizeof(yarrow_state));
231 sysctl_ctx_free(&random_clist);
236 random_yarrow_post_insert(void)
238 u_int pl, overthreshhold[2];
239 enum random_entropy_source src;
242 mtx_assert(&random_reseed_mtx, MA_OWNED);
244 /* Count the over-threshold sources in each pool */
245 for (pl = 0; pl < 2; pl++) {
246 overthreshhold[pl] = 0;
247 for (src = RANDOM_START; src < ENTROPYSOURCE; src++) {
248 if (yarrow_state.pool[pl].source[src].bits > yarrow_state.pool[pl].thresh)
249 overthreshhold[pl]++;
253 /* If enough slow sources are over threshhold, then slow reseed
254 * else if any fast source over threshhold, then fast reseed.
256 if (overthreshhold[SLOW] >= yarrow_state.slowoverthresh)
258 else if (overthreshhold[FAST] > 0 && yarrow_state.seeded)
262 /* Process a single stochastic event off the harvest queue */
264 random_yarrow_process_event(struct harvest_event *event)
268 mtx_lock(&random_reseed_mtx);
270 /* Accumulate the event into the appropriate pool
271 * where each event carries the destination information.
272 * We lock against pool state modification which can happen
273 * during accumulation/reseeding and reading/regating
275 pl = event->he_destination % 2;
276 randomdev_hash_iterate(&yarrow_state.pool[pl].hash, event, sizeof(*event));
277 yarrow_state.pool[pl].source[event->he_source].bits += event->he_bits;
279 random_yarrow_post_insert();
281 mtx_unlock(&random_reseed_mtx);
284 /* Process a block of data suspected to be slightly stochastic */
286 random_yarrow_process_buffer(uint8_t *buf, u_int length)
288 static struct harvest_event event;
291 /* Accumulate the data into the appropriate pools
292 * where each event carries the destination information.
293 * We lock against pool state modification which can happen
294 * during accumulation/reseeding and reading/regating
296 memset(event.he_entropy + sizeof(uint32_t), 0, HARVESTSIZE - sizeof(uint32_t));
297 for (i = 0; i < length/sizeof(uint32_t); i++) {
298 event.he_somecounter = get_cyclecount();
299 event.he_bits = 0; /* Fake */
300 event.he_source = RANDOM_CACHED;
301 event.he_destination = harvest_destination[RANDOM_CACHED]++;
302 event.he_size = sizeof(uint32_t);
303 *((uint32_t *)event.he_entropy) = *((uint32_t *)buf + i);
305 /* Do the actual entropy insertion */
306 pl = event.he_destination % 2;
307 randomdev_hash_iterate(&yarrow_state.pool[pl].hash, &event, sizeof(event));
308 #ifdef DONT_DO_THIS_HERE
309 /* Don't do this here - do it in bulk at the end */
310 yarrow_state.pool[pl].source[RANDOM_CACHED].bits += bits;
313 for (pl = FAST; pl <= SLOW; pl++)
314 yarrow_state.pool[pl].source[RANDOM_CACHED].bits += (length >> 4);
316 random_yarrow_post_insert();
320 reseed(u_int fastslow)
322 /* Interrupt-context stack is a limited resource; make large
325 static uint8_t v[TIMEBIN][KEYSIZE]; /* v[i] */
326 static uint8_t hash[KEYSIZE]; /* h' */
327 static uint8_t temp[KEYSIZE];
328 static struct randomdev_hash context;
330 enum random_entropy_source j;
332 KASSERT(yarrow_state.pool[FAST].thresh > 0, ("random: Yarrow fast threshold = 0"));
333 KASSERT(yarrow_state.pool[SLOW].thresh > 0, ("random: Yarrow slow threshold = 0"));
336 #ifdef RANDOM_DEBUG_VERBOSE
337 printf("random: %s %s\n", __func__, (fastslow == FAST ? "FAST" : "SLOW"));
339 if (!yarrow_state.seeded) {
340 printf("random: %s - fast - thresh %d,1 - ", __func__, yarrow_state.pool[FAST].thresh);
341 for (i = RANDOM_START; i < ENTROPYSOURCE; i++)
342 printf(" %d", yarrow_state.pool[FAST].source[i].bits);
344 printf("random: %s - slow - thresh %d,%d - ", __func__, yarrow_state.pool[SLOW].thresh, yarrow_state.slowoverthresh);
345 for (i = RANDOM_START; i < ENTROPYSOURCE; i++)
346 printf(" %d", yarrow_state.pool[SLOW].source[i].bits);
351 mtx_assert(&random_reseed_mtx, MA_OWNED);
354 /* 1. Hash the accumulated entropy into v[0] */
356 randomdev_hash_init(&context);
357 /* Feed the slow pool hash in if slow */
358 if (fastslow == SLOW) {
359 randomdev_hash_finish(&yarrow_state.pool[SLOW].hash, temp);
360 randomdev_hash_iterate(&context, temp, sizeof(temp));
362 randomdev_hash_finish(&yarrow_state.pool[FAST].hash, temp);
363 randomdev_hash_iterate(&context, temp, sizeof(temp));
364 randomdev_hash_finish(&context, v[0]);
366 /* 2. Compute hash values for all v. _Supposed_ to be computationally
370 if (yarrow_state.bins > TIMEBIN)
371 yarrow_state.bins = TIMEBIN;
372 for (i = 1; i < yarrow_state.bins; i++) {
373 randomdev_hash_init(&context);
374 /* v[i] #= h(v[i - 1]) */
375 randomdev_hash_iterate(&context, v[i - 1], KEYSIZE);
376 /* v[i] #= h(v[0]) */
377 randomdev_hash_iterate(&context, v[0], KEYSIZE);
379 randomdev_hash_iterate(&context, &i, sizeof(i));
380 /* Return the hashval */
381 randomdev_hash_finish(&context, v[i]);
384 /* 3. Compute a new key; h' is the identity function here;
385 * it is not being ignored!
388 randomdev_hash_init(&context);
389 randomdev_hash_iterate(&context, &yarrow_state.key, KEYSIZE);
390 for (i = 1; i < yarrow_state.bins; i++)
391 randomdev_hash_iterate(&context, v[i], KEYSIZE);
392 randomdev_hash_finish(&context, temp);
393 randomdev_encrypt_init(&yarrow_state.key, temp);
395 /* 4. Recompute the counter */
397 uint128_clear(&yarrow_state.counter.whole);
398 randomdev_encrypt(&yarrow_state.key, yarrow_state.counter.byte, temp, BLOCKSIZE);
399 memcpy(yarrow_state.counter.byte, temp, BLOCKSIZE);
401 /* 5. Reset entropy estimate accumulators to zero */
403 for (i = 0; i <= fastslow; i++)
404 for (j = RANDOM_START; j < ENTROPYSOURCE; j++)
405 yarrow_state.pool[i].source[j].bits = 0;
407 /* 6. Wipe memory of intermediate values */
409 memset(v, 0, sizeof(v));
410 memset(temp, 0, sizeof(temp));
411 memset(hash, 0, sizeof(hash));
412 memset(&context, 0, sizeof(context));
414 #ifdef RANDOM_RWFILE_WRITE_IS_OK /* Not defined so writes ain't gonna happen */
415 /* 7. Dump to seed file */
417 /* This pseudo-code is documentation. Please leave it alone. */
418 seed_file = "<some file>";
419 error = randomdev_write_file(seed_file, <generated entropy>, PAGE_SIZE);
421 printf("random: entropy seed file '%s' successfully written\n", seed_file);
424 /* Unblock the device if it was blocked due to being unseeded */
425 if (!yarrow_state.seeded) {
426 yarrow_state.seeded = 1;
427 random_adaptor_unblock();
431 /* Internal function to return processed entropy from the PRNG */
433 random_yarrow_read(uint8_t *buf, u_int bytecount)
435 uint8_t tbuf[BLOCKSIZE];
438 /* Check for initial/final read requests */
442 /* The reseed task must not be jumped on */
443 mtx_lock(&random_reseed_mtx);
445 blockcount = (bytecount + BLOCKSIZE - 1)/BLOCKSIZE;
446 for (i = 0; i < blockcount; i++) {
447 if (yarrow_state.outputblocks++ >= yarrow_state.gengateinterval) {
449 yarrow_state.outputblocks = 0;
451 uint128_increment(&yarrow_state.counter.whole);
452 if ((i + 1) * BLOCKSIZE > bytecount) {
453 /* TODO: FIX! remove memcpy()! */
454 randomdev_encrypt(&yarrow_state.key,
455 yarrow_state.counter.byte, tbuf, BLOCKSIZE);
456 memcpy(buf, tbuf, bytecount - i * BLOCKSIZE);
458 randomdev_encrypt(&yarrow_state.key,
459 yarrow_state.counter.byte, buf, BLOCKSIZE);
464 mtx_unlock(&random_reseed_mtx);
467 /* Internal function to hand external entropy to the PRNG */
469 random_yarrow_write(uint8_t *buf, u_int count)
473 /* We must be locked for all this as plenty of state gets messed with */
474 mtx_lock(&random_reseed_mtx);
476 timestamp = get_cyclecount();
477 randomdev_hash_iterate(&yarrow_state.start_cache.hash, ×tamp, sizeof(timestamp));
478 randomdev_hash_iterate(&yarrow_state.start_cache.hash, buf, count);
479 timestamp = get_cyclecount();
480 randomdev_hash_iterate(&yarrow_state.start_cache.hash, ×tamp, sizeof(timestamp));
481 randomdev_hash_finish(&yarrow_state.start_cache.hash, yarrow_state.start_cache.junk);
482 randomdev_hash_init(&yarrow_state.start_cache.hash);
484 #ifdef RANDOM_DEBUG_VERBOSE
488 printf("random: %s - ", __func__);
489 for (i = 0; i < KEYSIZE; i++)
490 printf("%02X", yarrow_state.start_cache.junk[i]);
495 random_yarrow_process_buffer(yarrow_state.start_cache.junk, KEYSIZE);
496 memset(yarrow_state.start_cache.junk, 0, KEYSIZE);
498 mtx_unlock(&random_reseed_mtx);
505 uint8_t temp[KEYSIZE];
507 for (i = 0; i < KEYSIZE; i += BLOCKSIZE) {
508 uint128_increment(&yarrow_state.counter.whole);
509 randomdev_encrypt(&yarrow_state.key, yarrow_state.counter.byte, temp + i, BLOCKSIZE);
512 randomdev_encrypt_init(&yarrow_state.key, temp);
513 memset(temp, 0, KEYSIZE);
517 random_yarrow_reseed(void)
520 mtx_lock(&random_reseed_mtx);
522 mtx_unlock(&random_reseed_mtx);
526 random_yarrow_seeded(void)
529 return (yarrow_state.seeded);
532 #endif /* RANDOM_YARROW */