7aa59c2fcb8d33bc9ded3008beffba3980befc85
[dragonfly.git] / sys / kern / kern_random.c
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 $
5  * $DragonFly: src/sys/kern/Attic/kern_random.c,v 1.6 2004/01/30 05:42:17 dillon Exp $
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>
50 #include <sys/systimer.h>
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. */
98 struct 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 */
107 struct timer_rand_state {
108         u_long  last_time;
109         int     last_delta;
110         int     nbits;
111 };
112
113 static struct random_bucket random_state;
114 static u_int32_t random_pool[POOLWORDS];
115 static struct timer_rand_state keyboard_timer_state;
116 static struct timer_rand_state extract_timer_state;
117 static struct timer_rand_state irq_timer_state[MAX_INTS];
118 #ifdef notyet
119 static struct timer_rand_state blkdev_timer_state[MAX_BLKDEV];
120 #endif
121 static struct wait_queue *random_wait;
122
123 void
124 rand_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  */
148 static __inline void
149 add_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  */
188 static void
189 add_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;
195
196         num ^= cputimer_count() << 16;
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
231 void
232 add_keyboard_randomness(u_char scancode)
233 {
234         add_timer_randomness(&random_state, &keyboard_timer_state, scancode);
235 }
236
237 void
238 add_interrupt_randomness(int intr)
239 {
240         add_timer_randomness(&random_state, &irq_timer_state[intr], intr);
241 }
242
243 #ifdef notused
244 void
245 add_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  */
264 static __inline int
265 extract_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  */
324 void
325 get_random_bytes(void *buf, u_int nbytes)
326 {
327         extract_entropy(&random_state, (char *) buf, nbytes);
328 }
329 #endif /* notused */
330
331 u_int
332 read_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
340 u_int
341 read_random_unlimited(void *buf, u_int nbytes)
342 {
343         return extract_entropy(&random_state, (char *)buf, nbytes);
344 }
345
346 #ifdef notused
347 u_int
348 write_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
366 void
367 add_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
376 int
377 random_poll(dev_t dev, int events, struct thread *td)
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
387                         selrecord(td, &random_state.rsel);
388         }
389         splx(s);
390         if (events & (POLLOUT | POLLWRNORM))
391                 revents |= events & (POLLOUT | POLLWRNORM);     /* heh */
392
393         return (revents);
394 }
395