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$");
31 #include "opt_random.h"
33 #include <sys/param.h>
34 #include <sys/kernel.h>
36 #include <sys/malloc.h>
37 #include <sys/mutex.h>
38 #include <sys/random.h>
39 #include <sys/sysctl.h>
40 #include <sys/systm.h>
42 #include <crypto/rijndael/rijndael-api-fst.h>
43 #include <crypto/sha2/sha256.h>
45 #include <dev/random/hash.h>
46 #include <dev/random/random_adaptors.h>
47 #include <dev/random/randomdev_soft.h>
48 #include <dev/random/yarrow.h>
50 #define TIMEBIN 16 /* max value for Pt/t */
55 /* This is the beastie that needs protecting. It contains all of the
56 * state that we are excited about.
57 * Exactly one is instantiated.
59 static struct random_state {
61 uint8_t byte[BLOCKSIZE];
62 uint64_t qword[BLOCKSIZE/sizeof(uint64_t)];
64 struct randomdev_key key; /* K */
65 u_int gengateinterval; /* Pg */
66 u_int bins; /* Pt/t */
67 u_int outputblocks; /* count output blocks for gates */
68 u_int slowoverthresh; /* slow pool overthreshhold reseed count */
71 u_int bits; /* estimated bits of entropy */
72 } source[ENTROPYSOURCE];
73 u_int thresh; /* pool reseed threshhold */
74 struct randomdev_hash hash; /* accumulated entropy */
75 } pool[2]; /* pool[0] is fast, pool[1] is slow */
76 u_int which; /* toggle - sets the current insertion pool */
79 RANDOM_CHECK_UINT(gengateinterval, 4, 64);
80 RANDOM_CHECK_UINT(bins, 2, 16);
81 RANDOM_CHECK_UINT(fastthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */
82 RANDOM_CHECK_UINT(slowthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */
83 RANDOM_CHECK_UINT(slowoverthresh, 1, 5);
85 static void generator_gate(void);
86 static void reseed(u_int);
88 /* The reseed thread mutex */
89 struct mtx random_reseed_mtx;
92 /* Nothing to see here, folks, just an ugly mess. */
96 random_state.counter.qword[0] = 0UL;
97 random_state.counter.qword[1] = 0UL;
100 /* 128-bit C = C + 1 */
101 /* Nothing to see here, folks, just an ugly mess. */
102 /* TODO: Make a Galois counter instead? */
104 increment_counter(void)
106 random_state.counter.qword[0]++;
107 if (!random_state.counter.qword[0])
108 random_state.counter.qword[1]++;
111 /* Process a single stochastic event off the harvest queue */
113 random_process_event(struct harvest *event)
115 u_int pl, overthreshhold[2];
116 struct source *source;
120 /* Do this better with DTrace */
124 printf("Harvest:%16jX ", event->somecounter);
125 for (i = 0; i < event->size; i++)
126 printf("%02X", event->entropy[i]);
129 printf(" %2d %2d %02X\n", event->size, event->bits, event->source);
133 /* Accumulate the event into the appropriate pool */
134 pl = random_state.which;
135 source = &random_state.pool[pl].source[event->source];
136 randomdev_hash_iterate(&random_state.pool[pl].hash, event,
138 source->bits += event->bits;
140 /* Count the over-threshold sources in each pool */
141 for (pl = 0; pl < 2; pl++) {
142 overthreshhold[pl] = 0;
143 for (src = RANDOM_START; src < ENTROPYSOURCE; src++) {
144 if (random_state.pool[pl].source[src].bits
145 > random_state.pool[pl].thresh)
146 overthreshhold[pl]++;
150 /* if any fast source over threshhold, reseed */
151 if (overthreshhold[FAST])
154 /* if enough slow sources are over threshhold, reseed */
155 if (overthreshhold[SLOW] >= random_state.slowoverthresh)
158 /* Invert the fast/slow pool selector bit */
159 random_state.which = !random_state.which;
163 random_yarrow_init_alg(struct sysctl_ctx_list *clist)
166 struct sysctl_oid *random_yarrow_o;
168 /* Yarrow parameters. Do not adjust these unless you have
169 * have a very good clue about what they do!
171 random_yarrow_o = SYSCTL_ADD_NODE(clist,
172 SYSCTL_STATIC_CHILDREN(_kern_random),
173 OID_AUTO, "yarrow", CTLFLAG_RW, 0,
174 "Yarrow Parameters");
176 SYSCTL_ADD_PROC(clist,
177 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
178 "gengateinterval", CTLTYPE_INT|CTLFLAG_RW,
179 &random_state.gengateinterval, 10,
180 random_check_uint_gengateinterval, "I",
181 "Generation gate interval");
183 SYSCTL_ADD_PROC(clist,
184 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
185 "bins", CTLTYPE_INT|CTLFLAG_RW,
186 &random_state.bins, 10,
187 random_check_uint_bins, "I",
188 "Execution time tuner");
190 SYSCTL_ADD_PROC(clist,
191 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
192 "fastthresh", CTLTYPE_INT|CTLFLAG_RW,
193 &random_state.pool[0].thresh, (3*(BLOCKSIZE*8))/4,
194 random_check_uint_fastthresh, "I",
195 "Fast reseed threshold");
197 SYSCTL_ADD_PROC(clist,
198 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
199 "slowthresh", CTLTYPE_INT|CTLFLAG_RW,
200 &random_state.pool[1].thresh, (BLOCKSIZE*8),
201 random_check_uint_slowthresh, "I",
202 "Slow reseed threshold");
204 SYSCTL_ADD_PROC(clist,
205 SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO,
206 "slowoverthresh", CTLTYPE_INT|CTLFLAG_RW,
207 &random_state.slowoverthresh, 2,
208 random_check_uint_slowoverthresh, "I",
209 "Slow over-threshold reseed");
211 random_state.gengateinterval = 10;
212 random_state.bins = 10;
213 random_state.pool[0].thresh = (3*(BLOCKSIZE*8))/4;
214 random_state.pool[1].thresh = (BLOCKSIZE*8);
215 random_state.slowoverthresh = 2;
216 random_state.which = FAST;
218 /* Initialise the fast and slow entropy pools */
219 for (i = 0; i < 2; i++)
220 randomdev_hash_init(&random_state.pool[i].hash);
222 /* Clear the counter */
225 /* Set up a lock for the reseed process */
226 mtx_init(&random_reseed_mtx, "Yarrow reseed", NULL, MTX_DEF);
230 random_yarrow_deinit_alg(void)
232 mtx_destroy(&random_reseed_mtx);
236 reseed(u_int fastslow)
238 /* Interrupt-context stack is a limited resource; make large
241 static uint8_t v[TIMEBIN][KEYSIZE]; /* v[i] */
242 static struct randomdev_hash context;
243 uint8_t hash[KEYSIZE]; /* h' */
244 uint8_t temp[KEYSIZE];
249 printf("Yarrow: %s reseed\n", fastslow == FAST ? "fast" : "slow");
252 /* The reseed task must not be jumped on */
253 mtx_lock(&random_reseed_mtx);
255 /* 1. Hash the accumulated entropy into v[0] */
257 randomdev_hash_init(&context);
258 /* Feed the slow pool hash in if slow */
259 if (fastslow == SLOW)
260 randomdev_hash_iterate(&context,
261 &random_state.pool[SLOW].hash,
262 sizeof(struct randomdev_hash));
263 randomdev_hash_iterate(&context,
264 &random_state.pool[FAST].hash, sizeof(struct randomdev_hash));
265 randomdev_hash_finish(&context, v[0]);
267 /* 2. Compute hash values for all v. _Supposed_ to be computationally
271 if (random_state.bins > TIMEBIN)
272 random_state.bins = TIMEBIN;
273 for (i = 1; i < random_state.bins; i++) {
274 randomdev_hash_init(&context);
275 /* v[i] #= h(v[i - 1]) */
276 randomdev_hash_iterate(&context, v[i - 1], KEYSIZE);
277 /* v[i] #= h(v[0]) */
278 randomdev_hash_iterate(&context, v[0], KEYSIZE);
280 randomdev_hash_iterate(&context, &i, sizeof(u_int));
281 /* Return the hashval */
282 randomdev_hash_finish(&context, v[i]);
285 /* 3. Compute a new key; h' is the identity function here;
286 * it is not being ignored!
289 randomdev_hash_init(&context);
290 randomdev_hash_iterate(&context, &random_state.key, KEYSIZE);
291 for (i = 1; i < random_state.bins; i++)
292 randomdev_hash_iterate(&context, &v[i], KEYSIZE);
293 randomdev_hash_finish(&context, temp);
294 randomdev_encrypt_init(&random_state.key, temp);
296 /* 4. Recompute the counter */
299 randomdev_encrypt(&random_state.key, random_state.counter.byte, temp, BLOCKSIZE);
300 memcpy(random_state.counter.byte, temp, BLOCKSIZE);
302 /* 5. Reset entropy estimate accumulators to zero */
304 for (i = 0; i <= fastslow; i++)
305 for (j = RANDOM_START; j < ENTROPYSOURCE; j++)
306 random_state.pool[i].source[j].bits = 0;
308 /* 6. Wipe memory of intermediate values */
310 memset((void *)v, 0, sizeof(v));
311 memset((void *)temp, 0, sizeof(temp));
312 memset((void *)hash, 0, sizeof(hash));
314 /* 7. Dump to seed file */
315 /* XXX Not done here yet */
317 /* Unblock the device if it was blocked due to being unseeded */
320 /* Release the reseed mutex */
321 mtx_unlock(&random_reseed_mtx);
324 /* Internal function to return processed entropy from the PRNG */
326 random_yarrow_read(void *buf, int count)
330 static uint8_t genval[KEYSIZE];
335 /* Check for final read request */
336 if (buf == NULL && count == 0)
339 /* The reseed task must not be jumped on */
340 mtx_lock(&random_reseed_mtx);
344 random_state.outputblocks = 0;
347 if (count > 0 && (size_t)count >= BLOCKSIZE) {
349 for (i = 0; i < count; i += BLOCKSIZE) {
351 randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE);
352 tomove = MIN(count - i, BLOCKSIZE);
353 memcpy((char *)buf + i, genval, tomove);
354 if (++random_state.outputblocks >= random_state.gengateinterval) {
356 random_state.outputblocks = 0;
358 retval += (int)tomove;
365 randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE);
366 memcpy(buf, genval, (size_t)count);
367 cur = BLOCKSIZE - count;
368 if (++random_state.outputblocks >= random_state.gengateinterval) {
370 random_state.outputblocks = 0;
375 retval = MIN(cur, count);
376 memcpy(buf, &genval[BLOCKSIZE - cur], (size_t)retval);
380 mtx_unlock(&random_reseed_mtx);
388 uint8_t temp[KEYSIZE];
390 for (i = 0; i < KEYSIZE; i += BLOCKSIZE) {
392 randomdev_encrypt(&random_state.key, random_state.counter.byte, temp + i, BLOCKSIZE);
395 randomdev_encrypt_init(&random_state.key, temp);
396 memset((void *)temp, 0, KEYSIZE);
399 /* Helper routine to perform explicit reseeds */
401 random_yarrow_reseed(void)
406 printf("%s(): fast:", __func__);
407 for (i = RANDOM_START; i < ENTROPYSOURCE; ++i)
408 printf(" %d", random_state.pool[FAST].source[i].bits);
410 printf("%s(): slow:", __func__);
411 for (i = RANDOM_START; i < ENTROPYSOURCE; ++i)
412 printf(" %d", random_state.pool[SLOW].source[i].bits);