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