entropy.c 31 KB
Newer Older
Michael Graff's avatar
Michael Graff committed
1
2
/*
 * Copyright (C) 2000  Internet Software Consortium.
3
 *
Michael Graff's avatar
Michael Graff committed
4
5
6
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
7
 *
8
9
10
11
12
13
14
15
 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM
 * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
 * INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
Michael Graff's avatar
Michael Graff committed
16
17
 */

18
/* $Id: entropy.c,v 1.48 2000/08/26 01:10:54 bwelling Exp $ */
David Lawrence's avatar
David Lawrence committed
19

Michael Graff's avatar
Michael Graff committed
20
21
#include <config.h>

David Lawrence's avatar
David Lawrence committed
22
#include <errno.h>
Michael Graff's avatar
Michael Graff committed
23
#include <fcntl.h>
Michael Graff's avatar
Michael Graff committed
24
#include <stdio.h>
Michael Graff's avatar
Michael Graff committed
25
#include <unistd.h>
Michael Graff's avatar
Michael Graff committed
26
27
28

#include <isc/buffer.h>
#include <isc/entropy.h>
29
#include <isc/list.h>
Michael Graff's avatar
Michael Graff committed
30
#include <isc/magic.h>
31
32
#include <isc/mem.h>
#include <isc/mutex.h>
Michael Graff's avatar
Michael Graff committed
33
#include <isc/region.h>
34
#include <isc/sha1.h>
Michael Graff's avatar
Michael Graff committed
35
#include <isc/string.h>
36
#include <isc/time.h>
Michael Graff's avatar
Michael Graff committed
37
38
39
40
41
42
43
#include <isc/util.h>

/*
 * Much of this code is modeled after the NetBSD /dev/random implementation,
 * written by Michael Graff <explorer@netbsd.org>.
 */

Michael Graff's avatar
Michael Graff committed
44
45
#define ENTROPY_MAGIC		ISC_MAGIC('E', 'n', 't', 'e')
#define SOURCE_MAGIC		ISC_MAGIC('E', 'n', 't', 's')
Michael Graff's avatar
Michael Graff committed
46

Michael Graff's avatar
Michael Graff committed
47
48
#define VALID_ENTROPY(e)	ISC_MAGIC_VALID(e, ENTROPY_MAGIC)
#define VALID_SOURCE(s)		ISC_MAGIC_VALID(s, SOURCE_MAGIC)
Michael Graff's avatar
Michael Graff committed
49

Michael Graff's avatar
Michael Graff committed
50
51
52
53
54
55
56
57
/***
 *** "constants."  Do not change these unless you _really_ know what
 *** you are doing.
 ***/

/*
 * size of entropy pool in 32-bit words.  This _MUST_ be a power of 2.
 */
58
#define RND_POOLWORDS	128
59
#define RND_POOLBITS	(RND_POOLWORDS * 32)
Michael Graff's avatar
Michael Graff committed
60
61

/*
62
63
 * Number of bytes returned per hash.  This must be true:
 *	threshold * 2 <= digest_size_in_bytes
Michael Graff's avatar
Michael Graff committed
64
 */
65
#define RND_ENTROPY_THRESHOLD	10
66
#define THRESHOLD_BITS		(RND_ENTROPY_THRESHOLD * 8)
Michael Graff's avatar
Michael Graff committed
67
68

/*
69
 * Size of the input event queue in samples.
Michael Graff's avatar
Michael Graff committed
70
 */
71
#define RND_EVENTQSIZE	32
Michael Graff's avatar
Michael Graff committed
72

73
74
75
76
77
78
79
80
81
/*
 * The number of times we'll "reseed" for pseudorandom seeds.  This is an
 * extremely weak pseudorandom seed.  If the caller is using lots of
 * pseudorandom data and they cannot provide a stronger random source,
 * there is little we can do other than hope they're smart enough to
 * call _adddata() with something better than we can come up with.
 */
#define RND_INITIALIZE	128

Michael Graff's avatar
Michael Graff committed
82
typedef struct {
Michael Graff's avatar
Michael Graff committed
83
	isc_uint32_t	magic;
Michael Graff's avatar
Michael Graff committed
84
85
	isc_uint32_t	cursor;		/* current add point in the pool */
	isc_uint32_t	entropy;	/* current entropy estimate in bits */
Michael Graff's avatar
Michael Graff committed
86
	isc_uint32_t	pseudo;		/* bits extracted in pseudorandom */
Michael Graff's avatar
Michael Graff committed
87
88
	isc_uint32_t	rotate;		/* how many bits to rotate by */
	isc_uint32_t	pool[RND_POOLWORDS];	/* random pool data */
89
90
91
} isc_entropypool_t;

struct isc_entropy {
Michael Graff's avatar
Michael Graff committed
92
	isc_uint32_t			magic;
93
	isc_mem_t		       *mctx;
94
	isc_mutex_t			lock;
95
	unsigned int			refcnt;
96
	isc_uint32_t			initialized;
97
	isc_uint32_t			initcount;
98
	isc_entropypool_t		pool;
99
100
	unsigned int			nsources;
	isc_entropysource_t	       *nextsource;
101
102
	ISC_LIST(isc_entropysource_t)	sources;
};
Michael Graff's avatar
Michael Graff committed
103
104

