| 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 | |