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