sys/kern/kern_random.c

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