yarrow.c revision 91600 
1/*-
2 * Copyright (c) 2000 Mark R V Murray
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
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.
14 *
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.
25 *
26 * $FreeBSD: head/sys/dev/random/yarrow.c 91600 2002-03-03 19:44:22Z markm $
27 */
28
29#include <sys/param.h>
30#include <sys/systm.h>
31#include <sys/kernel.h>
32#include <sys/lock.h>
33#include <sys/mutex.h>
34#include <sys/random.h>
35#include <sys/sysctl.h>
36
37#include <crypto/rijndael/rijndael.h>
38
39#include <dev/random/hash.h>
40#include <dev/random/randomdev.h>
41#include <dev/random/yarrow.h>
42
43/* #define DEBUG */
44
45RANDOM_CHECK_UINT(gengateinterval, 4, 64);
46RANDOM_CHECK_UINT(bins, 2, 16);
47RANDOM_CHECK_UINT(fastthresh, BLOCKSIZE/4, BLOCKSIZE);
48RANDOM_CHECK_UINT(slowthresh, BLOCKSIZE/4, BLOCKSIZE);
49RANDOM_CHECK_UINT(slowoverthresh, 1, 5);
50
51/* Structure holding the entropy state */
52static struct random_state random_state;
53
54SYSCTL_NODE(_kern_random, OID_AUTO, yarrow, CTLFLAG_RW, 0, "Yarrow Parameters");
55SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, gengateinterval,
56	CTLTYPE_INT|CTLFLAG_RW, &random_state.gengateinterval, 10,
57	random_check_uint_gengateinterval, "I", "Generator Gate Interval");
58SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, bins,
59	CTLTYPE_INT|CTLFLAG_RW, &random_state.bins, 10,
60	random_check_uint_bins, "I", "Execution time tuner");
61SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, fastthresh,
62	CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[0].thresh, (3*BLOCKSIZE)/4,
63	random_check_uint_fastthresh, "I", "Fast reseed threshold");
64SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowthresh,
65	CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[1].thresh, BLOCKSIZE,
66	random_check_uint_slowthresh, "I", "Slow reseed threshold");
67SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowoverthresh,
68	CTLTYPE_INT|CTLFLAG_RW, &random_state.slowoverthresh, 2,
69	random_check_uint_slowoverthresh, "I", "Slow over-threshold reseed");
70
71static void generator_gate(void);
72static void reseed(u_int);
73
74/* The reseed thread mutex */
75static struct mtx random_reseed_mtx;
76
77/* Process a single stochastic event off the harvest queue */
78void
79random_process_event(struct harvest *event)
80{
81	u_int pl, overthreshhold[2];
82	struct source *source;
83	enum esource src;
84
85	/* Unpack the event into the appropriate source accumulator */
86	pl = random_state.which;
87	source = &random_state.pool[pl].source[event->source];
88	yarrow_hash_iterate(&random_state.pool[pl].hash, event->entropy,
89		sizeof(event->entropy));
90	yarrow_hash_iterate(&random_state.pool[pl].hash, &event->somecounter,
91		sizeof(event->somecounter));
92	source->frac += event->frac;
93	source->bits += event->bits + source->frac/1024;
94	source->frac %= 1024;
95
96	/* Count the over-threshold sources in each pool */
97	for (pl = 0; pl < 2; pl++) {
98		overthreshhold[pl] = 0;
99		for (src = RANDOM_START; src < ENTROPYSOURCE; src++) {
100			if (random_state.pool[pl].source[src].bits
101				> random_state.pool[pl].thresh)
102				overthreshhold[pl]++;
103		}
104	}
105
106	/* if any fast source over threshhold, reseed */
107	if (overthreshhold[FAST])
108		reseed(FAST);
109
110	/* if enough slow sources are over threshhold, reseed */
111	if (overthreshhold[SLOW] >= random_state.slowoverthresh)
112		reseed(SLOW);
113
114	/* Invert the fast/slow pool selector bit */
115	random_state.which = !random_state.which;
116}
117
118void
119random_init(void)
120{
121	int i;
122
123	/* Yarrow parameters. Do not adjust these unless you have
124	 * have a very good clue about what they do!
125	 */
126	random_state.gengateinterval = 10;
127	random_state.bins = 10;
128	random_state.pool[0].thresh = (3*BLOCKSIZE)/4;
129	random_state.pool[1].thresh = BLOCKSIZE;
130	random_state.slowoverthresh = 2;
131	random_state.which = FAST;
132
133	/* Initialise the fast and slow entropy pools */
134	for (i = 0; i < 2; i++)
135		yarrow_hash_init(&random_state.pool[i].hash);
136
137	/* Clear the counter */
138	for (i = 0; i < 4; i++)
139		random_state.counter[i] = 0;
140
141	/* Set up a lock for the reseed process */
142	mtx_init(&random_reseed_mtx, "random reseed", MTX_DEF);
143}
144
145void
146random_deinit(void)
147{
148	mtx_destroy(&random_reseed_mtx);
149}
150
151static void
152reseed(u_int fastslow)
153{
154	/* Interrupt-context stack is a limited resource; make large
155	 * structures static.
156	 */
157	static u_char v[TIMEBIN][KEYSIZE];	/* v[i] */
158	static struct yarrowhash context;
159	u_char hash[KEYSIZE];			/* h' */
160	u_char temp[KEYSIZE];
161	u_int i;
162	enum esource j;
163
164#ifdef DEBUG
165	mtx_lock(&Giant);
166	printf("Reseed type %d\n", fastslow);
167	mtx_unlock(&Giant);
168#endif
169
170	/* The reseed task must not be jumped on */
171	mtx_lock(&random_reseed_mtx);
172
173	/* 1. Hash the accumulated entropy into v[0] */
174
175	yarrow_hash_init(&context);
176	/* Feed the slow pool hash in if slow */
177	if (fastslow == SLOW)
178		yarrow_hash_iterate(&context,
179			&random_state.pool[SLOW].hash,
180			sizeof(struct yarrowhash));
181	yarrow_hash_iterate(&context,
182		&random_state.pool[FAST].hash, sizeof(struct yarrowhash));
183	yarrow_hash_finish(&context, v[0]);
184
185	/* 2. Compute hash values for all v. _Supposed_ to be computationally
186	 *    intensive.
187	 */
188
189	if (random_state.bins > TIMEBIN)
190		random_state.bins = TIMEBIN;
191	for (i = 1; i < random_state.bins; i++) {
192		yarrow_hash_init(&context);
193		/* v[i] #= h(v[i - 1]) */
194		yarrow_hash_iterate(&context, v[i - 1], KEYSIZE);
195		/* v[i] #= h(v[0]) */
196		yarrow_hash_iterate(&context, v[0], KEYSIZE);
197		/* v[i] #= h(i) */
198		yarrow_hash_iterate(&context, &i, sizeof(u_int));
199		/* Return the hashval */
200		yarrow_hash_finish(&context, v[i]);
201	}
202
203	/* 3. Compute a new key; h' is the identity function here;
204	 *    it is not being ignored!
205	 */
206
207	yarrow_hash_init(&context);
208	yarrow_hash_iterate(&context, &random_state.key, KEYSIZE);
209	for (i = 1; i < random_state.bins; i++)
210		yarrow_hash_iterate(&context, &v[i], KEYSIZE);
211	yarrow_hash_finish(&context, temp);
212	yarrow_encrypt_init(&random_state.key, temp);
213
214	/* 4. Recompute the counter */
215
216	for (i = 0; i < 4; i++)
217		random_state.counter[i] = 0;
218	yarrow_encrypt(&random_state.key, random_state.counter, temp);
219	memcpy(random_state.counter, temp, sizeof(random_state.counter));
220
221	/* 5. Reset entropy estimate accumulators to zero */
222
223	for (i = 0; i <= fastslow; i++) {
224		for (j = RANDOM_START; j < ENTROPYSOURCE; j++) {
225			random_state.pool[i].source[j].bits = 0;
226			random_state.pool[i].source[j].frac = 0;
227		}
228	}
229
230	/* 6. Wipe memory of intermediate values */
231
232	memset((void *)v, 0, sizeof(v));
233	memset((void *)temp, 0, sizeof(temp));
234	memset((void *)hash, 0, sizeof(hash));
235
236	/* 7. Dump to seed file */
237	/* XXX Not done here yet */
238
239	/* Release the reseed mutex */
240	mtx_unlock(&random_reseed_mtx);
241
242#ifdef DEBUG
243	mtx_lock(&Giant);
244	printf("Reseed finish\n");
245	mtx_unlock(&Giant);
246#endif
247
248	/* Unblock the device if it was blocked due to being unseeded */
249	random_unblock();
250}
251
252/* Internal function to do return processed entropy from the
253 * Yarrow PRNG
254 */
255int
256read_random_real(void *buf, int count)
257{
258	static int cur = 0;
259	static int gate = 1;
260	static u_char genval[KEYSIZE];
261	int i;
262	int retval;
263
264	/* The reseed task must not be jumped on */
265	mtx_lock(&random_reseed_mtx);
266
267	if (gate) {
268		generator_gate();
269		random_state.outputblocks = 0;
270		gate = 0;
271	}
272	if (count > 0 && (size_t)count >= sizeof(random_state.counter)) {
273		retval = 0;
274		for (i = 0; i < count; i += (int)sizeof(random_state.counter)) {
275			random_state.counter[0]++;
276			yarrow_encrypt(&random_state.key, random_state.counter,
277				genval);
278			memcpy((char *)buf + i, genval,
279				sizeof(random_state.counter));
280			if (++random_state.outputblocks >=
281				random_state.gengateinterval) {
282				generator_gate();
283				random_state.outputblocks = 0;
284			}
285			retval += (int)sizeof(random_state.counter);
286		}
287	}
288	else {
289		if (!cur) {
290			random_state.counter[0]++;
291			yarrow_encrypt(&random_state.key, random_state.counter,
292				genval);
293			memcpy(buf, genval, (size_t)count);
294			cur = (int)sizeof(random_state.counter) - count;
295			if (++random_state.outputblocks >=
296				random_state.gengateinterval) {
297				generator_gate();
298				random_state.outputblocks = 0;
299			}
300			retval = count;
301		}
302		else {
303			retval = cur < count ? cur : count;
304			memcpy(buf,
305			    &genval[(int)sizeof(random_state.counter) - cur],
306			    (size_t)retval);
307			cur -= retval;
308		}
309	}
310	mtx_unlock(&random_reseed_mtx);
311	return retval;
312}
313
314static void
315generator_gate(void)
316{
317	u_int i;
318	u_char temp[KEYSIZE];
319
320#ifdef DEBUG
321	mtx_lock(&Giant);
322	printf("Generator gate\n");
323	mtx_unlock(&Giant);
324#endif
325
326	for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) {
327		random_state.counter[0]++;
328		yarrow_encrypt(&random_state.key, random_state.counter,
329			&(temp[i]));
330	}
331
332	yarrow_encrypt_init(&random_state.key, temp);
333	memset((void *)temp, 0, KEYSIZE);
334
335#ifdef DEBUG
336	mtx_lock(&Giant);
337	printf("Generator gate finish\n");
338	mtx_unlock(&Giant);
339#endif
340}
341
342/* Helper routine to perform explicit reseeds */
343void
344random_reseed(void)
345{
346	reseed(FAST);
347}
348