This commit represents a major revamping of the clock interrupt and timebase
[dragonfly.git] / sys / kern / kern_random.c
CommitLineData
984263bc
MD
1/*
2 * kern_random.c -- A strong random number generator
3 *
4 * $FreeBSD: src/sys/kern/kern_random.c,v 1.36.2.4 2002/09/17 17:11:57 sam Exp $
88c4d2f6 5 * $DragonFly: src/sys/kern/Attic/kern_random.c,v 1.6 2004/01/30 05:42:17 dillon Exp $
984263bc
MD
6 *
7 * Version 0.95, last modified 18-Oct-95
8 *
9 * Copyright Theodore Ts'o, 1994, 1995. All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
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
22 * written permission.
23 *
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.)
29 *
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.
41 */
42
43#include <sys/param.h>
44#include <sys/kernel.h>
45#include <sys/md5.h>
46#include <sys/poll.h>
47#include <sys/random.h>
48#include <sys/select.h>
49#include <sys/systm.h>
88c4d2f6 50#include <sys/systimer.h>
984263bc
MD
51
52#ifdef __i386__
53#include <i386/isa/icu.h>
54#endif
55#ifdef __alpha__
56/*
57 XXX the below should be used. However there is too much "16"
58 hardcodeing in kern_random.c right now. -- obrien
59#include <machine/ipl.h>
60#if NHWI > 0
61#define ICU_LEN (NHWI)
62#else
63#define ICU_LEN (NSWI)
64#endif
65*/
66#define ICU_LEN 16
67#endif
68
69#define MAX_BLKDEV 4
70
71/*
72 * The pool is stirred with a primitive polynomial of degree 128
73 * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
74 * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
75 */
76#define POOLWORDS 128 /* Power of 2 - note that this is 32-bit words */
77#define POOLBITS (POOLWORDS*32)
78
79#if POOLWORDS == 128
80#define TAP1 99 /* The polynomial taps */
81#define TAP2 59
82#define TAP3 31
83#define TAP4 9
84#define TAP5 7
85#elif POOLWORDS == 64
86#define TAP1 62 /* The polynomial taps */
87#define TAP2 38
88#define TAP3 10
89#define TAP4 6
90#define TAP5 1
91#else
92#error No primitive polynomial available for chosen POOLWORDS
93#endif
94
95#define WRITEBUFFER 512 /* size in bytes */
96
97/* There is actually only one of these, globally. */
98struct random_bucket {
99 u_int add_ptr;
100 u_int entropy_count;
101 int input_rotate;
102 u_int32_t *pool;
103 struct selinfo rsel;
104};
105
106/* There is one of these per entropy source */
107struct timer_rand_state {
108 u_long last_time;
109 int last_delta;
110 int nbits;
111};
112
113static struct random_bucket random_state;
114static u_int32_t random_pool[POOLWORDS];
115static struct timer_rand_state keyboard_timer_state;
116static struct timer_rand_state extract_timer_state;
7e071e7a 117static struct timer_rand_state irq_timer_state[MAX_INTS];
984263bc
MD
118#ifdef notyet
119static struct timer_rand_state blkdev_timer_state[MAX_BLKDEV];
120#endif
121static struct wait_queue *random_wait;
122
984263bc
MD
123void
124rand_initialize(void)
125{
126 random_state.add_ptr = 0;
127 random_state.entropy_count = 0;
128 random_state.pool = random_pool;
129 random_wait = NULL;
130 random_state.rsel.si_flags = 0;
131 random_state.rsel.si_pid = 0;
132}
133
134/*
135 * This function adds an int into the entropy "pool". It does not
136 * update the entropy estimate. The caller must do this if appropriate.
137 *
138 * The pool is stirred with a primitive polynomial of degree 128
139 * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
140 * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
141 *
142 * We rotate the input word by a changing number of bits, to help
143 * assure that all bits in the entropy get toggled. Otherwise, if we
144 * consistently feed the entropy pool small numbers (like ticks and
145 * scancodes, for example), the upper bits of the entropy pool don't
146 * get affected. --- TYT, 10/11/95
147 */
148static __inline void
149add_entropy_word(struct random_bucket *r, const u_int32_t input)
150{
151 u_int i;
152 u_int32_t w;
153
154 w = (input << r->input_rotate) | (input >> (32 - r->input_rotate));
155 i = r->add_ptr = (r->add_ptr - 1) & (POOLWORDS-1);
156 if (i)
157 r->input_rotate = (r->input_rotate + 7) & 31;
158 else
159 /*
160 * At the beginning of the pool, add an extra 7 bits
161 * rotation, so that successive passes spread the
162 * input bits across the pool evenly.
163 */
164 r->input_rotate = (r->input_rotate + 14) & 31;
165
166 /* XOR in the various taps */
167 w ^= r->pool[(i+TAP1)&(POOLWORDS-1)];
168 w ^= r->pool[(i+TAP2)&(POOLWORDS-1)];
169 w ^= r->pool[(i+TAP3)&(POOLWORDS-1)];
170 w ^= r->pool[(i+TAP4)&(POOLWORDS-1)];
171 w ^= r->pool[(i+TAP5)&(POOLWORDS-1)];
172 w ^= r->pool[i];
173 /* Rotate w left 1 bit (stolen from SHA) and store */
174 r->pool[i] = (w << 1) | (w >> 31);
175}
176
177/*
178 * This function adds entropy to the entropy "pool" by using timing
179 * delays. It uses the timer_rand_state structure to make an estimate
180 * of how any bits of entropy this call has added to the pool.
181 *
182 * The number "num" is also added to the pool - it should somehow describe
183 * the type of event which just happened. This is currently 0-255 for
184 * keyboard scan codes, and 256 upwards for interrupts.
185 * On the i386, this is assumed to be at most 16 bits, and the high bits
186 * are used for a high-resolution timer.
187 */
188static void
189add_timer_randomness(struct random_bucket *r, struct timer_rand_state *state,
190 u_int num)
191{
192 int delta, delta2;
193 u_int nbits;
194 u_int32_t time;
984263bc 195
88c4d2f6 196 num ^= cputimer_count() << 16;
984263bc
MD
197 r->entropy_count += 2;
198
199 time = ticks;
200
201 add_entropy_word(r, (u_int32_t) num);
202 add_entropy_word(r, time);
203
204 /*
205 * Calculate number of bits of randomness we probably
206 * added. We take into account the first and second order
207 * deltas in order to make our estimate.
208 */
209 delta = time - state->last_time;
210 state->last_time = time;
211
212 delta2 = delta - state->last_delta;
213 state->last_delta = delta;
214
215 if (delta < 0) delta = -delta;
216 if (delta2 < 0) delta2 = -delta2;
217 delta = MIN(delta, delta2) >> 1;
218 for (nbits = 0; delta; nbits++)
219 delta >>= 1;
220
221 r->entropy_count += nbits;
222
223 /* Prevent overflow */
224 if (r->entropy_count > POOLBITS)
225 r->entropy_count = POOLBITS;
226
227 if (r->entropy_count >= 8)
228 selwakeup(&random_state.rsel);
229}
230
231void
232add_keyboard_randomness(u_char scancode)
233{
234 add_timer_randomness(&random_state, &keyboard_timer_state, scancode);
235}
236
237void
7e071e7a 238add_interrupt_randomness(int intr)
984263bc 239{
984263bc
MD
240 add_timer_randomness(&random_state, &irq_timer_state[intr], intr);
241}
242
243#ifdef notused
244void
245add_blkdev_randomness(int major)
246{
247 if (major >= MAX_BLKDEV)
248 return;
249
250 add_timer_randomness(&random_state, &blkdev_timer_state[major],
251 0x200+major);
252}
253#endif /* notused */
254
255#if POOLWORDS % 16
256#error extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
257#endif
258/*
259 * This function extracts randomness from the "entropy pool", and
260 * returns it in a buffer. This function computes how many remaining
261 * bits of entropy are left in the pool, but it does not restrict the
262 * number of bytes that are actually obtained.
263 */
264static __inline int
265extract_entropy(struct random_bucket *r, char *buf, int nbytes)
266{
267 int ret, i;
268 u_int32_t tmp[4];
269
270 add_timer_randomness(r, &extract_timer_state, nbytes);
271
272 /* Redundant, but just in case... */
273 if (r->entropy_count > POOLBITS)
274 r->entropy_count = POOLBITS;
275 /* Why is this here? Left in from Ted Ts'o. Perhaps to limit time. */
276 if (nbytes > 32768)
277 nbytes = 32768;
278
279 ret = nbytes;
280 if (r->entropy_count / 8 >= nbytes)
281 r->entropy_count -= nbytes*8;
282 else
283 r->entropy_count = 0;
284
285 while (nbytes) {
286 /* Hash the pool to get the output */
287 tmp[0] = 0x67452301;
288 tmp[1] = 0xefcdab89;
289 tmp[2] = 0x98badcfe;
290 tmp[3] = 0x10325476;
291 for (i = 0; i < POOLWORDS; i += 16)
292 MD5Transform(tmp, (char *)(r->pool+i));
293 /* Modify pool so next hash will produce different results */
294 add_entropy_word(r, tmp[0]);
295 add_entropy_word(r, tmp[1]);
296 add_entropy_word(r, tmp[2]);
297 add_entropy_word(r, tmp[3]);
298 /*
299 * Run the MD5 Transform one more time, since we want
300 * to add at least minimal obscuring of the inputs to
301 * add_entropy_word(). --- TYT
302 */
303 MD5Transform(tmp, (char *)(r->pool));
304
305 /* Copy data to destination buffer */
306 i = MIN(nbytes, 16);
307 bcopy(tmp, buf, i);
308 nbytes -= i;
309 buf += i;
310 }
311
312 /* Wipe data from memory */
313 bzero(tmp, sizeof(tmp));
314
315 return ret;
316}
317
318#ifdef notused /* XXX NOT the exported kernel interface */
319/*
320 * This function is the exported kernel interface. It returns some
321 * number of good random numbers, suitable for seeding TCP sequence
322 * numbers, etc.
323 */
324void
325get_random_bytes(void *buf, u_int nbytes)
326{
327 extract_entropy(&random_state, (char *) buf, nbytes);
328}
329#endif /* notused */
330
331u_int
332read_random(void *buf, u_int nbytes)
333{
334 if ((nbytes * 8) > random_state.entropy_count)
335 nbytes = random_state.entropy_count / 8;
336
337 return extract_entropy(&random_state, (char *)buf, nbytes);
338}
339
340u_int
341read_random_unlimited(void *buf, u_int nbytes)
342{
343 return extract_entropy(&random_state, (char *)buf, nbytes);
344}
345
346#ifdef notused
347u_int
348write_random(const char *buf, u_int nbytes)
349{
350 u_int i;
351 u_int32_t word, *p;
352
353 for (i = nbytes, p = (u_int32_t *)buf;
354 i >= sizeof(u_int32_t);
355 i-= sizeof(u_int32_t), p++)
356 add_entropy_word(&random_state, *p);
357 if (i) {
358 word = 0;
359 bcopy(p, &word, i);
360 add_entropy_word(&random_state, word);
361 }
362 return nbytes;
363}
364#endif /* notused */
365
366void
367add_true_randomness(int val)
368{
369 add_entropy_word(&random_state, val);
370 random_state.entropy_count += 8*sizeof (val);
371 if (random_state.entropy_count > POOLBITS)
372 random_state.entropy_count = POOLBITS;
373 selwakeup(&random_state.rsel);
374}
375
376int
41c20dac 377random_poll(dev_t dev, int events, struct thread *td)
984263bc
MD
378{
379 int s;
380 int revents = 0;
381
382 s = splhigh();
383 if (events & (POLLIN | POLLRDNORM)) {
384 if (random_state.entropy_count >= 8)
385 revents |= events & (POLLIN | POLLRDNORM);
386 else
41c20dac 387 selrecord(td, &random_state.rsel);
984263bc
MD
388 }
389 splx(s);
390 if (events & (POLLOUT | POLLWRNORM))
391 revents |= events & (POLLOUT | POLLWRNORM); /* heh */
392
393 return (revents);
394}
395