typedef struct {
Michael Graff's avatar
Michael Graff committed
105
106
107
	isc_uint32_t	last_time;	/* last time recorded */
	isc_uint32_t	last_delta;	/* last delta value */
	isc_uint32_t	last_delta2;	/* last delta2 value */
Michael Graff's avatar
Michael Graff committed
108
109
110
	isc_uint32_t	nsamples;	/* number of samples filled in */
	isc_uint32_t   *samples;	/* the samples */
	isc_uint32_t   *extra;		/* extra samples added in */
Michael Graff's avatar
Michael Graff committed
111
} sample_queue_t;
Michael Graff's avatar
Michael Graff committed
112

Michael Graff's avatar
Michael Graff committed
113
typedef struct {
Michael Graff's avatar
Michael Graff committed
114
115
116
117
	sample_queue_t	samplequeue;
} isc_entropysamplesource_t;

typedef struct {
118
	isc_boolean_t		start_called;
Michael Graff's avatar
Michael Graff committed
119
120
121
122
123
124
	isc_entropystart_t	startfunc;
	isc_entropyget_t	getfunc;
	isc_entropystop_t	stopfunc;
	void		       *arg;
	sample_queue_t		samplequeue;
} isc_cbsource_t;
Michael Graff's avatar
Michael Graff committed
125

Michael Graff's avatar
Michael Graff committed
126
127
typedef struct {
	int		fd;		/* fd for the file, or -1 if closed */
128
} isc_entropyfilesource_t;
Michael Graff's avatar
Michael Graff committed
129

130
struct isc_entropysource {
Michael Graff's avatar
Michael Graff committed
131
	isc_uint32_t	magic;
Michael Graff's avatar
Michael Graff committed
132
	unsigned int	type;
Michael Graff's avatar
Michael Graff committed
133
	isc_entropy_t  *ent;
Michael Graff's avatar
Michael Graff committed
134
	isc_uint32_t	total;		/* entropy from this source */
Michael Graff's avatar
Michael Graff committed
135
	ISC_LINK(isc_entropysource_t)	link;
Michael Graff's avatar
Michael Graff committed
136
137
	char		name[32];
	union {
Michael Graff's avatar
Michael Graff committed
138
139
		isc_entropysamplesource_t	sample;
		isc_entropyfilesource_t		file;
Michael Graff's avatar
Michael Graff committed
140
		isc_cbsource_t	callback;
Michael Graff's avatar
Michael Graff committed
141
	} sources;
142
};
Michael Graff's avatar
Michael Graff committed
143

Michael Graff's avatar
Michael Graff committed
144
145
#define ENTROPY_SOURCETYPE_SAMPLE	1	/* Type is a sample source */
#define ENTROPY_SOURCETYPE_FILE		2	/* Type is a file source */
Michael Graff's avatar
Michael Graff committed
146
#define ENTROPY_SOURCETYPE_CALLBACK	3	/* Type is a callback source */
Michael Graff's avatar
Michael Graff committed
147

148
149
150
151
152
153
154
155
156
157
158
159
/*
 * The random pool "taps"
 */
#define TAP1	99
#define TAP2	59
#define TAP3	31
#define TAP4	 9
#define TAP5	 7

static inline void
entropypool_add_word(isc_entropypool_t *, isc_uint32_t);

Michael Graff's avatar
Michael Graff committed
160
161
162
static void
fillpool(isc_entropy_t *, unsigned int, isc_boolean_t);

163
164
165
static int
wait_for_sources(isc_entropy_t *);

166
167
168
static unsigned int
crunchsamples(isc_entropy_t *, sample_queue_t *sq);

169
170
171
static inline void
reseed(isc_entropy_t *ent);

Michael Graff's avatar
Michael Graff committed
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
static void
samplequeue_release(isc_entropy_t *ent, sample_queue_t *sq) {
	REQUIRE(sq->samples != NULL);
	REQUIRE(sq->extra != NULL);

	isc_mem_put(ent->mctx, sq->samples, RND_EVENTQSIZE * 4);
	isc_mem_put(ent->mctx, sq->extra, RND_EVENTQSIZE * 4);
	sq->samples = NULL;
	sq->extra = NULL;
}

static isc_result_t
samplesource_allocate(isc_entropy_t *ent, sample_queue_t *sq) {
	sq->samples = isc_mem_get(ent->mctx, RND_EVENTQSIZE * 4);
	if (sq->samples == NULL)
		return (ISC_R_NOMEMORY);

	sq->extra = isc_mem_get(ent->mctx, RND_EVENTQSIZE * 4);
	if (sq->extra == NULL) {
		isc_mem_put(ent->mctx, sq->samples, RND_EVENTQSIZE * 4);
		sq->samples = NULL;
		return (ISC_R_NOMEMORY);
	}

196
197
	sq->nsamples = 0;

Michael Graff's avatar
Michael Graff committed
198
199
200
	return (ISC_R_SUCCESS);
}

Michael Graff's avatar
Michael Graff committed
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
/*
 * Add in entropy, even when the value we're adding in could be
 * very large.
 */
