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