Annotation of sys/dev/rnd.c, Revision 1.1.1.1
1.1 nbrk 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: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to rnd.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / dev