static inline void
add_entropy(isc_entropy_t *ent, isc_uint32_t entropy) {
	/* clamp input.  Yes, this must be done. */
	entropy = ISC_MIN(entropy, RND_POOLBITS);
	/* Add in the entropy we already have. */
	entropy += ent->pool.entropy;
	/* Clamp. */
	ent->pool.entropy = ISC_MIN(entropy, RND_POOLBITS);
}

/*
 * Decrement the amount of entropy the pool has.
 */
static inline void
subtract_entropy(isc_entropy_t *ent, isc_uint32_t entropy) {
	entropy = ISC_MIN(entropy, ent->pool.entropy);
	ent->pool.entropy -= entropy;
}

/*
 * Add in entropy, even when the value we're adding in could be
 * very large.
 */
static inline void
229
add_pseudo(isc_entropy_t *ent, isc_uint32_t pseudo) {
Michael Graff's avatar
Michael Graff committed
230
	/* clamp input.  Yes, this must be done. */
231
232
233
	pseudo = ISC_MIN(pseudo, RND_POOLBITS * 8);
	/* Add in the pseudo we already have. */
	pseudo += ent->pool.pseudo;
Michael Graff's avatar
Michael Graff committed
234
	/* Clamp. */
235
	ent->pool.pseudo = ISC_MIN(pseudo, RND_POOLBITS * 8);
Michael Graff's avatar
Michael Graff committed
236
237
238
}

/*
239
 * Decrement the amount of pseudo the pool has.
Michael Graff's avatar
Michael Graff committed
240
241
 */
static inline void
242
243
244
subtract_pseudo(isc_entropy_t *ent, isc_uint32_t pseudo) {
	pseudo = ISC_MIN(pseudo, ent->pool.pseudo);
	ent->pool.pseudo -= pseudo;
Michael Graff's avatar
Michael Graff committed
245
}
Michael Graff's avatar
Michael Graff committed
246

247
248
249
250
/*
 * Add one word to the pool, rotating the input as needed.
 */
static inline void
Michael Graff's avatar
Michael Graff committed
251
entropypool_add_word(isc_entropypool_t *rp, isc_uint32_t val) {
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
	/*
	 * Steal some values out of the pool, and xor them into the
	 * word we were given.
	 *
	 * Mix the new value into the pool using xor.  This will
	 * prevent the actual values from being known to the caller
	 * since the previous values are assumed to be unknown as well.
	 */
	val ^= rp->pool[(rp->cursor + TAP1) & (RND_POOLWORDS - 1)];
	val ^= rp->pool[(rp->cursor + TAP2) & (RND_POOLWORDS - 1)];
	val ^= rp->pool[(rp->cursor + TAP3) & (RND_POOLWORDS - 1)];
	val ^= rp->pool[(rp->cursor + TAP4) & (RND_POOLWORDS - 1)];
	val ^= rp->pool[(rp->cursor + TAP5) & (RND_POOLWORDS - 1)];
	rp->pool[rp->cursor++] ^=
	  ((val << rp->rotate) | (val >> (32 - rp->rotate)));

	/*
	 * If we have looped around the pool, increment the rotate
	 * variable so the next value will get xored in rotated to
	 * a different position.
	 * Increment by a value that is relativly prime to the word size
	 * to try to spread the bits throughout the pool quickly when the
	 * pool is empty.
	 */
	if (rp->cursor == RND_POOLWORDS) {
		rp->cursor = 0;
		rp->rotate = (rp->rotate + 7) & 31;
	}
}

/*
Michael Graff's avatar
Michael Graff committed
283
284
285
 * Add a buffer's worth of data to the pool.
 *
 * Requires that the lock is held on the entropy pool.
286
 */
Michael Graff's avatar
Michael Graff committed
287
static void
Michael Graff's avatar
Michael Graff committed
288
entropypool_adddata(isc_entropy_t *ent, void *p, unsigned int len,
289
290
291
		    isc_uint32_t entropy)
{
	isc_uint32_t val;
292
	unsigned long addr;
293
294
	isc_uint8_t *buf;

295
	addr = (unsigned long)p;
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
	buf = p;

	if ((addr & 0x03) != 0) {
		val = 0;
		switch (len) {
		case 3:
			val = *buf++;
			len--;
		case 2:
			val = val << 8 | *buf++;
			len--;
		case 1:
			val = val << 8 | *buf++;
			len--;
		}

Michael Graff's avatar
Michael Graff committed
312
		entropypool_add_word(&ent->pool, val);
313
314
315
316
317
	}

	for (; len > 3 ; len -= 4) {
		val = *((isc_uint32_t *)buf);

Michael Graff's avatar
Michael Graff committed
318
		entropypool_add_word(&ent->pool, val);
319
320
321
322
323
324
325
326
327
328
329
330
331
332
		buf += 4;
	}

	if (len != 0) {
		val = 0;
		switch (len) {
		case 3:
			val = *buf++;
		case 2:
			val = val << 8 | *buf++;
		case 1:
			val = val << 8 | *buf++;
		}

Michael Graff's avatar
Michael Graff committed
333
		entropypool_add_word(&ent->pool, val);
334
335
	}

Michael Graff's avatar
Michael Graff committed
336
	add_entropy(ent, entropy);
337
	subtract_pseudo(ent, entropy);
338
339
}

