2 * kern_random.c -- A strong random number generator
4 * $FreeBSD: src/sys/kern/kern_random.c,v 1.36.2.4 2002/09/17 17:11:57 sam Exp $
5 * $DragonFly: src/sys/kern/Attic/kern_random.c,v 1.14 2006/04/12 18:28:30 dillon Exp $
7 * Version 0.95, last modified 18-Oct-95
9 * Copyright Theodore Ts'o, 1994, 1995. All rights reserved.
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, and the entire permission notice in its entirety,
16 * including the disclaimer of warranties.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. The name of the author may not be used to endorse or promote
21 * products derived from this software without specific prior
24 * ALTERNATIVELY, this product may be distributed under the terms of
25 * the GNU Public License, in which case the provisions of the GPL are
26 * required INSTEAD OF the above restrictions. (This clause is
27 * necessary due to a potential bad interaction between the GPL and
28 * the restrictions contained in a BSD-style copyright.)
30 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
31 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
33 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
34 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
35 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
36 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
38 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
39 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
40 * OF THE POSSIBILITY OF SUCH DAMAGE.
43 #include <sys/param.h>
44 #include <sys/kernel.h>
47 #include <sys/random.h>
48 #include <sys/select.h>
49 #include <sys/systm.h>
50 #include <sys/systimer.h>
51 #include <sys/thread2.h>
53 #include <machine/clock.h>
56 #include <i386/icu/icu.h>
62 * The pool is stirred with a primitive polynomial of degree 128
63 * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
64 * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
66 #define POOLWORDS 128 /* Power of 2 - note that this is 32-bit words */
67 #define POOLBITS (POOLWORDS*32)
70 #define TAP1 99 /* The polynomial taps */
76 #define TAP1 62 /* The polynomial taps */
82 #error No primitive polynomial available for chosen POOLWORDS
85 #define WRITEBUFFER 512 /* size in bytes */
88 * This is the number of bits represented by entropy_count. A value of
89 * 8 would represent an ultra-conservative value, while a value of 2
90 * would be ultra-liberal. Use a value of 4.
93 #define MIN_BITS (STATE_BITS*4)
95 /* There is actually only one of these, globally. */
96 struct random_bucket {
104 /* There is one of these per entropy source */
105 struct timer_rand_state {
111 static struct random_bucket random_state;
112 static u_int32_t random_pool[POOLWORDS];
113 static struct random_bucket urandom_state;
114 static u_int32_t urandom_pool[POOLWORDS];
115 static struct timer_rand_state keyboard_timer_state;
116 static struct timer_rand_state keyboard_utimer_state;
117 static struct timer_rand_state extract_timer_state;
118 static struct timer_rand_state irq_timer_state[MAX_INTS];
119 static struct timer_rand_state irq_utimer_state[MAX_INTS];
121 static struct timer_rand_state blkdev_timer_state[MAX_BLKDEV];
123 static thread_t rand_td;
124 static int rand_td_slot;
126 static void add_timer_randomness(struct random_bucket *r,
127 struct timer_rand_state *state, u_int num);
130 * Called from early boot
133 rand_initialize(void)
135 random_state.pool = random_pool;
136 urandom_state.pool = urandom_pool;
140 * Random number generator helper thread.
142 * Note that rand_td_slot is initially 0, which means nothing will try
143 * to schedule our thread until we reset it to -1. This also prevents
144 * any attempt to schedule the thread before it has been initialized.
148 rand_thread_loop(void *dummy)
154 if ((slot = rand_td_slot) >= 0) {
155 add_timer_randomness(&urandom_state,
156 &irq_timer_state[slot],
158 add_timer_randomness(&random_state,
159 &irq_utimer_state[slot],
164 * The fewer bits we have, the shorter we sleep, up to a
165 * point. We use an interrupt to trigger the thread once
166 * we have slept the calculated amount of time. This limits
167 * the wakeup rate AND gives us a good interrupt-based
168 * timer value at the same time.
170 * Use /dev/random's entropy count rather than /dev/urandom's.
171 * Things like the stacksmash code use /dev/urandom on program
172 * exec all the time, and it is not likely to ever have
175 count = random_state.entropy_count * hz / POOLBITS;
180 tsleep(rand_td, 0, "rwait", count);
181 lwkt_deschedule_self(rand_td);
189 rand_thread_init(void)
191 lwkt_create(rand_thread_loop, NULL, &rand_td, NULL, 0, 0, "random");
194 SYSINIT(rand, SI_SUB_HELPER_THREADS, SI_ORDER_ANY, rand_thread_init, 0);
197 * This function adds an int into the entropy "pool". It does not
198 * update the entropy estimate. The caller must do this if appropriate.
200 * The pool is stirred with a primitive polynomial of degree 128
201 * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
202 * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
204 * We rotate the input word by a changing number of bits, to help
205 * assure that all bits in the entropy get toggled. Otherwise, if we
206 * consistently feed the entropy pool small numbers (like ticks and
207 * scancodes, for example), the upper bits of the entropy pool don't
208 * get affected. --- TYT, 10/11/95
211 add_entropy_word(struct random_bucket *r, const u_int32_t input)
216 w = (input << r->input_rotate) | (input >> (32 - r->input_rotate));
217 i = r->add_ptr = (r->add_ptr - 1) & (POOLWORDS-1);
219 r->input_rotate = (r->input_rotate + 7) & 31;
222 * At the beginning of the pool, add an extra 7 bits
223 * rotation, so that successive passes spread the
224 * input bits across the pool evenly.
226 r->input_rotate = (r->input_rotate + 14) & 31;
228 /* XOR in the various taps */
229 w ^= r->pool[(i+TAP1)&(POOLWORDS-1)];
230 w ^= r->pool[(i+TAP2)&(POOLWORDS-1)];
231 w ^= r->pool[(i+TAP3)&(POOLWORDS-1)];
232 w ^= r->pool[(i+TAP4)&(POOLWORDS-1)];
233 w ^= r->pool[(i+TAP5)&(POOLWORDS-1)];
235 /* Rotate w left 1 bit (stolen from SHA) and store */
236 r->pool[i] = (w << 1) | (w >> 31);
240 * This function adds entropy to the entropy "pool" by using timing
241 * delays. It uses the timer_rand_state structure to make an estimate
242 * of how any bits of entropy this call has added to the pool.
244 * The number "num" is also added to the pool - it should somehow describe
245 * the type of event which just happened. This is currently 0-255 for
246 * keyboard scan codes, and 256 upwards for interrupts.
247 * On the i386, this is assumed to be at most 16 bits, and the high bits
248 * are used for a high-resolution timer.
251 add_timer_randomness(struct random_bucket *r, struct timer_rand_state *state,
259 num ^= sys_cputimer->count() << 16;
261 num ^= ~(u_int)rdtsc();
262 count = r->entropy_count + 2;
263 if (count > POOLBITS)
265 r->entropy_count = count;
269 add_entropy_word(r, (u_int32_t) num);
270 add_entropy_word(r, time);
273 * Calculate number of bits of randomness we probably
274 * added. We take into account the first and second order
275 * deltas in order to make our estimate.
277 delta = time - state->last_time;
278 state->last_time = time;
280 delta2 = delta - state->last_delta;
281 state->last_delta = delta;
283 if (delta < 0) delta = -delta;
284 if (delta2 < 0) delta2 = -delta2;
285 delta = MIN(delta, delta2) >> 1;
286 for (nbits = 0; delta; nbits++)
289 /* Prevent overflow */
290 count = r->entropy_count + nbits;
291 if (count > POOLBITS)
294 r->entropy_count = count;
296 if (count >= MIN_BITS && try_mplock()) {
303 add_keyboard_randomness(u_char scancode)
305 add_timer_randomness(&random_state, &keyboard_timer_state, scancode);
306 add_timer_randomness(&urandom_state, &keyboard_utimer_state, scancode);
310 * This routine is called from an interrupt and must be very efficient.
313 add_interrupt_randomness(int intr)
315 if (rand_td_slot < 0) {
317 lwkt_schedule(rand_td);
323 add_blkdev_randomness(int major)
325 if (major >= MAX_BLKDEV)
328 add_timer_randomness(&random_state, &blkdev_timer_state[major],
334 #error extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
337 * This function extracts randomness from the "entropy pool", and
338 * returns it in a buffer. This function computes how many remaining
339 * bits of entropy are left in the pool, but it does not restrict the
340 * number of bytes that are actually obtained.
343 extract_entropy(struct random_bucket *r, char *buf, int nbytes)
348 add_timer_randomness(r, &extract_timer_state, nbytes);
350 /* Redundant, but just in case... */
351 if (r->entropy_count > POOLBITS)
352 r->entropy_count = POOLBITS;
353 /* Why is this here? Left in from Ted Ts'o. Perhaps to limit time. */
358 if (r->entropy_count > nbytes * STATE_BITS)
359 r->entropy_count -= nbytes * STATE_BITS;
361 r->entropy_count = 0;
364 /* Hash the pool to get the output */
369 for (i = 0; i < POOLWORDS; i += 16)
370 MD5Transform(tmp, (char *)(r->pool+i));
371 /* Modify pool so next hash will produce different results */
372 add_entropy_word(r, tmp[0]);
373 add_entropy_word(r, tmp[1]);
374 add_entropy_word(r, tmp[2]);
375 add_entropy_word(r, tmp[3]);
377 * Run the MD5 Transform one more time, since we want
378 * to add at least minimal obscuring of the inputs to
379 * add_entropy_word(). --- TYT
381 MD5Transform(tmp, (char *)(r->pool));
383 /* Copy data to destination buffer */
390 /* Wipe data from memory */
391 bzero(tmp, sizeof(tmp));
396 #ifdef notused /* XXX NOT the exported kernel interface */
398 * This function is the exported kernel interface. It returns some
399 * number of good random numbers, suitable for seeding TCP sequence
403 get_random_bytes(void *buf, u_int nbytes)
405 extract_entropy(&random_state, (char *) buf, nbytes);
410 read_random(void *buf, u_int nbytes)
412 if (random_state.entropy_count < MIN_BITS)
414 if ((nbytes * STATE_BITS) > random_state.entropy_count)
415 nbytes = random_state.entropy_count / STATE_BITS;
417 return extract_entropy(&random_state, (char *)buf, nbytes);
421 read_random_unlimited(void *buf, u_int nbytes)
423 return extract_entropy(&urandom_state, (char *)buf, nbytes);
428 write_random(const char *buf, u_int nbytes)
433 for (i = nbytes, p = (u_int32_t *)buf;
434 i >= sizeof(u_int32_t);
435 i-= sizeof(u_int32_t), p++)
436 add_entropy_word(&random_state, *p);
440 add_entropy_word(&random_state, word);
447 add_true_randomness(int val)
451 add_entropy_word(&random_state, val);
452 count = random_state.entropy_count + 8 *sizeof(val);
453 if (count > POOLBITS)
455 random_state.entropy_count = count;
456 selwakeup(&random_state.rsel);
460 * Returns whether /dev/random has data or not. entropy_count must be
461 * at least STATE_BITS.
464 random_poll(dev_t dev, int events, struct thread *td)
469 if (events & (POLLIN | POLLRDNORM)) {
470 if (random_state.entropy_count >= MIN_BITS)
471 revents |= events & (POLLIN | POLLRDNORM);
473 selrecord(td, &random_state.rsel);
476 if (events & (POLLOUT | POLLWRNORM))
477 revents |= events & (POLLOUT | POLLWRNORM); /* heh */