2 * random_machdep.c -- A strong random number generator
6 * Version 0.95, last modified 18-Oct-95
8 * Copyright Theodore Ts'o, 1994, 1995. All rights reserved.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, and the entire permission notice in its entirety,
15 * including the disclaimer of warranties.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. The name of the author may not be used to endorse or promote
20 * products derived from this software without specific prior
23 * ALTERNATIVELY, this product may be distributed under the terms of
24 * the GNU Public License, in which case the provisions of the GPL are
25 * required INSTEAD OF the above restrictions. (This clause is
26 * necessary due to a potential bad interaction between the GPL and
27 * the restrictions contained in a BSD-style copyright.)
29 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
30 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
31 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
32 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
33 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
34 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
35 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
37 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
38 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
39 * OF THE POSSIBILITY OF SUCH DAMAGE.
42 #include <sys/param.h>
43 #include <sys/systm.h>
44 #include <sys/kernel.h>
45 #include <sys/select.h>
47 #include <sys/timetc.h>
50 #include <machine/random.h>
52 #include <i386/isa/icu.h>
57 * The pool is stirred with a primitive polynomial of degree 128
58 * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
59 * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
61 #define POOLWORDS 128 /* Power of 2 - note that this is 32-bit words */
62 #define POOLBITS (POOLWORDS*32)
65 #define TAP1 99 /* The polynomial taps */
71 #define TAP1 62 /* The polynomial taps */
77 #error No primitive polynomial available for chosen POOLWORDS
80 #define WRITEBUFFER 512 /* size in bytes */
82 /* There is actually only one of these, globally. */
83 struct random_bucket {
91 /* There is one of these per entropy source */
92 struct timer_rand_state {
98 static struct random_bucket random_state;
99 static u_int32_t random_pool[POOLWORDS];
100 static struct timer_rand_state keyboard_timer_state;
101 static struct timer_rand_state extract_timer_state;
102 static struct timer_rand_state irq_timer_state[ICU_LEN];
104 static struct timer_rand_state blkdev_timer_state[MAX_BLKDEV];
106 static struct wait_queue *random_wait;
109 #define MIN(a,b) (((a) < (b)) ? (a) : (b))
113 rand_initialize(void)
115 random_state.add_ptr = 0;
116 random_state.entropy_count = 0;
117 random_state.pool = random_pool;
119 random_state.rsel.si_flags = 0;
120 random_state.rsel.si_pid = 0;
124 * This function adds an int into the entropy "pool". It does not
125 * update the entropy estimate. The caller must do this if appropriate.
127 * The pool is stirred with a primitive polynomial of degree 128
128 * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
129 * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
131 * We rotate the input word by a changing number of bits, to help
132 * assure that all bits in the entropy get toggled. Otherwise, if we
133 * consistently feed the entropy pool small numbers (like ticks and
134 * scancodes, for example), the upper bits of the entropy pool don't
135 * get affected. --- TYT, 10/11/95
138 add_entropy_word(struct random_bucket *r, const u_int32_t input)
143 w = (input << r->input_rotate) | (input >> (32 - r->input_rotate));
144 i = r->add_ptr = (r->add_ptr - 1) & (POOLWORDS-1);
146 r->input_rotate = (r->input_rotate + 7) & 31;
149 * At the beginning of the pool, add an extra 7 bits
150 * rotation, so that successive passes spread the
151 * input bits across the pool evenly.
153 r->input_rotate = (r->input_rotate + 14) & 31;
155 /* XOR in the various taps */
156 w ^= r->pool[(i+TAP1)&(POOLWORDS-1)];
157 w ^= r->pool[(i+TAP2)&(POOLWORDS-1)];
158 w ^= r->pool[(i+TAP3)&(POOLWORDS-1)];
159 w ^= r->pool[(i+TAP4)&(POOLWORDS-1)];
160 w ^= r->pool[(i+TAP5)&(POOLWORDS-1)];
162 /* Rotate w left 1 bit (stolen from SHA) and store */
163 r->pool[i] = (w << 1) | (w >> 31);
167 * This function adds entropy to the entropy "pool" by using timing
168 * delays. It uses the timer_rand_state structure to make an estimate
169 * of how any bits of entropy this call has added to the pool.
171 * The number "num" is also added to the pool - it should somehow describe
172 * the type of event which just happened. This is currently 0-255 for
173 * keyboard scan codes, and 256 upwards for interrupts.
174 * On the i386, this is assumed to be at most 16 bits, and the high bits
175 * are used for a high-resolution timer.
178 add_timer_randomness(struct random_bucket *r, struct timer_rand_state *state,
185 num ^= timecounter->tc_get_timecount(timecounter) << 16;
186 r->entropy_count += 2;
190 add_entropy_word(r, (u_int32_t) num);
191 add_entropy_word(r, time);
194 * Calculate number of bits of randomness we probably
195 * added. We take into account the first and second order
196 * deltas in order to make our estimate.
198 delta = time - state->last_time;
199 state->last_time = time;
201 delta2 = delta - state->last_delta;
202 state->last_delta = delta;
204 if (delta < 0) delta = -delta;
205 if (delta2 < 0) delta2 = -delta2;
206 delta = MIN(delta, delta2) >> 1;
207 for (nbits = 0; delta; nbits++)
210 r->entropy_count += nbits;
212 /* Prevent overflow */
213 if (r->entropy_count > POOLBITS)
214 r->entropy_count = POOLBITS;
216 if (r->entropy_count >= 8)
217 selwakeup(&random_state.rsel);
221 add_keyboard_randomness(u_char scancode)
223 add_timer_randomness(&random_state, &keyboard_timer_state, scancode);
227 add_interrupt_randomness(void *vsc)
230 struct random_softc *sc = vsc;
232 (sc->sc_handler)(sc->sc_arg);
234 add_timer_randomness(&random_state, &irq_timer_state[intr], intr);
239 add_blkdev_randomness(int major)
241 if (major >= MAX_BLKDEV)
244 add_timer_randomness(&random_state, &blkdev_timer_state[major],
250 #error extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
253 * This function extracts randomness from the "entropy pool", and
254 * returns it in a buffer. This function computes how many remaining
255 * bits of entropy are left in the pool, but it does not restrict the
256 * number of bytes that are actually obtained.
259 extract_entropy(struct random_bucket *r, char *buf, int nbytes)
264 add_timer_randomness(r, &extract_timer_state, nbytes);
266 /* Redundant, but just in case... */
267 if (r->entropy_count > POOLBITS)
268 r->entropy_count = POOLBITS;
269 /* Why is this here? Left in from Ted Ts'o. Perhaps to limit time. */
274 if (r->entropy_count / 8 >= nbytes)
275 r->entropy_count -= nbytes*8;
277 r->entropy_count = 0;
280 /* Hash the pool to get the output */
285 for (i = 0; i < POOLWORDS; i += 16)
286 MD5Transform(tmp, (char *)(r->pool+i));
287 /* Modify pool so next hash will produce different results */
288 add_entropy_word(r, tmp[0]);
289 add_entropy_word(r, tmp[1]);
290 add_entropy_word(r, tmp[2]);
291 add_entropy_word(r, tmp[3]);
293 * Run the MD5 Transform one more time, since we want
294 * to add at least minimal obscuring of the inputs to
295 * add_entropy_word(). --- TYT
297 MD5Transform(tmp, (char *)(r->pool));
299 /* Copy data to destination buffer */
306 /* Wipe data from memory */
307 bzero(tmp, sizeof(tmp));
312 #ifdef notused /* XXX NOT the exported kernel interface */
314 * This function is the exported kernel interface. It returns some
315 * number of good random numbers, suitable for seeding TCP sequence
319 get_random_bytes(void *buf, u_int nbytes)
321 extract_entropy(&random_state, (char *) buf, nbytes);
326 read_random(void *buf, u_int nbytes)
328 if ((nbytes * 8) > random_state.entropy_count)
329 nbytes = random_state.entropy_count / 8;
331 return extract_entropy(&random_state, (char *)buf, nbytes);
335 read_random_unlimited(void *buf, u_int nbytes)
337 return extract_entropy(&random_state, (char *)buf, nbytes);
342 write_random(const char *buf, u_int nbytes)
347 for (i = nbytes, p = (u_int32_t *)buf;
348 i >= sizeof(u_int32_t);
349 i-= sizeof(u_int32_t), p++)
350 add_entropy_word(&random_state, *p);
354 add_entropy_word(&random_state, word);
361 random_poll(dev_t dev, int events, struct proc *p)
367 if (events & (POLLIN | POLLRDNORM)) {
368 if (random_state.entropy_count >= 8)
369 revents |= events & (POLLIN | POLLRDNORM);
371 selrecord(p, &random_state.rsel);
374 if (events & (POLLOUT | POLLWRNORM))
375 revents |= events & (POLLOUT | POLLWRNORM); /* heh */