340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
static inline void
reseed(isc_entropy_t *ent) {
	isc_result_t result;
	isc_time_t t;
	pid_t pid;

	if (ent->initcount == 0) {
		pid = getpid();
		entropypool_adddata(ent, &pid, sizeof pid, 0);
		pid = getppid();
		entropypool_adddata(ent, &pid, sizeof pid, 0);
	}

	/*
	 * After we've reseeded 100 times, only add new timing info every
	 * 50 requests.  This will keep us from using lots and lots of
	 * CPU just to return bad pseudorandom data anyway.
	 */
	if (ent->initcount > 100)
		if ((ent->initcount % 50) != 0)
			return;

	result = isc_time_now(&t);
	if (result == ISC_R_SUCCESS) {
		entropypool_adddata(ent, &t, sizeof t, 0);
		ent->initcount++;
	}
}

369
static unsigned int
Michael Graff's avatar
Michael Graff committed
370
get_from_filesource(isc_entropysource_t *source, isc_uint32_t desired) {
Michael Graff's avatar
Michael Graff committed
371
	isc_entropy_t *ent = source->ent;
Michael Graff's avatar
Michael Graff committed
372
373
374
	unsigned char buf[128];
	int fd = source->sources.file.fd;
	ssize_t n, ndesired;
375
	unsigned int added;
Michael Graff's avatar
Michael Graff committed
376
377
378
379

	if (fd == -1)
		return (0);

Michael Graff's avatar
Michael Graff committed
380
	desired = desired / 8 + (((desired & 0x07) > 0) ? 1 : 0);
Michael Graff's avatar
Michael Graff committed
381

Michael Graff's avatar
Michael Graff committed
382
	added = 0;
Michael Graff's avatar
Michael Graff committed
383
384
385
386
	while (desired > 0) {
		ndesired = ISC_MIN(desired, sizeof(buf));
		n = read(fd, buf, ndesired);
		if (n < 0) {
Michael Graff's avatar
Michael Graff committed
387
			if (errno == EAGAIN)
Michael Graff's avatar
Michael Graff committed
388
389
390
				goto out;
			close(fd);
			source->sources.file.fd = -1;
391
			goto out;
Michael Graff's avatar
Michael Graff committed
392
		}
393
394
395
		if (n == 0) {
			close(fd);
			source->sources.file.fd = -1;
Michael Graff's avatar
Michael Graff committed
396
			goto out;
397
		}
Michael Graff's avatar
Michael Graff committed
398

Michael Graff's avatar
Michael Graff committed
399
		entropypool_adddata(ent, buf, n, n * 8);
Michael Graff's avatar
Michael Graff committed
400
		added += n * 8;
Michael Graff's avatar
Michael Graff committed
401
		desired -= n;
Michael Graff's avatar
Michael Graff committed
402
403
404
405
406
407
	}

 out:
	return (added);
}

408
static unsigned int
409
410
411
get_from_callback(isc_entropysource_t *source, unsigned int desired,
		  isc_boolean_t blocking)
{
412
413
414
	isc_entropy_t *ent = source->ent;
	isc_cbsource_t *cbs = &source->sources.callback;
	unsigned int added;
415
	unsigned int got;
416
417
	isc_result_t result;

418
419
	if (desired == 0)
		return (0);
420

421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
	if (!cbs->start_called && cbs->startfunc != NULL) {
		result = cbs->startfunc(source, cbs->arg, blocking);
		if (result != ISC_R_SUCCESS)
			return (0);
		cbs->start_called = ISC_TRUE;
	}

	added = 0;
	result = ISC_R_SUCCESS;
	while (desired > 0 && result == ISC_R_SUCCESS) {
		result = cbs->getfunc(source, cbs->arg, blocking);
		if (result == ISC_R_QUEUEFULL) {
			got = crunchsamples(ent, &cbs->samplequeue);
			added += got;
			desired -= ISC_MIN(got, desired);
			result = ISC_R_SUCCESS;
		}
438
439
440
441
442
	}

	return (added);
}

Michael Graff's avatar
Michael Graff committed
443
444
445
446
447
/*
 * Poll each source, trying to get data from it to stuff into the entropy
 * pool.
 */
