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