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.14 2006/04/12 18:28:30 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 #include <sys/thread2.h>
  52 #include <sys/lock.h>
  53 #include <machine/clock.h>
  54
  55 #ifdef __i386__
  56 #include <i386/icu/icu.h>
  57 #endif
  58
  59 #define MAX_BLKDEV 4
  60
  61 /*
  62  * The pool is stirred with a primitive polynomial of degree 128
  63  * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
  64  * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
  65  */
  66 #define POOLWORDS 128    /* Power of 2 - note that this is 32-bit words */
  67 #define POOLBITS (POOLWORDS*32)
  68
  69 #if POOLWORDS == 128
  70 #define TAP1    99     /* The polynomial taps */
  71 #define TAP2    59
  72 #define TAP3    31
  73 #define TAP4    9
  74 #define TAP5    7
  75 #elif POOLWORDS == 64
  76 #define TAP1    62      /* The polynomial taps */
  77 #define TAP2    38
  78 #define TAP3    10
  79 #define TAP4    6
  80 #define TAP5    1
  81 #else
  82 #error No primitive polynomial available for chosen POOLWORDS
  83 #endif
  84
  85 #define WRITEBUFFER     512 /* size in bytes */
  86
  87 /*
  88  * This is the number of bits represented by entropy_count.  A value of
  89  * 8 would represent an ultra-conservative value, while a value of 2
  90  * would be ultra-liberal.  Use a value of 4.
  91  */
  92 #define STATE_BITS      4
  93 #define MIN_BITS        (STATE_BITS*4)
  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 random_bucket urandom_state;
 114 static u_int32_t urandom_pool[POOLWORDS];
 115 static struct timer_rand_state keyboard_timer_state;
 116 static struct timer_rand_state keyboard_utimer_state;
 117 static struct timer_rand_state extract_timer_state;
 118 static struct timer_rand_state irq_timer_state[MAX_INTS];
 119 static struct timer_rand_state irq_utimer_state[MAX_INTS];
 120 #ifdef notyet
 121 static struct timer_rand_state blkdev_timer_state[MAX_BLKDEV];
 122 #endif
 123 static thread_t rand_td;
 124 static int      rand_td_slot;
 125
 126 static void add_timer_randomness(struct random_bucket *r,
 127                                  struct timer_rand_state *state, u_int num);
 128
 129 /*
 130  * Called from early boot
 131  */
 132 void
 133 rand_initialize(void)
 134 {
 135         random_state.pool = random_pool;
 136         urandom_state.pool = urandom_pool;
 137 }
 138
 139 /*
 140  * Random number generator helper thread.
 141  *
 142  * Note that rand_td_slot is initially 0, which means nothing will try
 143  * to schedule our thread until we reset it to -1.  This also prevents
 144  * any attempt to schedule the thread before it has been initialized.
 145  */
 146 static
 147 void
 148 rand_thread_loop(void *dummy)
 149 {
 150         int slot;
 151         int count;
 152
 153         for (;;) {
 154                 if ((slot = rand_td_slot) >= 0) {
 155                         add_timer_randomness(&urandom_state,
 156                                              &irq_timer_state[slot],
 157                                              slot);
 158                         add_timer_randomness(&random_state,
 159                                              &irq_utimer_state[slot],
 160                                              slot);
 161                 }
 162
 163                 /*
 164                  * The fewer bits we have, the shorter we sleep, up to a
 165                  * point.  We use an interrupt to trigger the thread once
 166                  * we have slept the calculated amount of time.  This limits
 167                  * the wakeup rate AND gives us a good interrupt-based
 168                  * timer value at the same time.
 169                  *
 170                  * Use /dev/random's entropy count rather than /dev/urandom's.
 171                  * Things like the stacksmash code use /dev/urandom on program
 172                  * exec all the time, and it is not likely to ever have
 173                  * good entropy.
 174                  */
 175                 count = random_state.entropy_count * hz / POOLBITS;
 176                 if (count < hz / 25)
 177                         count = hz / 25;
 178                 if (count > hz)
 179                         count = hz;
 180                 tsleep(rand_td, 0, "rwait", count);
 181                 lwkt_deschedule_self(rand_td);
 182                 rand_td_slot = -1;
 183                 lwkt_switch();
 184         }
 185 }
 186
 187 static
 188 void
 189 rand_thread_init(void)
 190 {
 191         lwkt_create(rand_thread_loop, NULL, &rand_td, NULL, 0, 0, "random");
 192 }
 193
 194 SYSINIT(rand, SI_SUB_HELPER_THREADS, SI_ORDER_ANY, rand_thread_init, 0);
 195
 196 /*
 197  * This function adds an int into the entropy "pool".  It does not
 198  * update the entropy estimate.  The caller must do this if appropriate.
 199  *
 200  * The pool is stirred with a primitive polynomial of degree 128
 201  * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
 202  * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
 203  *
 204  * We rotate the input word by a changing number of bits, to help
 205  * assure that all bits in the entropy get toggled.  Otherwise, if we
 206  * consistently feed the entropy pool small numbers (like ticks and
 207  * scancodes, for example), the upper bits of the entropy pool don't
 208  * get affected. --- TYT, 10/11/95
 209  */
 210 static __inline void
 211 add_entropy_word(struct random_bucket *r, const u_int32_t input)
 212 {
 213         u_int i;
 214         u_int32_t w;
 215
 216         w = (input << r->input_rotate) | (input >> (32 - r->input_rotate));
 217         i = r->add_ptr = (r->add_ptr - 1) & (POOLWORDS-1);
 218         if (i)
 219                 r->input_rotate = (r->input_rotate + 7) & 31;
 220         else
 221                 /*
 222                  * At the beginning of the pool, add an extra 7 bits
 223                  * rotation, so that successive passes spread the
 224                  * input bits across the pool evenly.
 225                  */
 226                 r->input_rotate = (r->input_rotate + 14) & 31;
 227
 228         /* XOR in the various taps */
 229         w ^= r->pool[(i+TAP1)&(POOLWORDS-1)];
 230         w ^= r->pool[(i+TAP2)&(POOLWORDS-1)];
 231         w ^= r->pool[(i+TAP3)&(POOLWORDS-1)];
 232         w ^= r->pool[(i+TAP4)&(POOLWORDS-1)];
 233         w ^= r->pool[(i+TAP5)&(POOLWORDS-1)];
 234         w ^= r->pool[i];
 235         /* Rotate w left 1 bit (stolen from SHA) and store */
 236         r->pool[i] = (w << 1) | (w >> 31);
 237 }
 238
 239 /*
 240  * This function adds entropy to the entropy "pool" by using timing
 241  * delays.  It uses the timer_rand_state structure to make an estimate
 242  * of how  any bits of entropy this call has added to the pool.
 243  *
 244  * The number "num" is also added to the pool - it should somehow describe
 245  * the type of event which just happened.  This is currently 0-255 for
 246  * keyboard scan codes, and 256 upwards for interrupts.
 247  * On the i386, this is assumed to be at most 16 bits, and the high bits
 248  * are used for a high-resolution timer.
 249  */
 250 static void
 251 add_timer_randomness(struct random_bucket *r, struct timer_rand_state *state,
 252                      u_int num)
 253 {
 254         int             delta, delta2;
 255         u_int           nbits;
 256         u_int32_t       time;
 257         int             count;
 258
 259         num ^= sys_cputimer->count() << 16;
 260         if (tsc_present)
 261                 num ^= ~(u_int)rdtsc();
 262         count = r->entropy_count + 2;
 263         if (count > POOLBITS)
 264                 count = POOLBITS;
 265         r->entropy_count = count;
 266
 267         time = ticks;
 268
 269         add_entropy_word(r, (u_int32_t) num);
 270         add_entropy_word(r, time);
 271
 272         /*
 273          * Calculate number of bits of randomness we probably
 274          * added.  We take into account the first and second order
 275          * deltas in order to make our estimate.
 276          */
 277         delta = time - state->last_time;
 278         state->last_time = time;
 279
 280         delta2 = delta - state->last_delta;
 281         state->last_delta = delta;
 282
 283         if (delta < 0) delta = -delta;
 284         if (delta2 < 0) delta2 = -delta2;
 285         delta = MIN(delta, delta2) >> 1;
 286         for (nbits = 0; delta; nbits++)
 287                 delta >>= 1;
 288
 289         /* Prevent overflow */
 290         count = r->entropy_count + nbits;
 291         if (count > POOLBITS)
 292                 count = POOLBITS;
 293         cpu_sfence();
 294         r->entropy_count = count;
 295
 296         if (count >= MIN_BITS && try_mplock()) {
 297                 selwakeup(&r->rsel);
 298                 rel_mplock();
 299         }
 300 }
 301
 302 void
 303 add_keyboard_randomness(u_char scancode)
 304 {
 305         add_timer_randomness(&random_state, &keyboard_timer_state, scancode);
 306         add_timer_randomness(&urandom_state, &keyboard_utimer_state, scancode);
 307 }
 308
 309 /*
 310  * This routine is called from an interrupt and must be very efficient.
 311  */
 312 void
 313 add_interrupt_randomness(int intr)
 314 {
 315         if (rand_td_slot < 0) {
 316                 rand_td_slot = intr;
 317                 lwkt_schedule(rand_td);
 318         }
 319 }
 320
 321 #ifdef notused
 322 void
 323 add_blkdev_randomness(int major)
 324 {
 325         if (major >= MAX_BLKDEV)
 326                 return;
 327
 328         add_timer_randomness(&random_state, &blkdev_timer_state[major],
 329                              0x200+major);
 330 }
 331 #endif /* notused */
 332
 333 #if POOLWORDS % 16
 334 #error extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
 335 #endif
 336 /*
 337  * This function extracts randomness from the "entropy pool", and
 338  * returns it in a buffer.  This function computes how many remaining
 339  * bits of entropy are left in the pool, but it does not restrict the
 340  * number of bytes that are actually obtained.
 341  */
 342 static __inline int
 343 extract_entropy(struct random_bucket *r, char *buf, int nbytes)
 344 {
 345         int ret, i;
 346         u_int32_t tmp[4];
 347
 348         add_timer_randomness(r, &extract_timer_state, nbytes);
 349
 350         /* Redundant, but just in case... */
 351         if (r->entropy_count > POOLBITS)
 352                 r->entropy_count = POOLBITS;
 353         /* Why is this here?  Left in from Ted Ts'o.  Perhaps to limit time. */
 354         if (nbytes > 32768)
 355                 nbytes = 32768;
 356
 357         ret = nbytes;
 358         if (r->entropy_count > nbytes * STATE_BITS)
 359                 r->entropy_count -= nbytes * STATE_BITS;
 360         else
 361                 r->entropy_count = 0;
 362
 363         while (nbytes) {
 364                 /* Hash the pool to get the output */
 365                 tmp[0] = 0x67452301;
 366                 tmp[1] = 0xefcdab89;
 367                 tmp[2] = 0x98badcfe;
 368                 tmp[3] = 0x10325476;
 369                 for (i = 0; i < POOLWORDS; i += 16)
 370                         MD5Transform(tmp, (char *)(r->pool+i));
 371                 /* Modify pool so next hash will produce different results */
 372                 add_entropy_word(r, tmp[0]);
 373                 add_entropy_word(r, tmp[1]);
 374                 add_entropy_word(r, tmp[2]);
 375                 add_entropy_word(r, tmp[3]);
 376                 /*
 377                  * Run the MD5 Transform one more time, since we want
 378                  * to add at least minimal obscuring of the inputs to
 379                  * add_entropy_word().  --- TYT
 380                  */
 381                 MD5Transform(tmp, (char *)(r->pool));
 382
 383                 /* Copy data to destination buffer */
 384                 i = MIN(nbytes, 16);
 385                 bcopy(tmp, buf, i);
 386                 nbytes -= i;
 387                 buf += i;
 388         }
 389
 390         /* Wipe data from memory */
 391         bzero(tmp, sizeof(tmp));
 392
 393         return ret;
 394 }
 395
 396 #ifdef notused /* XXX NOT the exported kernel interface */
 397 /*
 398  * This function is the exported kernel interface.  It returns some
 399  * number of good random numbers, suitable for seeding TCP sequence
 400  * numbers, etc.
 401  */
 402 void
 403 get_random_bytes(void *buf, u_int nbytes)
 404 {
 405         extract_entropy(&random_state, (char *) buf, nbytes);
 406 }
 407 #endif /* notused */
 408
 409 u_int
 410 read_random(void *buf, u_int nbytes)
 411 {
 412         if (random_state.entropy_count < MIN_BITS)
 413                 return 0;
 414         if ((nbytes * STATE_BITS) > random_state.entropy_count)
 415                 nbytes = random_state.entropy_count / STATE_BITS;
 416
 417         return extract_entropy(&random_state, (char *)buf, nbytes);
 418 }
 419
 420 u_int
 421 read_random_unlimited(void *buf, u_int nbytes)
 422 {
 423         return extract_entropy(&urandom_state, (char *)buf, nbytes);
 424 }
 425
 426 #ifdef notused
 427 u_int
 428 write_random(const char *buf, u_int nbytes)
 429 {
 430         u_int i;
 431         u_int32_t word, *p;
 432
 433         for (i = nbytes, p = (u_int32_t *)buf;
 434              i >= sizeof(u_int32_t);
 435              i-= sizeof(u_int32_t), p++)
 436                 add_entropy_word(&random_state, *p);
 437         if (i) {
 438                 word = 0;
 439                 bcopy(p, &word, i);
 440                 add_entropy_word(&random_state, word);
 441         }
 442         return nbytes;
 443 }
 444 #endif /* notused */
 445
 446 void
 447 add_true_randomness(int val)
 448 {
 449         int count;
 450
 451         add_entropy_word(&random_state, val);
 452         count = random_state.entropy_count + 8 *sizeof(val);
 453         if (count > POOLBITS)
 454                 count = POOLBITS;
 455         random_state.entropy_count = count;
 456         selwakeup(&random_state.rsel);
 457 }
 458
 459 /*
 460  * Returns whether /dev/random has data or not.  entropy_count must be
 461  * at least STATE_BITS.
 462  */
 463 int
 464 random_poll(dev_t dev, int events, struct thread *td)
 465 {
 466         int revents = 0;
 467
 468         crit_enter();
 469         if (events & (POLLIN | POLLRDNORM)) {
 470                 if (random_state.entropy_count >= MIN_BITS)
 471                         revents |= events & (POLLIN | POLLRDNORM);
 472                 else
 473                         selrecord(td, &random_state.rsel);
 474         }
 475         crit_exit();
 476         if (events & (POLLOUT | POLLWRNORM))
 477                 revents |= events & (POLLOUT | POLLWRNORM);     /* heh */
 478
 479         return (revents);
 480 }
 481