static void
448
449
450
451
fillpool(isc_entropy_t *ent, unsigned int desired, isc_boolean_t blocking) {
	unsigned int added;
	unsigned int remaining;
	unsigned int needed;
452
	unsigned int nsource;
Michael Graff's avatar
Michael Graff committed
453
454
	isc_entropysource_t *source;

Michael Graff's avatar
Michael Graff committed
455
	REQUIRE(VALID_ENTROPY(ent));
Michael Graff's avatar
Michael Graff committed
456

457
458
	needed = desired;

Michael Graff's avatar
Michael Graff committed
459
	/*
Michael Graff's avatar
Michael Graff committed
460
461
462
463
464
465
466
467
468
469
470
471
472
473
	 * This logic is a little strange, so an explanation is in order.
	 *
	 * If needed is 0, it means we are being asked to "fill to whatever
	 * we think is best."  This means that if we have at least a
	 * partially full pool (say, > 1/4th of the pool) we probably don't
	 * need to add anything.
	 *
	 * Also, we will check to see if the "pseudo" count is too high.
	 * If it is, try to mix in better data.  Too high is currently
	 * defined as 1/4th of the pool.
	 *
	 * Next, if we are asked to add a specific bit of entropy, make
	 * certain that we will do so.  Clamp how much we try to add to
	 * (DIGEST_SIZE * 8 < needed < POOLBITS - entropy).
474
475
476
477
	 *
	 * Note that if we are in a blocking mode, we will only try to
	 * get as much data as we need, not as much as we might want
	 * to build up.
Michael Graff's avatar
Michael Graff committed
478
	 */
Michael Graff's avatar
Michael Graff committed
479
480
481
	if (needed == 0) {
		REQUIRE(!blocking);

Michael Graff's avatar
Michael Graff committed
482
483
484
		if ((ent->pool.entropy >= RND_POOLBITS / 4)
		    && (ent->pool.pseudo <= RND_POOLBITS / 4))
			return;
485
486

		needed = THRESHOLD_BITS * 4;
Michael Graff's avatar
Michael Graff committed
487
	} else {
488
		needed = ISC_MAX(needed, THRESHOLD_BITS);
Michael Graff's avatar
Michael Graff committed
489
		needed = ISC_MIN(needed, RND_POOLBITS);
Michael Graff's avatar
Michael Graff committed
490
	}
Michael Graff's avatar
Michael Graff committed
491

492
493
494
495
496
	/*
	 * In any case, clamp how much we need to how much we can add.
	 */
	needed = ISC_MIN(needed, RND_POOLBITS - ent->pool.entropy);

497
	/*
498
499
	 * But wait!  If we're not yet initialized, we need at least
	 *	THRESHOLD_BITS
500
	 * of randomness.
501
	 */
502
503
	if (ent->initialized < THRESHOLD_BITS)
		needed = ISC_MAX(needed, THRESHOLD_BITS - ent->initialized);
504

Michael Graff's avatar
Michael Graff committed
505
506
507
508
509
510
511
512
	/*
	 * Poll each file source to see if we can read anything useful from
	 * it.  XXXMLG When where are multiple sources, we should keep a
	 * record of which one we last used so we can start from it (or the
	 * next one) to avoid letting some sources build up entropy while
	 * others are always drained.
	 */

513
	added = 0;
Michael Graff's avatar
Michael Graff committed
514
	remaining = needed;
515
516
517
518
519
520
	if (ent->nextsource == NULL) {
		ent->nextsource = ISC_LIST_HEAD(ent->sources);
		if (ent->nextsource == NULL)
			return;
	}
	source = ent->nextsource;
521
 again_file:
522
	for (nsource = 0 ; nsource < ent->nsources ; nsource++) {
523
		unsigned int got;
Michael Graff's avatar
Michael Graff committed
524

525
526
527
		if (remaining == 0)
			break;

Michael Graff's avatar
Michael Graff committed
528
529
530
531
		got = 0;

		if (source->type == ENTROPY_SOURCETYPE_FILE)
			got = get_from_filesource(source, remaining);
Michael Graff's avatar
Michael Graff committed
532

Michael Graff's avatar
Michael Graff committed
533
534
		added += got;

535
		remaining -= ISC_MIN(remaining, got);
Michael Graff's avatar
Michael Graff committed
536

537
538
539
540
		source = ISC_LIST_NEXT(source, link);
		if (source == NULL)
			source = ISC_LIST_HEAD(ent->sources);

541
#if 0
Michael Graff's avatar
Michael Graff committed
542
543
		if (added >= needed)
			break;
544
#endif
Michael Graff's avatar
Michael Graff committed
545
	}
546
	ent->nextsource = source;
Michael Graff's avatar
Michael Graff committed
547

Michael Graff's avatar
Michael Graff committed
548
	if (blocking && remaining != 0) {
549
550
551
		int fds;
		fds = wait_for_sources(ent);
		if (fds > 0)
552
553
554
555
556
557
558
559
			goto again_file;
	}

	/*
	 * Here, if there are bits remaining to be had and we can block,
	 * check to see if we have a callback source.  If so, call them.
	 */
	source = ISC_LIST_HEAD(ent->sources);
560
	while ((remaining != 0) && (source != NULL)) {
561
562
563
564
565
		unsigned int got;

		got = 0;

		if (source->type == ENTROPY_SOURCETYPE_CALLBACK)
566
			got = get_from_callback(source, remaining, blocking);
567
568

		added += got;
569
		remaining -= ISC_MIN(remaining, got);
570
571
572
573
574

		if (added >= needed)
			break;

		source = ISC_LIST_NEXT(source, link);
575
576
	}

577
578
579
	/*
	 * Mark as initialized if we've added enough data.
	 */
580
	if (ent->initialized < THRESHOLD_BITS)
581
		ent->initialized += added;
Michael Graff's avatar
Michael Graff committed
582
583
}

