xref: /openbsd/sys/dev/rnd.c (revision 404b540a)
1 /*	$OpenBSD: rnd.c,v 1.100 2009/06/05 04:43:23 guenther Exp $	*/
2 
3 /*
4  * rnd.c -- A strong random number generator
5  *
6  * Copyright (c) 1996, 1997, 2000-2002 Michael Shalayeff.
7  * Copyright (c) 2008 Damien Miller.
8  *
9  * Version 1.89, last modified 19-Sep-99
10  *
11  * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.
12  * All rights reserved.
13  *
14  * Redistribution and use in source and binary forms, with or without
15  * modification, are permitted provided that the following conditions
16  * are met:
17  * 1. Redistributions of source code must retain the above copyright
18  *    notice, and the entire permission notice in its entirety,
19  *    including the disclaimer of warranties.
20  * 2. Redistributions in binary form must reproduce the above copyright
21  *    notice, this list of conditions and the following disclaimer in the
22  *    documentation and/or other materials provided with the distribution.
23  * 3. The name of the author may not be used to endorse or promote
24  *    products derived from this software without specific prior
25  *    written permission.
26  *
27  * ALTERNATIVELY, this product may be distributed under the terms of
28  * the GNU Public License, in which case the provisions of the GPL are
29  * required INSTEAD OF the above restrictions.  (This clause is
30  * necessary due to a potential bad interaction between the GPL and
31  * the restrictions contained in a BSD-style copyright.)
32  *
33  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
34  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
35  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
36  * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
37  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
38  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
39  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
40  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
41  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
42  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
43  * OF THE POSSIBILITY OF SUCH DAMAGE.
44  */
45 
46 /*
47  * (now, with legal B.S. out of the way.....)
48  *
49  * This routine gathers environmental noise from device drivers, etc.,
50  * and returns good random numbers, suitable for cryptographic use.
51  * Besides the obvious cryptographic uses, these numbers are also good
52  * for seeding TCP sequence numbers, and other places where it is
53  * desirable to have numbers which are not only random, but hard to
54  * predict by an attacker.
55  *
56  * Theory of operation
57  * ===================
58  *
59  * Computers are very predictable devices.  Hence it is extremely hard
60  * to produce truly random numbers on a computer --- as opposed to
61  * pseudo-random numbers, which can be easily generated by using an
62  * algorithm.  Unfortunately, it is very easy for attackers to guess
63  * the sequence of pseudo-random number generators, and for some
64  * applications this is not acceptable.  Instead, we must try to
65  * gather "environmental noise" from the computer's environment, which
66  * must be hard for outside attackers to observe and use to
67  * generate random numbers.  In a Unix environment, this is best done
68  * from inside the kernel.
69  *
70  * Sources of randomness from the environment include inter-keyboard
71  * timings, inter-interrupt timings from some interrupts, and other
72  * events which are both (a) non-deterministic and (b) hard for an
73  * outside observer to measure.  Randomness from these sources is
74  * added to the "entropy pool", which is mixed using a CRC-like function.
75  * This is not cryptographically strong, but it is adequate assuming
76  * the randomness is not chosen maliciously, and it is fast enough that
77  * the overhead of doing it on every interrupt is very reasonable.
78  * As random bytes are mixed into the entropy pool, the routines keep
79  * an *estimate* of how many bits of randomness have been stored into
80  * the random number generator's internal state.
81  *
82  * When random bytes are desired, they are obtained by taking the MD5
83  * hash of the content of the entropy pool.  The MD5 hash avoids
84  * exposing the internal state of the entropy pool.  It is believed to
85  * be computationally infeasible to derive any useful information
86  * about the input of MD5 from its output.  Even if it is possible to
87  * analyze MD5 in some clever way, as long as the amount of data
88  * returned from the generator is less than the inherent entropy in
89  * the pool, the output data is totally unpredictable.  For this
90  * reason, the routine decreases its internal estimate of how many
91  * bits of "true randomness" are contained in the entropy pool as it
92  * outputs random numbers.
93  *
94  * If this estimate goes to zero, the routine can still generate
95  * random numbers; however, an attacker may (at least in theory) be
96  * able to infer the future output of the generator from prior
97  * outputs.  This requires successful cryptanalysis of MD5, which is
98  * believed to be not feasible, but there is a remote possibility.
99  * Nonetheless, these numbers should be useful for the vast majority
100  * of purposes.
101  *
102  * Exported interfaces ---- output
103  * ===============================
104  *
105  * There are three exported interfaces.
106  * The first set are designed to be used from within the kernel:
107  *
108  *	void get_random_bytes(void *buf, int nbytes);
109  *
110  * This interface will return the requested number of random bytes,
111  * and place it in the requested buffer.
112  *
113  * Two other interfaces are two character devices /dev/random and
114  * /dev/urandom.  /dev/random is suitable for use when very high
115  * quality randomness is desired (for example, for key generation or
116  * one-time pads), as it will only return a maximum of the number of
117  * bits of randomness (as estimated by the random number generator)
118  * contained in the entropy pool.
119  *
120  * The /dev/urandom device does not have this limit, and will return
121  * as many bytes as were requested.  As more and more random bytes
122  * requested without giving time for the entropy pool to recharge,
123  * this will result in random numbers that are merely cryptographically
124  * strong.  For many applications, however, this is acceptable.
125  *
126  * Exported interfaces ---- input
127  * ==============================
128  *
129  * The current exported interfaces for gathering environmental noise
130  * from the devices are:
131  *
132  *	void add_true_randomness(int data);
133  *	void add_timer_randomness(int data);
134  *	void add_mouse_randomness(int mouse_data);
135  *	void add_net_randomness(int isr);
136  *	void add_tty_randomness(int c);
137  *	void add_disk_randomness(int n);
138  *	void add_audio_randomness(int n);
139  *	void add_video_randomness(int n);
140  *
141  * add_true_randomness() uses true random number generators present
142  * on some cryptographic and system chipsets.  Entropy accounting
143  * is not quitable, no timing is done, supplied 32 bits of pure entropy
144  * are hashed into the pool plain and blindly, increasing the counter.
145  *
146  * add_timer_randomness() uses the random driver itselves timing,
147  * measuring extract_entropy() and rndioctl() execution times.
148  *
149  * add_mouse_randomness() uses the mouse interrupt timing, as well as
150  * the reported position of the mouse from the hardware.
151  *
152  * add_net_randomness() times the finishing time of net input.
153  *
154  * add_tty_randomness() uses the inter-keypress timing, as well as the
155  * character as random inputs into the entropy pool.
156  *
157  * add_disk_randomness() times the finishing time of disk requests as well
158  * as feeding both xfer size & time into the entropy pool.
159  *
160  * add_audio_randomness() times the finishing of audio codec dma
161  * requests for both recording and playback, apparently supplies quite
162  * a lot of entropy. I'd blame it on low resolution audio clock generators.
163  *
164  * All of these routines (except for add_true_randomness() of course)
165  * try to estimate how many bits of randomness are in a particular
166  * randomness source.  They do this by keeping track of the first and
167  * second order deltas of the event timings.
168  *
169  * Ensuring unpredictability at system startup
170  * ============================================
171  *
172  * When any operating system starts up, it will go through a sequence
173  * of actions that are fairly predictable by an adversary, especially
174  * if the start-up does not involve interaction with a human operator.
175  * This reduces the actual number of bits of unpredictability in the
176  * entropy pool below the value in entropy_count.  In order to
177  * counteract this effect, it helps to carry information in the
178  * entropy pool across shut-downs and start-ups.  To do this, put the
179  * following lines in appropriate script which is run during the boot
180  * sequence:
181  *
182  *	echo "Initializing random number generator..."
183  *	# Carry a random seed from start-up to start-up
184  *	# Load and then save 512 bytes, which is the size of the entropy pool
185  *	if [ -f /etc/random-seed ]; then
186  *		cat /etc/random-seed >/dev/urandom
187  *	fi
188  *	dd if=/dev/urandom of=/etc/random-seed count=1
189  *
190  * and the following lines in appropriate script which is run when
191  * the system is shutting down:
192  *
193  *	# Carry a random seed from shut-down to start-up
194  *	# Save 512 bytes, which is the size of the entropy pool
195  *	echo "Saving random seed..."
196  *	dd if=/dev/urandom of=/etc/random-seed count=1
197  *
198  * For example, on OpenBSD systems, the appropriate scripts are
199  * usually /etc/rc.local and /etc/rc.shutdown, respectively.
200  *
201  * Effectively, these commands cause the contents of the entropy pool
202  * to be saved at shutdown time and reloaded into the entropy pool at
203  * start-up.  (The 'dd' in the addition to the bootup script is to
204  * make sure that /etc/random-seed is different for every start-up,
205  * even if the system crashes without executing rc.shutdown) Even with
206  * complete knowledge of the start-up activities, predicting the state
207  * of the entropy pool requires knowledge of the previous history of
208  * the system.
209  *
210  * Configuring the random(4) driver under OpenBSD
211  * ==============================================
212  *
213  * The special files for the random(4) driver should have been created
214  * during the installation process.  However, if your system does not have
215  * /dev/random and /dev/[s|u|p|a]random created already, they can be created
216  * by using the MAKEDEV(8) script in /dev:
217  *
218  *	/dev/MAKEDEV random
219  *
220  * Check MAKEDEV for information about major and minor numbers.
221  *
222  * Acknowledgements:
223  * =================
224  *
225  * Ideas for constructing this random number generator were derived
226  * from Pretty Good Privacy's random number generator, and from private
227  * discussions with Phil Karn.  Colin Plumb provided a faster random
228  * number generator, which speeds up the mixing function of the entropy
229  * pool, taken from PGPfone.  Dale Worley has also contributed many
230  * useful ideas and suggestions to improve this driver.
231  *
232  * Any flaws in the design are solely my responsibility, and should
233  * not be attributed to the Phil, Colin, or any of the authors of PGP.
234  *
235  * Further background information on this topic may be obtained from
236  * RFC 1750, "Randomness Recommendations for Security", by Donald
237  * Eastlake, Steve Crocker, and Jeff Schiller.
238  */
239 
240 #include <sys/param.h>
241 #include <sys/endian.h>
242 #include <sys/systm.h>
243 #include <sys/conf.h>
244 #include <sys/disk.h>
245 #include <sys/limits.h>
246 #include <sys/ioctl.h>
247 #include <sys/malloc.h>
248 #include <sys/fcntl.h>
249 #include <sys/vnode.h>
250 #include <sys/sysctl.h>
251 #include <sys/timeout.h>
252 #include <sys/poll.h>
253 #include <sys/mutex.h>
254 #include <sys/msgbuf.h>
255 
256 #include <crypto/md5.h>
257 #include <crypto/arc4.h>
258 
259 #include <dev/rndvar.h>
260 #include <dev/rndioctl.h>
261 
262 #ifdef	RNDEBUG
263 int	rnd_debug = 0x0000;
264 #define	RD_INPUT	0x000f	/* input data */
265 #define	RD_OUTPUT	0x00f0	/* output data */
266 #define	RD_WAIT		0x0100	/* sleep/wakeup for good data */
267 #endif
268 
269 /*
270  * Master random number pool functions
271  * -----------------------------------
272  */
273 
274 /*
275  * For the purposes of better mixing, we use the CRC-32 polynomial as
276  * well to make a twisted Generalized Feedback Shift Register
277  *
278  * (See M. Matsumoto & Y. Kurita, 1992.  Twisted GFSR generators.  ACM
279  * Transactions on Modeling and Computer Simulation 2(3):179-194.
280  * Also see M. Matsumoto & Y. Kurita, 1994.  Twisted GFSR generators
281  * II.  ACM Transactions on Mdeling and Computer Simulation 4:254-266)
282  *
283  * Thanks to Colin Plumb for suggesting this.
284  *
285  * We have not analyzed the resultant polynomial to prove it primitive;
286  * in fact it almost certainly isn't.  Nonetheless, the irreducible factors
287  * of a random large-degree polynomial over GF(2) are more than large enough
288  * that periodicity is not a concern.
289  *
290  * The input hash is much less sensitive than the output hash.  All
291  * we want from it is to be a good non-cryptographic hash -
292  * i.e. to not produce collisions when fed "random" data of the sort
293  * we expect to see.  As long as the pool state differs for different
294  * inputs, we have preserved the input entropy and done a good job.
295  * The fact that an intelligent attacker can construct inputs that
296  * will produce controlled alterations to the pool's state is not
297  * important because we don't consider such inputs to contribute any
298  * randomness.  The only property we need with respect to them is that
299  * the attacker can't increase his/her knowledge of the pool's state.
300  * Since all additions are reversible (knowing the final state and the
301  * input, you can reconstruct the initial state), if an attacker has
302  * any uncertainty about the initial state, he/she can only shuffle
303  * that uncertainty about, but never cause any collisions (which would
304  * decrease the uncertainty).
305  *
306  * The chosen system lets the state of the pool be (essentially) the input
307  * modulo the generator polynomial.  Now, for random primitive polynomials,
308  * this is a universal class of hash functions, meaning that the chance
309  * of a collision is limited by the attacker's knowledge of the generator
310  * polynomial, so if it is chosen at random, an attacker can never force
311  * a collision.  Here, we use a fixed polynomial, but we *can* assume that
312  * ###--> it is unknown to the processes generating the input entropy. <-###
313  * Because of this important property, this is a good, collision-resistant
314  * hash; hash collisions will occur no more often than chance.
315  */
316 
317 /*
318  * Stirring polynomials over GF(2) for various pool sizes. Used in
319  * add_entropy_words() below.
320  *
321  * The polynomial terms are chosen to be evenly spaced (minimum RMS
322  * distance from evenly spaced; except for the last tap, which is 1 to
323  * get the twisting happening as fast as possible.
324  *
325  * The reultant polynomial is:
326  *   2^POOLWORDS + 2^POOL_TAP1 + 2^POOL_TAP2 + 2^POOL_TAP3 + 2^POOL_TAP4 + 1
327  */
328 #define POOLBITS	(POOLWORDS*32)
329 #define POOLBYTES	(POOLWORDS*4)
330 #define POOLMASK	(POOLWORDS - 1)
331 #if POOLWORDS == 2048
332 #define	POOL_TAP1	1638
333 #define	POOL_TAP2	1231
334 #define	POOL_TAP3	819
335 #define	POOL_TAP4	411
336 #elif POOLWORDS == 1024	/* also (819, 616, 410, 207, 2) */
337 #define	POOL_TAP1	817
338 #define	POOL_TAP2	615
339 #define	POOL_TAP3	412
340 #define	POOL_TAP4	204
341 #elif POOLWORDS == 512	/* also (409,307,206,102,2), (409,309,205,103,2) */
342 #define	POOL_TAP1	411
343 #define	POOL_TAP2	308
344 #define	POOL_TAP3	208
345 #define	POOL_TAP4	104
346 #elif POOLWORDS == 256
347 #define	POOL_TAP1	205
348 #define	POOL_TAP2	155
349 #define	POOL_TAP3	101
350 #define	POOL_TAP4	52
351 #elif POOLWORDS == 128	/* also (103, 78, 51, 27, 2) */
352 #define	POOL_TAP1	103
353 #define	POOL_TAP2	76
354 #define	POOL_TAP3	51
355 #define	POOL_TAP4	25
356 #elif POOLWORDS == 64
357 #define	POOL_TAP1	52
358 #define	POOL_TAP2	39
359 #define	POOL_TAP3	26
360 #define	POOL_TAP4	14
361 #elif POOLWORDS == 32
362 #define	POOL_TAP1	26
363 #define	POOL_TAP2	20
364 #define	POOL_TAP3	14
365 #define	POOL_TAP4	7
366 #else
367 #error No primitive polynomial available for chosen POOLWORDS
368 #endif
369 
370 static void dequeue_randomness(void *);
371 
372 /* Master kernel random number pool. */
373 struct random_bucket {
374 	u_int	add_ptr;
375 	u_int	entropy_count;
376 	u_char	input_rotate;
377 	u_int32_t pool[POOLWORDS];
378 	u_int	asleep;
379 	u_int	tmo;
380 };
381 struct random_bucket random_state;
382 struct mutex rndlock;
383 
384 /*
385  * This function adds a byte into the entropy pool.  It does not
386  * update the entropy estimate.  The caller must do this if appropriate.
387  *
388  * The pool is stirred with a polynomial of degree POOLWORDS over GF(2);
389  * see POOL_TAP[1-4] above
390  *
391  * Rotate the input word by a changing number of bits, to help assure
392  * that all bits in the entropy get toggled.  Otherwise, if the pool
393  * is consistently feed small numbers (such as keyboard scan codes)
394  * then the upper bits of the entropy pool will frequently remain
395  * untouched.
396  */
397 static void
398 add_entropy_words(const u_int32_t *buf, u_int n)
399 {
400 	/* derived from IEEE 802.3 CRC-32 */
401 	static const u_int32_t twist_table[8] = {
402 		0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
403 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278
404 	};
405 
406 	for (; n--; buf++) {
407 		u_int32_t w = (*buf << random_state.input_rotate) |
408 		    (*buf >> (32 - random_state.input_rotate));
409 		u_int i = random_state.add_ptr =
410 		    (random_state.add_ptr - 1) & POOLMASK;
411 		/*
412 		 * Normally, we add 7 bits of rotation to the pool.
413 		 * At the beginning of the pool, add an extra 7 bits
414 		 * rotation, so that successive passes spread the
415 		 * input bits across the pool evenly.
416 		 */
417 		random_state.input_rotate =
418 		    (random_state.input_rotate + (i ? 7 : 14)) & 31;
419 
420 		/* XOR pool contents corresponding to polynomial terms */
421 		w ^= random_state.pool[(i + POOL_TAP1) & POOLMASK] ^
422 		     random_state.pool[(i + POOL_TAP2) & POOLMASK] ^
423 		     random_state.pool[(i + POOL_TAP3) & POOLMASK] ^
424 		     random_state.pool[(i + POOL_TAP4) & POOLMASK] ^
425 		     random_state.pool[(i + 1) & POOLMASK] ^
426 		     random_state.pool[i]; /* + 2^POOLWORDS */
427 
428 		random_state.pool[i] = (w >> 3) ^ twist_table[w & 7];
429 	}
430 }
431 
432 /*
433  * This function extracts randomness from the entropy pool, and
434  * returns it in a buffer.  This function computes how many remaining
435  * bits of entropy are left in the pool, but it does not restrict the
436  * number of bytes that are actually obtained.
437  */
438 static void
439 extract_entropy(u_int8_t *buf, int nbytes)
440 {
441 	struct random_bucket *rs = &random_state;
442 	u_char buffer[16];
443 	MD5_CTX tmp;
444 	u_int i;
445 
446 	add_timer_randomness(nbytes);
447 
448 	while (nbytes) {
449 		if (nbytes < sizeof(buffer) / 2)
450 			i = nbytes;
451 		else
452 			i = sizeof(buffer) / 2;
453 
454 		/* Hash the pool to get the output */
455 		MD5Init(&tmp);
456 		mtx_enter(&rndlock);
457 		MD5Update(&tmp, (u_int8_t*)rs->pool, sizeof(rs->pool));
458 		if (rs->entropy_count / 8 > i)
459 			rs->entropy_count -= i * 8;
460 		else
461 			rs->entropy_count = 0;
462 		mtx_leave(&rndlock);
463 		MD5Final(buffer, &tmp);
464 
465 		/*
466 		 * In case the hash function has some recognizable
467 		 * output pattern, we fold it in half.
468 		 */
469 		buffer[0] ^= buffer[15];
470 		buffer[1] ^= buffer[14];
471 		buffer[2] ^= buffer[13];
472 		buffer[3] ^= buffer[12];
473 		buffer[4] ^= buffer[11];
474 		buffer[5] ^= buffer[10];
475 		buffer[6] ^= buffer[ 9];
476 		buffer[7] ^= buffer[ 8];
477 
478 		/* Copy data to destination buffer */
479 		bcopy(buffer, buf, i);
480 		nbytes -= i;
481 		buf += i;
482 
483 		/* Modify pool so next hash will produce different results */
484 		add_timer_randomness(nbytes);
485 		dequeue_randomness(&random_state);
486 	}
487 
488 	/* Wipe data from memory */
489 	bzero(&tmp, sizeof(tmp));
490 	bzero(buffer, sizeof(buffer));
491 }
492 
493 /*
494  * Kernel-side entropy crediting API and handling of entropy-bearing events
495  * ------------------------------------------------------------------------
496  */
497 
498 /* pIII/333 reported to have some drops w/ these numbers */
499 #define QEVLEN (1024 / sizeof(struct rand_event))
500 #define QEVSLOW (QEVLEN * 3 / 4) /* yet another 0.75 for 60-minutes hour /-; */
501 #define QEVSBITS 10
502 
503 /* There is one of these per entropy source */
504 struct timer_rand_state {
505 	u_int	last_time;
506 	u_int	last_delta;
507 	u_int	last_delta2;
508 	u_int	dont_count_entropy : 1;
509 	u_int	max_entropy : 1;
510 };
511 
512 struct rand_event {
513 	struct timer_rand_state *re_state;
514 	u_int re_nbits;
515 	u_int re_time;
516 	u_int re_val;
517 };
518 
519 struct timer_rand_state rnd_states[RND_SRC_NUM];
520 struct rand_event rnd_event_space[QEVLEN];
521 struct rand_event *rnd_event_head = rnd_event_space;
522 struct rand_event *rnd_event_tail = rnd_event_space;
523 struct timeout rnd_timeout;
524 struct selinfo rnd_rsel;
525 struct rndstats rndstats;
526 int rnd_attached;
527 
528 /* must be called at a proper spl, returns ptr to the next event */
529 static __inline struct rand_event *
530 rnd_get(void)
531 {
532 	struct rand_event *p = rnd_event_tail;
533 
534 	if (p == rnd_event_head)
535 		return NULL;
536 
537 	if (p + 1 >= &rnd_event_space[QEVLEN])
538 		rnd_event_tail = rnd_event_space;
539 	else
540 		rnd_event_tail++;
541 
542 	return p;
543 }
544 
545 /* must be called at a proper spl, returns next available item */
546 static __inline struct rand_event *
547 rnd_put(void)
548 {
549 	struct rand_event *p = rnd_event_head + 1;
550 
551 	if (p >= &rnd_event_space[QEVLEN])
552 		p = rnd_event_space;
553 
554 	if (p == rnd_event_tail)
555 		return NULL;
556 
557 	return rnd_event_head = p;
558 }
559 
560 /* must be called at a proper spl, returns number of items in the queue */
561 static __inline int
562 rnd_qlen(void)
563 {
564 	int len = rnd_event_head - rnd_event_tail;
565 	return (len < 0)? -len : len;
566 }
567 
568 /*
569  * This function adds entropy to the entropy pool by using timing
570  * delays.  It uses the timer_rand_state structure to make an estimate
571  * of how many bits of entropy this call has added to the pool.
572  *
573  * The number "val" is also added to the pool - it should somehow describe
574  * the type of event which just happened.  Currently the values of 0-255
575  * are for keyboard scan codes, 256 and upwards - for interrupts.
576  * On the i386, this is assumed to be at most 16 bits, and the high bits
577  * are used for a high-resolution timer.
578  */
579 void
580 enqueue_randomness(int state, int val)
581 {
582 	struct timer_rand_state *p;
583 	struct rand_event *rep;
584 	struct timespec	tv;
585 	u_int	time, nbits;
586 
587 #ifdef DIAGNOSTIC
588 	if (state < 0 || state >= RND_SRC_NUM)
589 		return;
590 #endif
591 
592 	p = &rnd_states[state];
593 	val += state << 13;
594 
595 	if (!rnd_attached) {
596 		if ((rep = rnd_put()) == NULL) {
597 			rndstats.rnd_drops++;
598 			return;
599 		}
600 
601 		rep->re_state = &rnd_states[RND_SRC_TIMER];
602 		rep->re_nbits = 0;
603 		rep->re_time = 0;
604 		rep->re_time = val;
605 		return;
606 	}
607 
608 	nanotime(&tv);
609 	time = (tv.tv_nsec >> 10) + (tv.tv_sec << 20);
610 	nbits = 0;
611 
612 	/*
613 	 * Calculate the number of bits of randomness that we probably
614 	 * added.  We take into account the first and second order
615 	 * deltas in order to make our estimate.
616 	 */
617 	if (!p->dont_count_entropy) {
618 		int	delta, delta2, delta3;
619 		delta  = time   - p->last_time;
620 		delta2 = delta  - p->last_delta;
621 		delta3 = delta2 - p->last_delta2;
622 
623 		if (delta < 0) delta = -delta;
624 		if (delta2 < 0) delta2 = -delta2;
625 		if (delta3 < 0) delta3 = -delta3;
626 		if (delta > delta2) delta = delta2;
627 		if (delta > delta3) delta = delta3;
628 		delta3 = delta >>= 1;
629 		/*
630 		 * delta &= 0xfff;
631 		 * we don't do it since our time sheet is different from linux
632 		 */
633 
634 		if (delta & 0xffff0000) {
635 			nbits = 16;
636 			delta >>= 16;
637 		}
638 		if (delta & 0xff00) {
639 			nbits += 8;
640 			delta >>= 8;
641 		}
642 		if (delta & 0xf0) {
643 			nbits += 4;
644 			delta >>= 4;
645 		}
646 		if (delta & 0xc) {
647 			nbits += 2;
648 			delta >>= 2;
649 		}
650 		if (delta & 2) {
651 			nbits += 1;
652 			delta >>= 1;
653 		}
654 		if (delta & 1)
655 			nbits++;
656 
657 		/*
658 		 * the logic is to drop low-entropy entries,
659 		 * in hope for dequeuing to be more randomfull
660 		 */
661 		if (rnd_qlen() > QEVSLOW && nbits < QEVSBITS) {
662 			rndstats.rnd_drople++;
663 			return;
664 		}
665 		p->last_time = time;
666 		p->last_delta  = delta3;
667 		p->last_delta2 = delta2;
668 	} else if (p->max_entropy)
669 		nbits = 8 * sizeof(val) - 1;
670 
671 	/* given the multi-order delta logic above, this should never happen */
672 	if (nbits >= 32)
673 		return;
674 
675 	mtx_enter(&rndlock);
676 	if ((rep = rnd_put()) == NULL) {
677 		rndstats.rnd_drops++;
678 		mtx_leave(&rndlock);
679 		return;
680 	}
681 
682 	rep->re_state = p;
683 	rep->re_nbits = nbits;
684 	rep->re_time = tv.tv_nsec ^ (tv.tv_sec << 20);
685 	rep->re_val = val;
686 
687 	rndstats.rnd_enqs++;
688 	rndstats.rnd_ed[nbits]++;
689 	rndstats.rnd_sc[state]++;
690 	rndstats.rnd_sb[state] += nbits;
691 
692 	if (rnd_qlen() > QEVSLOW/2 && !random_state.tmo) {
693 		random_state.tmo++;
694 		timeout_add(&rnd_timeout, 1);
695 	}
696 	mtx_leave(&rndlock);
697 }
698 
699 static void
700 dequeue_randomness(void *v)
701 {
702 	struct random_bucket *rs = v;
703 	struct rand_event *rep;
704 	u_int32_t buf[2];
705 	u_int nbits;
706 
707 	timeout_del(&rnd_timeout);
708 	rndstats.rnd_deqs++;
709 
710 	mtx_enter(&rndlock);
711 	while ((rep = rnd_get())) {
712 
713 		buf[0] = rep->re_time;
714 		buf[1] = rep->re_val;
715 		nbits = rep->re_nbits;
716 		mtx_leave(&rndlock);
717 
718 		add_entropy_words(buf, 2);
719 
720 		rndstats.rnd_total += nbits;
721 		rs->entropy_count += nbits;
722 		if (rs->entropy_count > POOLBITS)
723 			rs->entropy_count = POOLBITS;
724 
725 		if (rs->asleep && rs->entropy_count > 8) {
726 #ifdef	RNDEBUG
727 			if (rnd_debug & RD_WAIT)
728 				printf("rnd: wakeup[%u]{%u}\n",
729 				    rs->asleep,
730 				    rs->entropy_count);
731 #endif
732 			rs->asleep--;
733 			wakeup((void *)&rs->asleep);
734 			selwakeup(&rnd_rsel);
735 			KNOTE(&rnd_rsel.si_note, 0);
736 		}
737 
738 		mtx_enter(&rndlock);
739 	}
740 
741 	rs->tmo = 0;
742 	mtx_leave(&rndlock);
743 }
744 
745 /*
746  * Exported kernel CPRNG API: arc4random() and friends
747  * ---------------------------------------------------
748  */
749 
750 /*
751  * Maximum number of bytes to serve directly from the main arc4random
752  * pool. Larger requests are served from discrete arc4 instances keyed
753  * from the main pool.
754  */
755 #define ARC4_MAIN_MAX_BYTES	2048
756 
757 /*
758  * Key size (in bytes) for arc4 instances setup to serve requests larger
759  * than ARC4_MAIN_MAX_BYTES.
760  */
761 #define ARC4_SUB_KEY_BYTES	(256 / 8)
762 
763 struct timeout arc4_timeout;
764 struct rc4_ctx arc4random_state;
765 int arc4random_initialized;
766 u_long arc4random_count = 0;
767 
768 /*
769  * This function returns some number of good random numbers but is quite
770  * slow. Please use arc4random_buf() instead unless very high quality
771  * randomness is required.
772  * XXX: rename this
773  */
774 void
775 get_random_bytes(void *buf, size_t nbytes)
776 {
777 	extract_entropy((u_int8_t *) buf, nbytes);
778 	rndstats.rnd_used += nbytes * 8;
779 }
780 
781 static void
782 arc4_stir(void)
783 {
784 	u_int8_t buf[256];
785 	int len;
786 
787 	nanotime((struct timespec *) buf);
788 	len = sizeof(buf) - sizeof(struct timespec);
789 	get_random_bytes(buf + sizeof (struct timespec), len);
790 	len += sizeof(struct timespec);
791 
792 	mtx_enter(&rndlock);
793 	if (rndstats.arc4_nstirs > 0)
794 		rc4_crypt(&arc4random_state, buf, buf, sizeof(buf));
795 
796 	rc4_keysetup(&arc4random_state, buf, sizeof(buf));
797 	arc4random_count = 0;
798 	rndstats.arc4_stirs += len;
799 	rndstats.arc4_nstirs++;
800 
801 	/*
802 	 * Throw away the first N words of output, as suggested in the
803 	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
804 	 * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
805 	 */
806 	rc4_skip(&arc4random_state, 256 * 4);
807 	mtx_leave(&rndlock);
808 }
809 
810 /*
811  * called by timeout to mark arc4 for stirring,
812  * actual stirring happens on any access attempt.
813  */
814 static void
815 arc4_reinit(void *v)
816 {
817 	arc4random_initialized = 0;
818 }
819 
820 static void
821 arc4maybeinit(void)
822 {
823 
824 	if (!arc4random_initialized) {
825 #ifdef DIAGNOSTIC
826 		if (!rnd_attached)
827 			panic("arc4maybeinit: premature");
828 #endif
829 		arc4random_initialized++;
830 		arc4_stir();
831 		/* 10 minutes, per dm@'s suggestion */
832 		timeout_add_sec(&arc4_timeout, 10 * 60);
833 	}
834 }
835 
836 void
837 randomattach(void)
838 {
839 	if (rnd_attached) {
840 #ifdef RNDEBUG
841 		printf("random: second attach\n");
842 #endif
843 		return;
844 	}
845 
846 	timeout_set(&rnd_timeout, dequeue_randomness, &random_state);
847 	timeout_set(&arc4_timeout, arc4_reinit, NULL);
848 
849 	random_state.add_ptr = 0;
850 	random_state.entropy_count = 0;
851 	rnd_states[RND_SRC_TIMER].dont_count_entropy = 1;
852 	rnd_states[RND_SRC_TRUE].dont_count_entropy = 1;
853 	rnd_states[RND_SRC_TRUE].max_entropy = 1;
854 
855 	mtx_init(&rndlock, IPL_HIGH);
856 	arc4_reinit(NULL);
857 
858 	if (msgbufp && msgbufp->msg_magic == MSG_MAGIC)
859 		add_entropy_words((u_int32_t *)msgbufp->msg_bufc,
860 		    msgbufp->msg_bufs / sizeof(u_int32_t));
861 	rnd_attached = 1;
862 }
863 
864 /* Return one word of randomness from an RC4 generator */
865 u_int32_t
866 arc4random(void)
867 {
868 	u_int32_t ret;
869 
870 	arc4maybeinit();
871 	mtx_enter(&rndlock);
872 	rc4_getbytes(&arc4random_state, (u_char*)&ret, sizeof(ret));
873 	rndstats.arc4_reads += sizeof(ret);
874 	arc4random_count += sizeof(ret);
875 	mtx_leave(&rndlock);
876 	return ret;
877 }
878 
879 /*
880  * Return a "large" buffer of randomness using an independantly-keyed RC4
881  * generator.
882  */
883 static void
884 arc4random_buf_large(void *buf, size_t n)
885 {
886 	u_char lbuf[ARC4_SUB_KEY_BYTES];
887 	struct rc4_ctx lctx;
888 
889 	mtx_enter(&rndlock);
890 	rc4_getbytes(&arc4random_state, lbuf, sizeof(lbuf));
891 	rndstats.arc4_reads += n;
892 	arc4random_count += sizeof(lbuf);
893 	mtx_leave(&rndlock);
894 
895 	rc4_keysetup(&lctx, lbuf, sizeof(lbuf));
896 	rc4_skip(&lctx, 256 * 4);
897 	rc4_getbytes(&lctx, (u_char*)buf, n);
898 	bzero(lbuf, sizeof(lbuf));
899 	bzero(&lctx, sizeof(lctx));
900 }
901 
902 /*
903  * Fill a buffer of arbitrary length with RC4-derived randomness.
904  */
905 void
906 arc4random_buf(void *buf, size_t n)
907 {
908 	arc4maybeinit();
909 
910 	/* Satisfy large requests via an independent ARC4 instance */
911 	if (n > ARC4_MAIN_MAX_BYTES) {
912 		arc4random_buf_large(buf, n);
913 		return;
914 	}
915 
916 	mtx_enter(&rndlock);
917 	rc4_getbytes(&arc4random_state, (u_char*)buf, n);
918 	rndstats.arc4_reads += n;
919 	arc4random_count += n;
920 	mtx_leave(&rndlock);
921 }
922 
923 /*
924  * Calculate a uniformly distributed random number less than upper_bound
925  * avoiding "modulo bias".
926  *
927  * Uniformity is achieved by generating new random numbers until the one
928  * returned is outside the range [0, 2**32 % upper_bound).  This
929  * guarantees the selected random number will be inside
930  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
931  * after reduction modulo upper_bound.
932  */
933 u_int32_t
934 arc4random_uniform(u_int32_t upper_bound)
935 {
936 	u_int32_t r, min;
937 
938 	if (upper_bound < 2)
939 		return 0;
940 
941 #if (ULONG_MAX > 0xffffffffUL)
942 	min = 0x100000000UL % upper_bound;
943 #else
944 	/* Calculate (2**32 % upper_bound) avoiding 64-bit math */
945 	if (upper_bound > 0x80000000)
946 		min = 1 + ~upper_bound;		/* 2**32 - upper_bound */
947 	else {
948 		/* (2**32 - x) % x == 2**32 % x when x <= 2**31 */
949 		min = ((0xffffffff - upper_bound) + 1) % upper_bound;
950 	}
951 #endif
952 
953 	/*
954 	 * This could theoretically loop forever but each retry has
955 	 * p > 0.5 (worst case, usually far better) of selecting a
956 	 * number inside the range we need, so it should rarely need
957 	 * to re-roll.
958 	 */
959 	for (;;) {
960 		r = arc4random();
961 		if (r >= min)
962 			break;
963 	}
964 
965 	return r % upper_bound;
966 }
967 
968 /*
969  * random, srandom, urandom, arandom char devices
970  * -------------------------------------------------------
971  */
972 
973 void filt_rndrdetach(struct knote *kn);
974 int filt_rndread(struct knote *kn, long hint);
975 
976 struct filterops rndread_filtops =
977 	{ 1, NULL, filt_rndrdetach, filt_rndread};
978 
979 void filt_rndwdetach(struct knote *kn);
980 int filt_rndwrite(struct knote *kn, long hint);
981 
982 struct filterops rndwrite_filtops =
983 	{ 1, NULL, filt_rndwdetach, filt_rndwrite};
984 
985 struct selinfo rnd_wsel;
986 
987 int
988 randomopen(dev_t dev, int flag, int mode, struct proc *p)
989 {
990 	return (minor (dev) < RND_NODEV) ? 0 : ENXIO;
991 }
992 
993 int
994 randomclose(dev_t dev, int flag, int mode, struct proc *p)
995 {
996 	return 0;
997 }
998 
999 int
1000 randomread(dev_t dev, struct uio *uio, int ioflag)
1001 {
1002 	int		ret = 0;
1003 	u_int32_t 	*buf;
1004 
1005 	if (uio->uio_resid == 0)
1006 		return 0;
1007 
1008 	buf = malloc(POOLBYTES, M_TEMP, M_WAITOK);
1009 
1010 	while (!ret && uio->uio_resid > 0) {
1011 		int	n = min(POOLBYTES, uio->uio_resid);
1012 
1013 		switch(minor(dev)) {
1014 		case RND_RND:
1015 			ret = EIO;	/* no chip -- error */
1016 			break;
1017 		case RND_SRND:
1018 			if (random_state.entropy_count < 16 * 8) {
1019 				if (ioflag & IO_NDELAY) {
1020 					ret = EWOULDBLOCK;
1021 					break;
1022 				}
1023 #ifdef	RNDEBUG
1024 				if (rnd_debug & RD_WAIT)
1025 					printf("rnd: sleep[%u]\n",
1026 					    random_state.asleep);
1027 #endif
1028 				random_state.asleep++;
1029 				rndstats.rnd_waits++;
1030 				ret = tsleep(&random_state.asleep,
1031 				    PWAIT | PCATCH, "rndrd", 0);
1032 #ifdef	RNDEBUG
1033 				if (rnd_debug & RD_WAIT)
1034 					printf("rnd: awakened(%d)\n", ret);
1035 #endif
1036 				if (ret)
1037 					break;
1038 			}
1039 			if (n > random_state.entropy_count / 8)
1040 				n = random_state.entropy_count / 8;
1041 			rndstats.rnd_reads++;
1042 #ifdef	RNDEBUG
1043 			if (rnd_debug & RD_OUTPUT)
1044 				printf("rnd: %u possible output\n", n);
1045 #endif
1046 		case RND_URND:
1047 			get_random_bytes((char *)buf, n);
1048 #ifdef	RNDEBUG
1049 			if (rnd_debug & RD_OUTPUT)
1050 				printf("rnd: %u bytes for output\n", n);
1051 #endif
1052 			break;
1053 		case RND_ARND_OLD:
1054 		case RND_ARND:
1055 			arc4random_buf(buf, n);
1056 			break;
1057 		default:
1058 			ret = ENXIO;
1059 		}
1060 		if (n != 0 && ret == 0) {
1061 			ret = uiomove((caddr_t)buf, n, uio);
1062 			if (!ret && uio->uio_resid > 0)
1063 				yield();
1064 		}
1065 	}
1066 
1067 	free(buf, M_TEMP);
1068 	return ret;
1069 }
1070 
1071 int
1072 randompoll(dev_t dev, int events, struct proc *p)
1073 {
1074 	int revents;
1075 
1076 	revents = events & (POLLOUT | POLLWRNORM);	/* always writable */
1077 	if (events & (POLLIN | POLLRDNORM)) {
1078 		if (minor(dev) == RND_SRND && random_state.entropy_count <= 0)
1079 			selrecord(p, &rnd_rsel);
1080 		else
1081 			revents |= events & (POLLIN | POLLRDNORM);
1082 	}
1083 
1084 	return (revents);
1085 }
1086 
1087 int
1088 randomkqfilter(dev_t dev, struct knote *kn)
1089 {
1090 	struct klist *klist;
1091 
1092 	switch (kn->kn_filter) {
1093 	case EVFILT_READ:
1094 		klist = &rnd_rsel.si_note;
1095 		kn->kn_fop = &rndread_filtops;
1096 		break;
1097 	case EVFILT_WRITE:
1098 		klist = &rnd_wsel.si_note;
1099 		kn->kn_fop = &rndwrite_filtops;
1100 		break;
1101 	default:
1102 		return (1);
1103 	}
1104 	kn->kn_hook = (void *)&random_state;
1105 
1106 	mtx_enter(&rndlock);
1107 	SLIST_INSERT_HEAD(klist, kn, kn_selnext);
1108 	mtx_leave(&rndlock);
1109 
1110 	return (0);
1111 }
1112 
1113 void
1114 filt_rndrdetach(struct knote *kn)
1115 {
1116 	mtx_enter(&rndlock);
1117 	SLIST_REMOVE(&rnd_rsel.si_note, kn, knote, kn_selnext);
1118 	mtx_leave(&rndlock);
1119 }
1120 
1121 int
1122 filt_rndread(struct knote *kn, long hint)
1123 {
1124 	struct random_bucket *rs = (struct random_bucket *)kn->kn_hook;
1125 
1126 	kn->kn_data = (int)rs->entropy_count;
1127 	return rs->entropy_count > 0;
1128 }
1129 
1130 void
1131 filt_rndwdetach(struct knote *kn)
1132 {
1133 	mtx_enter(&rndlock);
1134 	SLIST_REMOVE(&rnd_wsel.si_note, kn, knote, kn_selnext);
1135 	mtx_leave(&rndlock);
1136 }
1137 
1138 int
1139 filt_rndwrite(struct knote *kn, long hint)
1140 {
1141 	return (1);
1142 }
1143 
1144 int
1145 randomwrite(dev_t dev, struct uio *uio, int flags)
1146 {
1147 	int		ret = 0;
1148 	u_int32_t	*buf;
1149 
1150 	if (minor(dev) == RND_RND)
1151 		return ENXIO;
1152 
1153 	if (uio->uio_resid == 0)
1154 		return 0;
1155 
1156 	buf = malloc(POOLBYTES, M_TEMP, M_WAITOK);
1157 
1158 	while (!ret && uio->uio_resid > 0) {
1159 		u_short	n = min(POOLBYTES, uio->uio_resid);
1160 
1161 		ret = uiomove((caddr_t)buf, n, uio);
1162 		if (!ret) {
1163 			while (n % sizeof(u_int32_t))
1164 				((u_int8_t *) buf)[n++] = 0;
1165 			add_entropy_words(buf, n / 4);
1166 		}
1167 	}
1168 
1169 	if ((minor(dev) == RND_ARND || minor(dev) == RND_ARND_OLD) &&
1170 	    !ret)
1171 		arc4random_initialized = 0;
1172 
1173 	free(buf, M_TEMP);
1174 	return ret;
1175 }
1176 
1177 int
1178 randomioctl(dev_t dev, u_long cmd, caddr_t data, int flag, struct proc *p)
1179 {
1180 	int	ret = 0;
1181 	u_int	cnt;
1182 
1183 	add_timer_randomness((u_long)p ^ (u_long)data ^ cmd);
1184 
1185 	switch (cmd) {
1186 	case FIOASYNC:
1187 		/* rnd has no async flag in softc so this is really a no-op. */
1188 		break;
1189 
1190 	case FIONBIO:
1191 		/* Handled in the upper FS layer. */
1192 		break;
1193 
1194 	case RNDGETENTCNT:
1195 		mtx_enter(&rndlock);
1196 		*(u_int *)data = random_state.entropy_count;
1197 		mtx_leave(&rndlock);
1198 		break;
1199 	case RNDADDTOENTCNT:
1200 		if (suser(p, 0) != 0)
1201 			ret = EPERM;
1202 		else {
1203 			cnt = *(u_int *)data;
1204 			mtx_enter(&rndlock);
1205 			random_state.entropy_count += cnt;
1206 			if (random_state.entropy_count > POOLBITS)
1207 				random_state.entropy_count = POOLBITS;
1208 			mtx_leave(&rndlock);
1209 		}
1210 		break;
1211 	case RNDZAPENTCNT:
1212 		if (suser(p, 0) != 0)
1213 			ret = EPERM;
1214 		else {
1215 			mtx_enter(&rndlock);
1216 			random_state.entropy_count = 0;
1217 			mtx_leave(&rndlock);
1218 		}
1219 		break;
1220 	case RNDSTIRARC4:
1221 		if (suser(p, 0) != 0)
1222 			ret = EPERM;
1223 		else if (random_state.entropy_count < 64)
1224 			ret = EAGAIN;
1225 		else {
1226 			mtx_enter(&rndlock);
1227 			arc4random_initialized = 0;
1228 			mtx_leave(&rndlock);
1229 		}
1230 		break;
1231 	case RNDCLRSTATS:
1232 		if (suser(p, 0) != 0)
1233 			ret = EPERM;
1234 		else {
1235 			mtx_enter(&rndlock);
1236 			bzero(&rndstats, sizeof(rndstats));
1237 			mtx_leave(&rndlock);
1238 		}
1239 		break;
1240 	default:
1241 		ret = ENOTTY;
1242 	}
1243 
1244 	add_timer_randomness((u_long)p ^ (u_long)data ^ cmd);
1245 	return ret;
1246 }
1247