584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
static int
wait_for_sources(isc_entropy_t *ent) {
	isc_entropysource_t *source;
	int maxfd, fd;
	int cc;
	fd_set reads;

	maxfd = -1;
	FD_ZERO(&reads);

	source = ISC_LIST_HEAD(ent->sources);
	while (source != NULL) {
		if (source->type == ENTROPY_SOURCETYPE_FILE) {
			fd = source->sources.file.fd;
			if (fd >= 0) {
				maxfd = ISC_MAX(maxfd, fd);
				FD_SET(fd, &reads);
			}
		}
		source = ISC_LIST_NEXT(source, link);
	}

	if (maxfd < 0)
		return (-1);

	cc = select(maxfd + 1, &reads, NULL, NULL, NULL);
	if (cc < 0)
		return (-1);

	return (cc);
}

616
617
618
619
620
621
622
623
624
/*
 * Extract some number of bytes from the random pool, decreasing the
 * estimate of randomness as each byte is extracted.
 *
 * Do this by stiring the pool and returning a part of hash as randomness.
 * Note that no secrets are given away here since parts of the hash are
 * xored together before returned.
 *
 * Honor the request from the caller to only return good data, any data,
Michael Graff's avatar
Michael Graff committed
625
 * etc.
626
 */
Michael Graff's avatar
Michael Graff committed
627
628
629
isc_result_t
isc_entropy_getdata(isc_entropy_t *ent, void *data, unsigned int length,
		    unsigned int *returned, unsigned int flags)
630
631
632
633
{
	unsigned int i;
	isc_sha1_t hash;
	unsigned char digest[ISC_SHA1_DIGESTLENGTH];
Michael Graff's avatar
Michael Graff committed
634
	isc_uint32_t remain, deltae, count, total;
635
	isc_uint8_t *buf;
Michael Graff's avatar
Michael Graff committed
636
	isc_boolean_t goodonly, partial, blocking;
637

Michael Graff's avatar
Michael Graff committed
638
639
640
641
642
643
644
645
	REQUIRE(VALID_ENTROPY(ent));
	REQUIRE(data != NULL);
	REQUIRE(length > 0);

	goodonly = ISC_TF((flags & ISC_ENTROPY_GOODONLY) != 0);
	partial = ISC_TF((flags & ISC_ENTROPY_PARTIAL) != 0);
	blocking = ISC_TF((flags & ISC_ENTROPY_BLOCKING) != 0);

646
647
	REQUIRE(!partial || returned != NULL);

Michael Graff's avatar
Michael Graff committed
648
	LOCK(&ent->lock);
649

Michael Graff's avatar
Michael Graff committed
650
651
652
653
654
655
	remain = length;
	buf = data;
	total = 0;
	while (remain != 0) {
		count = ISC_MIN(remain, RND_ENTROPY_THRESHOLD);

Michael Graff's avatar
Michael Graff committed
656
657
658
659
660
661
		/*
		 * If we are extracting good data only, make certain we
		 * have enough data in our pool for this pass.  If we don't,
		 * get some, and fail if we can't, and partial returns
		 * are not ok.
		 */
Michael Graff's avatar
Michael Graff committed
662
		if (goodonly) {
663
664
665
666
			unsigned int fillcount;

			fillcount = ISC_MAX(remain * 8, count * 8);

667
668
669
670
671
672
673
674
675
676
677
			/*
			 * If, however, we have at least THRESHOLD_BITS
			 * of entropy in the pool, don't block here.  It is
			 * better to drain the pool once in a while and
			 * then refill it than it is to constantly keep the
			 * pool full.
			 */
			if (ent->pool.entropy >= THRESHOLD_BITS)
				fillpool(ent, fillcount, ISC_FALSE);
			else
				fillpool(ent, fillcount, blocking);
678

679
680
681
682
			/*
			 * Verify that we got enough entropy to do one
			 * extraction.  If we didn't, bail.
			 */
683
			if (ent->pool.entropy < THRESHOLD_BITS) {
684
				if (!partial)
685
					goto zeroize;
686
				else
687
688
					goto partial_output;
			}
Michael Graff's avatar
Michael Graff committed
689
690
691
692
693
		} else {
			/*
			 * If we've extracted half our pool size in bits
			 * since the last refresh, try to refresh here.
			 */
694
695
			if (ent->initialized < THRESHOLD_BITS)
				fillpool(ent, THRESHOLD_BITS, blocking);
696
697
			else
				fillpool(ent, 0, ISC_FALSE);
698
699
700

			/*
			 * If we've not initialized with enough good random
701
			 * data, seed with our crappy code.
702
			 */
703
			if (ent->initialized < THRESHOLD_BITS)
704
				reseed(ent);
Michael Graff's avatar
Michael Graff committed
705
706
		}

707
		isc_sha1_init(&hash);
Michael Graff's avatar
Michael Graff committed
708
		isc_sha1_update(&hash, (void *)(ent->pool.pool),
709
710
				RND_POOLWORDS * 4);
		isc_sha1_final(&hash, digest);
711

712
		/*
Michael Graff's avatar
Michael Graff committed
713
		 * Stir the extracted data (all of it) back into the pool.
714
		 */
Michael Graff's avatar
Michael Graff committed
715
		entropypool_adddata(ent, digest, ISC_SHA1_DIGESTLENGTH, 0);
716
717

		for (i = 0; i < count; i++)
Michael Graff's avatar
Michael Graff committed
718
			buf[i] = digest[i] ^ digest[i + RND_ENTROPY_THRESHOLD];
719
720
721
722

		buf += count;
		remain -= count;

Michael Graff's avatar
Michael Graff committed
723
		deltae = count * 8;
Michael Graff's avatar
Michael Graff committed
724
		deltae = ISC_MIN(deltae, ent->pool.entropy);
Michael Graff's avatar
Michael Graff committed
725
		total += deltae;
Michael Graff's avatar
Michael Graff committed
726
		subtract_entropy(ent, deltae);
727
		add_pseudo(ent, count * 8);
Michael Graff's avatar
Michael Graff committed
728
729
	}

730
 partial_output:
Michael Graff's avatar
Michael Graff committed
731
	memset(digest, 0, sizeof(digest));
732

Michael Graff's avatar
Michael Graff committed
733
	if (returned != NULL)
Michael Graff's avatar
Michael Graff committed
734
		*returned = (length - remain);
735

Michael Graff's avatar
Michael Graff committed
736
737
	UNLOCK(&ent->lock);

Michael Graff's avatar
Michael Graff committed
738
739
740
741
	return (ISC_R_SUCCESS);

 zeroize:
	/* put the entropy we almost extracted back */
Michael Graff's avatar
Michael Graff committed
742
	add_entropy(ent, total);
Michael Graff's avatar
Michael Graff committed
743
	memset(data, 0, length);
744
	memset(digest, 0, sizeof(digest));
Michael Graff's avatar
Michael Graff committed
745
	if (returned != NULL)
Michael Graff's avatar
Michael Graff committed
746
		*returned = 0;
747

Michael Graff's avatar
Michael Graff committed
748
749
	UNLOCK(&ent->lock);

Michael Graff's avatar
Michael Graff committed
750
	return (ISC_R_NOENTROPY);
751
752
753
754
755
756
}

static void
isc_entropypool_init(isc_entropypool_t *pool) {
	pool->cursor = RND_POOLWORDS - 1;
	pool->entropy = 0;
Michael Graff's avatar
Michael Graff committed
757
	pool->pseudo = 0;
758
759
760
761
762
763
764
765
	pool->rotate = 0;
	memset(pool->pool, 0, RND_POOLWORDS);
}

static void
isc_entropypool_invalidate(isc_entropypool_t *pool) {
	pool->cursor = 0;
	pool->entropy = 0;
Michael Graff's avatar
Michael Graff committed
766
	pool->pseudo = 0;
767
768
769
770
	pool->rotate = 0;
	memset(pool->pool, 0, RND_POOLWORDS);
}

Michael Graff's avatar
Michael Graff committed
771
772
isc_result_t
isc_entropy_create(isc_mem_t *mctx, isc_entropy_t **entp) {
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
	isc_result_t ret;
	isc_entropy_t *ent;

	REQUIRE(mctx != NULL);
	REQUIRE(entp != NULL && *entp == NULL);

	ent = isc_mem_get(mctx, sizeof(isc_entropy_t));
	if (ent == NULL)
		return (ISC_R_NOMEMORY);

	/*
	 * We need a lock.
	 */
	if (isc_mutex_init(&ent->lock) != ISC_R_SUCCESS) {
		ret = ISC_R_UNEXPECTED;
		goto errout;
	}

	/*
	 * From here down, no failures will/can occur.
	 */
	ISC_LIST_INIT(ent->sources);
795
796
	ent->nextsource = NULL;
	ent->nsources = 0;
797
798
799
	ent->mctx = NULL;
	isc_mem_attach(mctx, &ent->mctx);
	ent->refcnt = 1;
800
	ent->initialized = 0;
801
	ent->initcount = 0;
Michael Graff's avatar
Michael Graff committed
802
	ent->magic = ENTROPY_MAGIC;
803
804
805
806
807
808
809
810
811
812

	isc_entropypool_init(&ent->pool);

	*entp = ent;
	return (ISC_R_SUCCESS);

 errout:
	isc_mem_put(mctx, ent, sizeof(isc_entropy_t));

	return (ret);
Michael Graff's avatar
Michael Graff committed
813
}
Michael Graff's avatar
Michael Graff committed
814

815
816
817
818
819
820
821
/*
 * Requires "ent" be locked.
 */
static void
destroysource(isc_entropysource_t **sourcep) {
	isc_entropysource_t *source;
	isc_entropy_t *ent;
Michael Graff's avatar
Michael Graff committed
822
	isc_cbsource_t *cbs;
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
	int fd;

	source = *sourcep;
	*sourcep = NULL;
	ent = source->ent;

	ISC_LIST_UNLINK(ent->sources, source, link);
	ent->nextsource = NULL;
	REQUIRE(ent->nsources > 0);
	ent->nsources--;

	switch (source->type) {
	case ENTROPY_SOURCETYPE_FILE:
		fd = source->sources.file.fd;
		if (fd >= 0)
			close(fd);
		break;
	case ENTROPY_SOURCETYPE_SAMPLE:
Michael Graff's avatar
Michael Graff committed
841
842
843
844
		samplequeue_release(ent, &source->sources.sample.samplequeue);
		break;
	case ENTROPY_SOURCETYPE_CALLBACK:
		cbs = &source->sources.callback;
845
846
847
848
		if (cbs->start_called && cbs->stopfunc != NULL) {
			cbs->stopfunc(source, cbs->arg);
			cbs->start_called = ISC_FALSE;
		}
Michael Graff's avatar
Michael Graff committed
849
		samplequeue_release(ent, &cbs->samplequeue);
850
851
852
853
854
855
856
857
		break;
	}

	memset(source, 0, sizeof(isc_entropysource_t));

	isc_mem_put(ent->mctx, source, sizeof(isc_entropysource_t));
}

858
859
static inline isc_boolean_t
destroy_check(isc_entropy_t *ent) {
860
861
	isc_entropysource_t *source;

862
863
	if (ent->refcnt > 0)
		return (ISC_FALSE);
864
865
866
867
868
869
870
871
872
873
874

	source = ISC_LIST_HEAD(ent->sources);
	while (source != NULL) {
		switch (source->type) {
		case ENTROPY_SOURCETYPE_FILE:
			break;
		default:
			return (ISC_FALSE);
		}
		source = ISC_LIST_NEXT(source, link);
	}
875
876
877
878
879
880

	return (ISC_TRUE);
}

static void
destroy(isc_entropy_t **entp) {
881
	isc_entropy_t *ent;
882
	isc_entropysource_t *source;
Michael Graff's avatar
Michael Graff committed
883
	isc_mem_t *mctx;
884
885
886
887
888

	REQUIRE(entp != NULL && *entp != NULL);
	ent = *entp;
	*entp = NULL;

889
890
	LOCK(&ent->lock);

891
	REQUIRE(ent->refcnt == 0);
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908

	/*
	 * Here, detach non-sample sources.
	 */
	source = ISC_LIST_HEAD(ent->sources);
	while (source != NULL) {
		switch(source->type) {
		case ENTROPY_SOURCETYPE_FILE:
			destroysource(&source);
			break;
		}
		source = ISC_LIST_HEAD(ent->sources);
	}

	/*
	 * If there are other types of sources, we've found a bug.
	 */
909
	REQUIRE(ISC_LIST_EMPTY(ent->sources));
910

Michael Graff's avatar
Michael Graff committed
911
	mctx = ent->mctx;
912
913

	isc_entropypool_invalidate(&ent->pool);
914
915
916

	UNLOCK(&ent->lock);

917
	(void)isc_mutex_destroy(&ent->lock);
918
919

	memset(ent, 0, sizeof(isc_entropy_t));
Michael Graff's avatar
Michael Graff committed
920
	isc_mem_put(mctx, ent, sizeof(isc_entropy_t));
921
	isc_mem_detach(&mctx);
Michael Graff's avatar
Michael Graff committed
922
923
}

Michael Graff's avatar
Michael Graff committed
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
/*
 * Make a fd non-blocking
 */
static isc_result_t
make_nonblock(int fd) {
	int ret;
	int flags;

	flags = fcntl(fd, F_GETFL, 0);
	flags |= O_NONBLOCK;
	ret = fcntl(fd, F_SETFL, flags);

	if (ret == -1) {
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "fcntl(%d, F_SETFL, %d): %s",
				 fd, flags, strerror(errno));

		return (ISC_R_UNEXPECTED);
	}

	return (ISC_R_SUCCESS);
}

Michael Graff's avatar
Michael Graff committed
947
isc_result_t
948
isc_entropy_createfilesource(isc_entropy_t *ent, const char *fname) {
Michael Graff's avatar
Michael Graff committed
949
950
951
	int fd;
	isc_result_t ret;
	isc_entropysource_t *source;
952

Michael Graff's avatar
Michael Graff committed
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
	REQUIRE(VALID_ENTROPY(ent));
	REQUIRE(fname != NULL);

	LOCK(&ent->lock);

	source = NULL;
	fd = -1;

	fd = open(fname, O_RDONLY | O_NONBLOCK, 0);
	if (fd < 0) {
		ret = ISC_R_IOERROR;
		goto errout;
	}

	ret = make_nonblock(fd);
	if (ret != ISC_R_SUCCESS)
		goto errout;

	source = isc_mem_get(ent->mctx, sizeof(isc_entropysource_t));
	if (source == NULL) {
		ret = ISC_R_NOMEMORY;
		goto errout;
	}

	/*
	 * From here down, no failures can occur.
	 */
Michael Graff's avatar
Michael Graff committed
980
	source->magic = SOURCE_MAGIC;
Michael Graff's avatar
Michael Graff committed
981
982
983
984
985
986
987
988
989
990
991
	source->type = ENTROPY_SOURCETYPE_FILE;
	source->ent = ent;
	source->total = 0;
	memset(source->name, 0, sizeof(source->name));
	ISC_LINK_INIT(source, link);
	source->sources.file.fd = fd;

	/*
	 * Hook it into the entropy system.
	 */
	ISC_LIST_APPEND(ent->sources, source, link);
992
	ent->nsources++;
Michael Graff's avatar
Michael Graff committed
993
994
995
996
997
998
999
1000

	UNLOCK(&ent->lock);
	return (ISC_R_SUCCESS);

 errout:
	if (source != NULL)
		isc_mem_put(ent->mctx, source, sizeof(isc_entropysource_t));
	if (fd >= 0)
For faster browsing, not all history is shown. View entire blame