contrib/bind-9.2.4rc7/lib/isc/entropy.c

   1 /*
   2  * Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 2000, 2001, 2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: entropy.c,v 1.3.2.4 2004/03/09 06:11:45 marka Exp $ */
  19
  20 /*
  21  * This is the system independent part of the entropy module.  It is
  22  * compiled via inclusion from the relevant OS source file, ie,
  23  * unix/entropy.c or win32/entropy.c.
  24  */
  25
  26 #include <errno.h>
  27 #include <fcntl.h>
  28 #include <stdio.h>
  29
  30 #include <isc/buffer.h>
  31 #include <isc/entropy.h>
  32 #include <isc/keyboard.h>
  33 #include <isc/list.h>
  34 #include <isc/magic.h>
  35 #include <isc/mem.h>
  36 #include <isc/msgs.h>
  37 #include <isc/mutex.h>
  38 #include <isc/platform.h>
  39 #include <isc/region.h>
  40 #include <isc/sha1.h>
  41 #include <isc/string.h>
  42 #include <isc/time.h>
  43 #include <isc/util.h>
  44
  45 /*
  46  * Much of this code is modeled after the NetBSD /dev/random implementation,
  47  * written by Michael Graff <explorer@netbsd.org>.
  48  */
  49
  50 #define ENTROPY_MAGIC           ISC_MAGIC('E', 'n', 't', 'e')
  51 #define SOURCE_MAGIC            ISC_MAGIC('E', 'n', 't', 's')
  52
  53 #define VALID_ENTROPY(e)        ISC_MAGIC_VALID(e, ENTROPY_MAGIC)
  54 #define VALID_SOURCE(s)         ISC_MAGIC_VALID(s, SOURCE_MAGIC)
  55
  56 /***
  57  *** "constants."  Do not change these unless you _really_ know what
  58  *** you are doing.
  59  ***/
  60
  61 /*
  62  * size of entropy pool in 32-bit words.  This _MUST_ be a power of 2.
  63  */
  64 #define RND_POOLWORDS   128
  65 #define RND_POOLBYTES   (RND_POOLWORDS * 4)
  66 #define RND_POOLBITS    (RND_POOLWORDS * 32)
  67
  68 /*
  69  * Number of bytes returned per hash.  This must be true:
  70  *      threshold * 2 <= digest_size_in_bytes
  71  */
  72 #define RND_ENTROPY_THRESHOLD   10
  73 #define THRESHOLD_BITS          (RND_ENTROPY_THRESHOLD * 8)
  74
  75 /*
  76  * Size of the input event queue in samples.
  77  */
  78 #define RND_EVENTQSIZE  32
  79
  80 /*
  81  * The number of times we'll "reseed" for pseudorandom seeds.  This is an
  82  * extremely weak pseudorandom seed.  If the caller is using lots of
  83  * pseudorandom data and they cannot provide a stronger random source,
  84  * there is little we can do other than hope they're smart enough to
  85  * call _adddata() with something better than we can come up with.
  86  */
  87 #define RND_INITIALIZE  128
  88
  89 typedef struct {
  90         isc_uint32_t    cursor;         /* current add point in the pool */
  91         isc_uint32_t    entropy;        /* current entropy estimate in bits */
  92         isc_uint32_t    pseudo;         /* bits extracted in pseudorandom */
  93         isc_uint32_t    rotate;         /* how many bits to rotate by */
  94         isc_uint32_t    pool[RND_POOLWORDS];    /* random pool data */
  95 } isc_entropypool_t;
  96
  97 struct isc_entropy {
  98         unsigned int                    magic;
  99         isc_mem_t                      *mctx;
 100         isc_mutex_t                     lock;
 101         unsigned int                    refcnt;
 102         isc_uint32_t                    initialized;
 103         isc_uint32_t                    initcount;
 104         isc_entropypool_t               pool;
 105         unsigned int                    nsources;
 106         isc_entropysource_t            *nextsource;
 107         ISC_LIST(isc_entropysource_t)   sources;
 108 };
 109
 110 typedef struct {
 111         isc_uint32_t    last_time;      /* last time recorded */
 112         isc_uint32_t    last_delta;     /* last delta value */
 113         isc_uint32_t    last_delta2;    /* last delta2 value */
 114         isc_uint32_t    nsamples;       /* number of samples filled in */
 115         isc_uint32_t   *samples;        /* the samples */
 116         isc_uint32_t   *extra;          /* extra samples added in */
 117 } sample_queue_t;
 118
 119 typedef struct {
 120         sample_queue_t  samplequeue;
 121 } isc_entropysamplesource_t;
 122
 123 typedef struct {
 124         isc_boolean_t           start_called;
 125         isc_entropystart_t      startfunc;
 126         isc_entropyget_t        getfunc;
 127         isc_entropystop_t       stopfunc;
 128         void                   *arg;
 129         sample_queue_t          samplequeue;
 130 } isc_cbsource_t;
 131
 132 typedef struct {
 133         FILESOURCE_HANDLE_TYPE handle;
 134 } isc_entropyfilesource_t;
 135
 136 struct isc_entropysource {
 137         unsigned int    magic;
 138         unsigned int    type;
 139         isc_entropy_t  *ent;
 140         isc_uint32_t    total;          /* entropy from this source */
 141         ISC_LINK(isc_entropysource_t)   link;
 142         char            name[32];
 143         isc_boolean_t   bad;
 144         isc_boolean_t   warn_keyboard;
 145         isc_keyboard_t  kbd;
 146         union {
 147                 isc_entropysamplesource_t       sample;
 148                 isc_entropyfilesource_t         file;
 149                 isc_cbsource_t                  callback;
 150         } sources;
 151 };
 152
 153 #define ENTROPY_SOURCETYPE_SAMPLE       1       /* Type is a sample source */
 154 #define ENTROPY_SOURCETYPE_FILE         2       /* Type is a file source */
 155 #define ENTROPY_SOURCETYPE_CALLBACK     3       /* Type is a callback source */
 156
 157 /*
 158  * The random pool "taps"
 159  */
 160 #define TAP1    99
 161 #define TAP2    59
 162 #define TAP3    31
 163 #define TAP4     9
 164 #define TAP5     7
 165
 166 /*
 167  * Declarations for function provided by the system dependent sources that
 168  * include this file.
 169  */
 170 static void
 171 fillpool(isc_entropy_t *, unsigned int, isc_boolean_t);
 172
 173 static int
 174 wait_for_sources(isc_entropy_t *);
 175
 176 static void
 177 destroyfilesource(isc_entropyfilesource_t *source);
 178
 179
 180 static void
 181 samplequeue_release(isc_entropy_t *ent, sample_queue_t *sq) {
 182         REQUIRE(sq->samples != NULL);
 183         REQUIRE(sq->extra != NULL);
 184
 185         isc_mem_put(ent->mctx, sq->samples, RND_EVENTQSIZE * 4);
 186         isc_mem_put(ent->mctx, sq->extra, RND_EVENTQSIZE * 4);
 187         sq->samples = NULL;
 188         sq->extra = NULL;
 189 }
 190
 191 static isc_result_t
 192 samplesource_allocate(isc_entropy_t *ent, sample_queue_t *sq) {
 193         sq->samples = isc_mem_get(ent->mctx, RND_EVENTQSIZE * 4);
 194         if (sq->samples == NULL)
 195                 return (ISC_R_NOMEMORY);
 196
 197         sq->extra = isc_mem_get(ent->mctx, RND_EVENTQSIZE * 4);
 198         if (sq->extra == NULL) {
 199                 isc_mem_put(ent->mctx, sq->samples, RND_EVENTQSIZE * 4);
 200                 sq->samples = NULL;
 201                 return (ISC_R_NOMEMORY);
 202         }
 203
 204         sq->nsamples = 0;
 205
 206         return (ISC_R_SUCCESS);
 207 }
 208
 209 /*
 210  * Add in entropy, even when the value we're adding in could be
 211  * very large.
 212  */
 213 static inline void
 214 add_entropy(isc_entropy_t *ent, isc_uint32_t entropy) {
 215         /* clamp input.  Yes, this must be done. */
 216         entropy = ISC_MIN(entropy, RND_POOLBITS);
 217         /* Add in the entropy we already have. */
 218         entropy += ent->pool.entropy;
 219         /* Clamp. */
 220         ent->pool.entropy = ISC_MIN(entropy, RND_POOLBITS);
 221 }
 222
 223 /*
 224  * Decrement the amount of entropy the pool has.
 225  */
 226 static inline void
 227 subtract_entropy(isc_entropy_t *ent, isc_uint32_t entropy) {
 228         entropy = ISC_MIN(entropy, ent->pool.entropy);
 229         ent->pool.entropy -= entropy;
 230 }
 231
 232 /*
 233  * Add in entropy, even when the value we're adding in could be
 234  * very large.
 235  */
 236 static inline void
 237 add_pseudo(isc_entropy_t *ent, isc_uint32_t pseudo) {
 238         /* clamp input.  Yes, this must be done. */
 239         pseudo = ISC_MIN(pseudo, RND_POOLBITS * 8);
 240         /* Add in the pseudo we already have. */
 241         pseudo += ent->pool.pseudo;
 242         /* Clamp. */
 243         ent->pool.pseudo = ISC_MIN(pseudo, RND_POOLBITS * 8);
 244 }
 245
 246 /*
 247  * Decrement the amount of pseudo the pool has.
 248  */
 249 static inline void
 250 subtract_pseudo(isc_entropy_t *ent, isc_uint32_t pseudo) {
 251         pseudo = ISC_MIN(pseudo, ent->pool.pseudo);
 252         ent->pool.pseudo -= pseudo;
 253 }
 254
 255 /*
 256  * Add one word to the pool, rotating the input as needed.
 257  */
 258 static inline void
 259 entropypool_add_word(isc_entropypool_t *rp, isc_uint32_t val) {
 260         /*
 261          * Steal some values out of the pool, and xor them into the
 262          * word we were given.
 263          *
 264          * Mix the new value into the pool using xor.  This will
 265          * prevent the actual values from being known to the caller
 266          * since the previous values are assumed to be unknown as well.
 267          */
 268         val ^= rp->pool[(rp->cursor + TAP1) & (RND_POOLWORDS - 1)];
 269         val ^= rp->pool[(rp->cursor + TAP2) & (RND_POOLWORDS - 1)];
 270         val ^= rp->pool[(rp->cursor + TAP3) & (RND_POOLWORDS - 1)];
 271         val ^= rp->pool[(rp->cursor + TAP4) & (RND_POOLWORDS - 1)];
 272         val ^= rp->pool[(rp->cursor + TAP5) & (RND_POOLWORDS - 1)];
 273         rp->pool[rp->cursor++] ^=
 274           ((val << rp->rotate) | (val >> (32 - rp->rotate)));
 275
 276         /*
 277          * If we have looped around the pool, increment the rotate
 278          * variable so the next value will get xored in rotated to
 279          * a different position.
 280          * Increment by a value that is relativly prime to the word size
 281          * to try to spread the bits throughout the pool quickly when the
 282          * pool is empty.
 283          */
 284         if (rp->cursor == RND_POOLWORDS) {
 285                 rp->cursor = 0;
 286                 rp->rotate = (rp->rotate + 7) & 31;
 287         }
 288 }
 289
 290 /*
 291  * Add a buffer's worth of data to the pool.
 292  *
 293  * Requires that the lock is held on the entropy pool.
 294  */
 295 static void
 296 entropypool_adddata(isc_entropy_t *ent, void *p, unsigned int len,
 297                     isc_uint32_t entropy)
 298 {
 299         isc_uint32_t val;
 300         unsigned long addr;
 301         isc_uint8_t *buf;
 302
 303         addr = (unsigned long)p;
 304         buf = p;
 305
 306         if ((addr & 0x03U) != 0U) {
 307                 val = 0;
 308                 switch (len) {
 309                 case 3:
 310                         val = *buf++;
 311                         len--;
 312                 case 2:
 313                         val = val << 8 | *buf++;
 314                         len--;
 315                 case 1:
 316                         val = val << 8 | *buf++;
 317                         len--;
 318                 }
 319
 320                 entropypool_add_word(&ent->pool, val);
 321         }
 322
 323         for (; len > 3 ; len -= 4) {
 324                 val = *((isc_uint32_t *)buf);
 325
 326                 entropypool_add_word(&ent->pool, val);
 327                 buf += 4;
 328         }
 329
 330         if (len != 0) {
 331                 val = 0;
 332                 switch (len) {
 333                 case 3:
 334                         val = *buf++;
 335                 case 2:
 336                         val = val << 8 | *buf++;
 337                 case 1:
 338                         val = val << 8 | *buf++;
 339                 }
 340
 341                 entropypool_add_word(&ent->pool, val);
 342         }
 343
 344         add_entropy(ent, entropy);
 345         subtract_pseudo(ent, entropy);
 346 }
 347
 348 static inline void
 349 reseed(isc_entropy_t *ent) {
 350         isc_result_t result;
 351         isc_time_t t;
 352         pid_t pid;
 353
 354         if (ent->initcount == 0) {
 355                 pid = getpid();
 356                 entropypool_adddata(ent, &pid, sizeof pid, 0);
 357                 pid = getppid();
 358                 entropypool_adddata(ent, &pid, sizeof pid, 0);
 359         }
 360
 361         /*
 362          * After we've reseeded 100 times, only add new timing info every
 363          * 50 requests.  This will keep us from using lots and lots of
 364          * CPU just to return bad pseudorandom data anyway.
 365          */
 366         if (ent->initcount > 100)
 367                 if ((ent->initcount % 50) != 0)
 368                         return;
 369
 370         result = isc_time_now(&t);
 371         if (result == ISC_R_SUCCESS) {
 372                 entropypool_adddata(ent, &t, sizeof t, 0);
 373                 ent->initcount++;
 374         }
 375 }
 376
 377 static inline unsigned int
 378 estimate_entropy(sample_queue_t *sq, isc_uint32_t t) {
 379         isc_int32_t             delta;
 380         isc_int32_t             delta2;
 381         isc_int32_t             delta3;
 382
 383         /*
 384          * If the time counter has overflowed, calculate the real difference.
 385          * If it has not, it is simplier.
 386          */
 387         if (t < sq->last_time)
 388                 delta = UINT_MAX - sq->last_time + t;
 389         else
 390                 delta = sq->last_time - t;
 391
 392         if (delta < 0)
 393                 delta = -delta;
 394
 395         /*
 396          * Calculate the second and third order differentials
 397          */
 398         delta2 = sq->last_delta - delta;
 399         if (delta2 < 0)
 400                 delta2 = -delta2;
 401
 402         delta3 = sq->last_delta2 - delta2;
 403         if (delta3 < 0)
 404                 delta3 = -delta3;
 405
 406         sq->last_time = t;
 407         sq->last_delta = delta;
 408         sq->last_delta2 = delta2;
 409
 410         /*
 411          * If any delta is 0, we got no entropy.  If all are non-zero, we
 412          * might have something.
 413          */
 414         if (delta == 0 || delta2 == 0 || delta3 == 0)
 415                 return 0;
 416
 417         /*
 418          * We could find the smallest delta and claim we got log2(delta)
 419          * bits, but for now return that we found 1 bit.
 420          */
 421         return 1;
 422 }
 423
 424 static unsigned int
 425 crunchsamples(isc_entropy_t *ent, sample_queue_t *sq) {
 426         unsigned int ns;
 427         unsigned int added;
 428
 429         if (sq->nsamples < 6)
 430                 return (0);
 431
 432         added = 0;
 433         sq->last_time = sq->samples[0];
 434         sq->last_delta = 0;
 435         sq->last_delta2 = 0;
 436
 437         /*
 438          * Prime the values by adding in the first 4 samples in.  This
 439          * should completely initialize the delta calculations.
 440          */
 441         for (ns = 0 ; ns < 4 ; ns++)
 442                 (void)estimate_entropy(sq, sq->samples[ns]);
 443
 444         for (ns = 4 ; ns < sq->nsamples ; ns++)
 445                 added += estimate_entropy(sq, sq->samples[ns]);
 446
 447         entropypool_adddata(ent, sq->samples, sq->nsamples * 4, added);
 448         entropypool_adddata(ent, sq->extra, sq->nsamples * 4, 0);
 449
 450         /*
 451          * Move the last 4 samples into the first 4 positions, and start
 452          * adding new samples from that point.
 453          */
 454         for (ns = 0 ; ns < 4 ; ns++) {
 455                 sq->samples[ns] = sq->samples[sq->nsamples - 4 + ns];
 456                 sq->extra[ns] = sq->extra[sq->nsamples - 4 + ns];
 457         }
 458
 459         sq->nsamples = 4;
 460
 461         return (added);
 462 }
 463
 464 static unsigned int
 465 get_from_callback(isc_entropysource_t *source, unsigned int desired,
 466                   isc_boolean_t blocking)
 467 {
 468         isc_entropy_t *ent = source->ent;
 469         isc_cbsource_t *cbs = &source->sources.callback;
 470         unsigned int added;
 471         unsigned int got;
 472         isc_result_t result;
 473
 474         if (desired == 0)
 475                 return (0);
 476
 477         if (source->bad)
 478                 return (0);
 479
 480         if (!cbs->start_called && cbs->startfunc != NULL) {
 481                 result = cbs->startfunc(source, cbs->arg, blocking);
 482                 if (result != ISC_R_SUCCESS)
 483                         return (0);
 484                 cbs->start_called = ISC_TRUE;
 485         }
 486
 487         added = 0;
 488         result = ISC_R_SUCCESS;
 489         while (desired > 0 && result == ISC_R_SUCCESS) {
 490                 result = cbs->getfunc(source, cbs->arg, blocking);
 491                 if (result == ISC_R_QUEUEFULL) {
 492                         got = crunchsamples(ent, &cbs->samplequeue);
 493                         added += got;
 494                         desired -= ISC_MIN(got, desired);
 495                         result = ISC_R_SUCCESS;
 496                 } else if (result != ISC_R_SUCCESS &&
 497                            result != ISC_R_NOTBLOCKING)
 498                         source->bad = ISC_TRUE;
 499
 500         }
 501
 502         return (added);
 503 }
 504
 505 /*
 506  * Extract some number of bytes from the random pool, decreasing the
 507  * estimate of randomness as each byte is extracted.
 508  *
 509  * Do this by stiring the pool and returning a part of hash as randomness.
 510  * Note that no secrets are given away here since parts of the hash are
 511  * xored together before returned.
 512  *
 513  * Honor the request from the caller to only return good data, any data,
 514  * etc.
 515  */
 516 isc_result_t
 517 isc_entropy_getdata(isc_entropy_t *ent, void *data, unsigned int length,
 518                     unsigned int *returned, unsigned int flags)
 519 {
 520         unsigned int i;
 521         isc_sha1_t hash;
 522         unsigned char digest[ISC_SHA1_DIGESTLENGTH];
 523         isc_uint32_t remain, deltae, count, total;
 524         isc_uint8_t *buf;
 525         isc_boolean_t goodonly, partial, blocking;
 526
 527         REQUIRE(VALID_ENTROPY(ent));
 528         REQUIRE(data != NULL);
 529         REQUIRE(length > 0);
 530
 531         goodonly = ISC_TF((flags & ISC_ENTROPY_GOODONLY) != 0);
 532         partial = ISC_TF((flags & ISC_ENTROPY_PARTIAL) != 0);
 533         blocking = ISC_TF((flags & ISC_ENTROPY_BLOCKING) != 0);
 534
 535         REQUIRE(!partial || returned != NULL);
 536
 537         LOCK(&ent->lock);
 538
 539         remain = length;
 540         buf = data;
 541         total = 0;
 542         while (remain != 0) {
 543                 count = ISC_MIN(remain, RND_ENTROPY_THRESHOLD);
 544
 545                 /*
 546                  * If we are extracting good data only, make certain we
 547                  * have enough data in our pool for this pass.  If we don't,
 548                  * get some, and fail if we can't, and partial returns
 549                  * are not ok.
 550                  */
 551                 if (goodonly) {
 552                         unsigned int fillcount;
 553
 554                         fillcount = ISC_MAX(remain * 8, count * 8);
 555
 556                         /*
 557                          * If, however, we have at least THRESHOLD_BITS
 558                          * of entropy in the pool, don't block here.  It is
 559                          * better to drain the pool once in a while and
 560                          * then refill it than it is to constantly keep the
 561                          * pool full.
 562                          */
 563                         if (ent->pool.entropy >= THRESHOLD_BITS)
 564                                 fillpool(ent, fillcount, ISC_FALSE);
 565                         else
 566                                 fillpool(ent, fillcount, blocking);
 567
 568                         /*
 569                          * Verify that we got enough entropy to do one
 570                          * extraction.  If we didn't, bail.
 571                          */
 572                         if (ent->pool.entropy < THRESHOLD_BITS) {
 573                                 if (!partial)
 574                                         goto zeroize;
 575                                 else
 576                                         goto partial_output;
 577                         }
 578                 } else {
 579                         /*
 580                          * If we've extracted half our pool size in bits
 581                          * since the last refresh, try to refresh here.
 582                          */
 583                         if (ent->initialized < THRESHOLD_BITS)
 584                                 fillpool(ent, THRESHOLD_BITS, blocking);
 585                         else
 586                                 fillpool(ent, 0, ISC_FALSE);
 587
 588                         /*
 589                          * If we've not initialized with enough good random
 590                          * data, seed with our crappy code.
 591                          */
 592                         if (ent->initialized < THRESHOLD_BITS)
 593                                 reseed(ent);
 594                 }
 595
 596                 isc_sha1_init(&hash);
 597                 isc_sha1_update(&hash, (void *)(ent->pool.pool),
 598                                 RND_POOLBYTES);
 599                 isc_sha1_final(&hash, digest);
 600
 601                 /*
 602                  * Stir the extracted data (all of it) back into the pool.
 603                  */
 604                 entropypool_adddata(ent, digest, ISC_SHA1_DIGESTLENGTH, 0);
 605
 606                 for (i = 0; i < count; i++)
 607                         buf[i] = digest[i] ^ digest[i + RND_ENTROPY_THRESHOLD];
 608
 609                 buf += count;
 610                 remain -= count;
 611
 612                 deltae = count * 8;
 613                 deltae = ISC_MIN(deltae, ent->pool.entropy);
 614                 total += deltae;
 615                 subtract_entropy(ent, deltae);
 616                 add_pseudo(ent, count * 8);
 617         }
 618
 619  partial_output:
 620         memset(digest, 0, sizeof(digest));
 621
 622         if (returned != NULL)
 623                 *returned = (length - remain);
 624
 625         UNLOCK(&ent->lock);
 626
 627         return (ISC_R_SUCCESS);
 628
 629  zeroize:
 630         /* put the entropy we almost extracted back */
 631         add_entropy(ent, total);
 632         memset(data, 0, length);
 633         memset(digest, 0, sizeof(digest));
 634         if (returned != NULL)
 635                 *returned = 0;
 636
 637         UNLOCK(&ent->lock);
 638
 639         return (ISC_R_NOENTROPY);
 640 }
 641
 642 static void
 643 isc_entropypool_init(isc_entropypool_t *pool) {
 644         pool->cursor = RND_POOLWORDS - 1;
 645         pool->entropy = 0;
 646         pool->pseudo = 0;
 647         pool->rotate = 0;
 648         memset(pool->pool, 0, RND_POOLBYTES);
 649 }
 650
 651 static void
 652 isc_entropypool_invalidate(isc_entropypool_t *pool) {
 653         pool->cursor = 0;
 654         pool->entropy = 0;
 655         pool->pseudo = 0;
 656         pool->rotate = 0;
 657         memset(pool->pool, 0, RND_POOLBYTES);
 658 }
 659
 660 isc_result_t
 661 isc_entropy_create(isc_mem_t *mctx, isc_entropy_t **entp) {
 662         isc_result_t ret;
 663         isc_entropy_t *ent;
 664
 665         REQUIRE(mctx != NULL);
 666         REQUIRE(entp != NULL && *entp == NULL);
 667
 668         ent = isc_mem_get(mctx, sizeof(isc_entropy_t));
 669         if (ent == NULL)
 670                 return (ISC_R_NOMEMORY);
 671
 672         /*
 673          * We need a lock.
 674          */
 675         if (isc_mutex_init(&ent->lock) != ISC_R_SUCCESS) {
 676                 ret = ISC_R_UNEXPECTED;
 677                 goto errout;
 678         }
 679
 680         /*
 681          * From here down, no failures will/can occur.
 682          */
 683         ISC_LIST_INIT(ent->sources);
 684         ent->nextsource = NULL;
 685         ent->nsources = 0;
 686         ent->mctx = NULL;
 687         isc_mem_attach(mctx, &ent->mctx);
 688         ent->refcnt = 1;
 689         ent->initialized = 0;
 690         ent->initcount = 0;
 691         ent->magic = ENTROPY_MAGIC;
 692
 693         isc_entropypool_init(&ent->pool);
 694
 695         *entp = ent;
 696         return (ISC_R_SUCCESS);
 697
 698  errout:
 699         isc_mem_put(mctx, ent, sizeof(isc_entropy_t));
 700
 701         return (ret);
 702 }
 703
 704 /*
 705  * Requires "ent" be locked.
 706  */
 707 static void
 708 destroysource(isc_entropysource_t **sourcep) {
 709         isc_entropysource_t *source;
 710         isc_entropy_t *ent;
 711         isc_cbsource_t *cbs;
 712
 713         source = *sourcep;
 714         *sourcep = NULL;
 715         ent = source->ent;
 716
 717         ISC_LIST_UNLINK(ent->sources, source, link);
 718         ent->nextsource = NULL;
 719         REQUIRE(ent->nsources > 0);
 720         ent->nsources--;
 721
 722         switch (source->type) {
 723         case ENTROPY_SOURCETYPE_FILE:
 724                 if (! source->bad)
 725                         destroyfilesource(&source->sources.file);
 726                 break;
 727         case ENTROPY_SOURCETYPE_SAMPLE:
 728                 samplequeue_release(ent, &source->sources.sample.samplequeue);
 729                 break;
 730         case ENTROPY_SOURCETYPE_CALLBACK:
 731                 cbs = &source->sources.callback;
 732                 if (cbs->start_called && cbs->stopfunc != NULL) {
 733                         cbs->stopfunc(source, cbs->arg);
 734                         cbs->start_called = ISC_FALSE;
 735                 }
 736                 samplequeue_release(ent, &cbs->samplequeue);
 737                 break;
 738         }
 739
 740         memset(source, 0, sizeof(isc_entropysource_t));
 741
 742         isc_mem_put(ent->mctx, source, sizeof(isc_entropysource_t));
 743 }
 744
 745 static inline isc_boolean_t
 746 destroy_check(isc_entropy_t *ent) {
 747         isc_entropysource_t *source;
 748
 749         if (ent->refcnt > 0)
 750                 return (ISC_FALSE);
 751
 752         source = ISC_LIST_HEAD(ent->sources);
 753         while (source != NULL) {
 754                 switch (source->type) {
 755                 case ENTROPY_SOURCETYPE_FILE:
 756                         break;
 757                 default:
 758                         return (ISC_FALSE);
 759                 }
 760                 source = ISC_LIST_NEXT(source, link);
 761         }
 762
 763         return (ISC_TRUE);
 764 }
 765
 766 static void
 767 destroy(isc_entropy_t **entp) {
 768         isc_entropy_t *ent;
 769         isc_entropysource_t *source;
 770         isc_mem_t *mctx;
 771
 772         REQUIRE(entp != NULL && *entp != NULL);
 773         ent = *entp;
 774         *entp = NULL;
 775
 776         LOCK(&ent->lock);
 777
 778         REQUIRE(ent->refcnt == 0);
 779
 780         /*
 781          * Here, detach non-sample sources.
 782          */
 783         source = ISC_LIST_HEAD(ent->sources);
 784         while (source != NULL) {
 785                 switch(source->type) {
 786                 case ENTROPY_SOURCETYPE_FILE:
 787                         destroysource(&source);
 788                         break;
 789                 }
 790                 source = ISC_LIST_HEAD(ent->sources);
 791         }
 792
 793         /*
 794          * If there are other types of sources, we've found a bug.
 795          */
 796         REQUIRE(ISC_LIST_EMPTY(ent->sources));
 797
 798         mctx = ent->mctx;
 799
 800         isc_entropypool_invalidate(&ent->pool);
 801
 802         UNLOCK(&ent->lock);
 803
 804         DESTROYLOCK(&ent->lock);
 805
 806         memset(ent, 0, sizeof(isc_entropy_t));
 807         isc_mem_put(mctx, ent, sizeof(isc_entropy_t));
 808         isc_mem_detach(&mctx);
 809 }
 810
 811 void
 812 isc_entropy_destroysource(isc_entropysource_t **sourcep) {
 813         isc_entropysource_t *source;
 814         isc_entropy_t *ent;
 815         isc_boolean_t killit;
 816
 817         REQUIRE(sourcep != NULL);
 818         REQUIRE(VALID_SOURCE(*sourcep));
 819
 820         source = *sourcep;
 821         *sourcep = NULL;
 822
 823         ent = source->ent;
 824         REQUIRE(VALID_ENTROPY(ent));
 825
 826         LOCK(&ent->lock);
 827
 828         destroysource(&source);
 829
 830         killit = destroy_check(ent);
 831
 832         UNLOCK(&ent->lock);
 833
 834         if (killit)
 835                 destroy(&ent);
 836 }
 837
 838 isc_result_t
 839 isc_entropy_createcallbacksource(isc_entropy_t *ent,
 840                                  isc_entropystart_t start,
 841                                  isc_entropyget_t get,
 842                                  isc_entropystop_t stop,
 843                                  void *arg,
 844                                  isc_entropysource_t **sourcep)
 845 {
 846         isc_result_t ret;
 847         isc_entropysource_t *source;
 848         isc_cbsource_t *cbs;
 849
 850         REQUIRE(VALID_ENTROPY(ent));
 851         REQUIRE(get != NULL);
 852         REQUIRE(sourcep != NULL && *sourcep == NULL);
 853
 854         LOCK(&ent->lock);
 855
 856         source = isc_mem_get(ent->mctx, sizeof(isc_entropysource_t));
 857         if (source == NULL) {
 858                 ret = ISC_R_NOMEMORY;
 859                 goto errout;
 860         }
 861         source->bad = ISC_FALSE;
 862
 863         cbs = &source->sources.callback;
 864
 865         ret = samplesource_allocate(ent, &cbs->samplequeue);
 866         if (ret != ISC_R_SUCCESS)
 867                 goto errout;
 868
 869         cbs->start_called = ISC_FALSE;
 870         cbs->startfunc = start;
 871         cbs->getfunc = get;
 872         cbs->stopfunc = stop;
 873         cbs->arg = arg;
 874
 875         /*
 876          * From here down, no failures can occur.
 877          */
 878         source->magic = SOURCE_MAGIC;
 879         source->type = ENTROPY_SOURCETYPE_CALLBACK;
 880         source->ent = ent;
 881         source->total = 0;
 882         memset(source->name, 0, sizeof(source->name));
 883         ISC_LINK_INIT(source, link);
 884
 885         /*
 886          * Hook it into the entropy system.
 887          */
 888         ISC_LIST_APPEND(ent->sources, source, link);
 889         ent->nsources++;
 890
 891         *sourcep = source;
 892
 893         UNLOCK(&ent->lock);
 894         return (ISC_R_SUCCESS);
 895
 896  errout:
 897         if (source != NULL)
 898                 isc_mem_put(ent->mctx, source, sizeof(isc_entropysource_t));
 899
 900         UNLOCK(&ent->lock);
 901
 902         return (ret);
 903 }
 904
 905 void
 906 isc_entropy_stopcallbacksources(isc_entropy_t *ent) {
 907         isc_entropysource_t *source;
 908         isc_cbsource_t *cbs;
 909
 910         REQUIRE(VALID_ENTROPY(ent));
 911
 912         LOCK(&ent->lock);
 913
 914         source = ISC_LIST_HEAD(ent->sources);
 915         while (source != NULL) {
 916                 if (source->type == ENTROPY_SOURCETYPE_CALLBACK) {
 917                         cbs = &source->sources.callback;
 918                         if (cbs->start_called && cbs->stopfunc != NULL) {
 919                                 cbs->stopfunc(source, cbs->arg);
 920                                 cbs->start_called = ISC_FALSE;
 921                         }
 922                 }
 923
 924                 source = ISC_LIST_NEXT(source, link);
 925         }
 926
 927         UNLOCK(&ent->lock);
 928 }
 929
 930 isc_result_t
 931 isc_entropy_createsamplesource(isc_entropy_t *ent,
 932                                isc_entropysource_t **sourcep)
 933 {
 934         isc_result_t ret;
 935         isc_entropysource_t *source;
 936         sample_queue_t *sq;
 937
 938         REQUIRE(VALID_ENTROPY(ent));
 939         REQUIRE(sourcep != NULL && *sourcep == NULL);
 940
 941         LOCK(&ent->lock);
 942
 943         source = isc_mem_get(ent->mctx, sizeof(isc_entropysource_t));
 944         if (source == NULL) {
 945                 ret = ISC_R_NOMEMORY;
 946                 goto errout;
 947         }
 948
 949         sq = &source->sources.sample.samplequeue;
 950         ret = samplesource_allocate(ent, sq);
 951         if (ret != ISC_R_SUCCESS)
 952                 goto errout;
 953
 954         /*
 955          * From here down, no failures can occur.
 956          */
 957         source->magic = SOURCE_MAGIC;
 958         source->type = ENTROPY_SOURCETYPE_SAMPLE;
 959         source->ent = ent;
 960         source->total = 0;
 961         memset(source->name, 0, sizeof(source->name));
 962         ISC_LINK_INIT(source, link);
 963
 964         /*
 965          * Hook it into the entropy system.
 966          */
 967         ISC_LIST_APPEND(ent->sources, source, link);
 968         ent->nsources++;
 969
 970         *sourcep = source;
 971
 972         UNLOCK(&ent->lock);
 973         return (ISC_R_SUCCESS);
 974
 975  errout:
 976         if (source != NULL)
 977                 isc_mem_put(ent->mctx, source, sizeof(isc_entropysource_t));
 978
 979         UNLOCK(&ent->lock);
 980
 981         return (ret);
 982 }
 983
 984 /*
 985  * Add a sample, and return ISC_R_SUCCESS if the queue has become full,
 986  * ISC_R_NOENTROPY if it has space remaining, and ISC_R_NOMORE if the
 987  * queue was full when this function was called.
 988  */
 989 static isc_result_t
 990 addsample(sample_queue_t *sq, isc_uint32_t sample, isc_uint32_t extra) {
 991         if (sq->nsamples >= RND_EVENTQSIZE)
 992                 return (ISC_R_NOMORE);
 993
 994         sq->samples[sq->nsamples] = sample;
 995         sq->extra[sq->nsamples] = extra;
 996         sq->nsamples++;
 997
 998         if (sq->nsamples >= RND_EVENTQSIZE)
 999                 return (ISC_R_QUEUEFULL);
1000
1001         return (ISC_R_SUCCESS);
1002 }
1003
1004 isc_result_t
1005 isc_entropy_addsample(isc_entropysource_t *source, isc_uint32_t sample,
1006                       isc_uint32_t extra)
1007 {
1008         isc_entropy_t *ent;
1009         sample_queue_t *sq;
1010         unsigned int entropy;
1011         isc_result_t result;
1012
1013         REQUIRE(VALID_SOURCE(source));
1014
1015         ent = source->ent;
1016
1017         LOCK(&ent->lock);
1018
1019         sq = &source->sources.sample.samplequeue;
1020         result = addsample(sq, sample, extra);
1021         if (result == ISC_R_QUEUEFULL) {
1022                 entropy = crunchsamples(ent, sq);
1023                 add_entropy(ent, entropy);
1024         }
1025
1026         UNLOCK(&ent->lock);
1027
1028         return (result);
1029 }
1030
1031 isc_result_t
1032 isc_entropy_addcallbacksample(isc_entropysource_t *source, isc_uint32_t sample,
1033                               isc_uint32_t extra)
1034 {
1035         sample_queue_t *sq;
1036         isc_result_t result;
1037
1038         REQUIRE(VALID_SOURCE(source));
1039         REQUIRE(source->type == ENTROPY_SOURCETYPE_CALLBACK);
1040
1041         sq = &source->sources.callback.samplequeue;
1042         result = addsample(sq, sample, extra);
1043
1044         return (result);
1045 }
1046
1047 void
1048 isc_entropy_putdata(isc_entropy_t *ent, void *data, unsigned int length,
1049                     isc_uint32_t entropy)
1050 {
1051         REQUIRE(VALID_ENTROPY(ent));
1052
1053         LOCK(&ent->lock);
1054
1055         entropypool_adddata(ent, data, length, entropy);
1056
1057         if (ent->initialized < THRESHOLD_BITS)
1058                 ent->initialized = THRESHOLD_BITS;
1059
1060         UNLOCK(&ent->lock);
1061 }
1062
1063 static void
1064 dumpstats(isc_entropy_t *ent, FILE *out) {
1065         fprintf(out,
1066                 isc_msgcat_get(isc_msgcat, ISC_MSGSET_ENTROPY,
1067                                ISC_MSG_ENTROPYSTATS,
1068                                "Entropy pool %p:  refcnt %u cursor %u,"
1069                                " rotate %u entropy %u pseudo %u nsources %u"
1070                                " nextsource %p initialized %u initcount %u\n"),
1071                 ent, ent->refcnt,
1072                 ent->pool.cursor, ent->pool.rotate,
1073                 ent->pool.entropy, ent->pool.pseudo,
1074                 ent->nsources, ent->nextsource, ent->initialized,
1075                 ent->initcount);
1076 }
1077
1078 /*
1079  * This function ignores locking.  Use at your own risk.
1080  */
1081 void
1082 isc_entropy_stats(isc_entropy_t *ent, FILE *out) {
1083         REQUIRE(VALID_ENTROPY(ent));
1084
1085         LOCK(&ent->lock);
1086         dumpstats(ent, out);
1087         UNLOCK(&ent->lock);
1088 }
1089
1090 void
1091 isc_entropy_attach(isc_entropy_t *ent, isc_entropy_t **entp) {
1092         REQUIRE(VALID_ENTROPY(ent));
1093         REQUIRE(entp != NULL && *entp == NULL);
1094
1095         LOCK(&ent->lock);
1096
1097         ent->refcnt++;
1098         *entp = ent;
1099
1100         UNLOCK(&ent->lock);
1101 }
1102
1103 void
1104 isc_entropy_detach(isc_entropy_t **entp) {
1105         isc_entropy_t *ent;
1106         isc_boolean_t killit;
1107
1108         REQUIRE(entp != NULL && VALID_ENTROPY(*entp));
1109         ent = *entp;
1110         *entp = NULL;
1111
1112         LOCK(&ent->lock);
1113
1114         REQUIRE(ent->refcnt > 0);
1115         ent->refcnt--;
1116
1117         killit = destroy_check(ent);
1118
1119         UNLOCK(&ent->lock);
1120
1121         if (killit)
1122                 destroy(&ent);
1123 }
1124
1125 static isc_result_t
1126 kbdstart(isc_entropysource_t *source, void *arg, isc_boolean_t blocking) {
1127         /*
1128          * The intent of "first" is to provide a warning message only once
1129          * during the run of a program that might try to gather keyboard
1130          * entropy multiple times.
1131          */
1132         static isc_boolean_t first = ISC_TRUE;
1133
1134         UNUSED(arg);
1135
1136         if (! blocking)
1137                 return (ISC_R_NOENTROPY);
1138
1139         if (first) {
1140                 if (source->warn_keyboard)
1141                         fprintf(stderr, "You must use the keyboard to create "
1142                                 "entropy, since your system is lacking\n"
1143                                 "/dev/random (or equivalent)\n\n");
1144                 first = ISC_FALSE;
1145         }
1146         fprintf(stderr, "start typing:\n");
1147
1148         return (isc_keyboard_open(&source->kbd));
1149 }
1150
1151 static void
1152 kbdstop(isc_entropysource_t *source, void *arg) {
1153
1154         UNUSED(arg);
1155
1156         if (! isc_keyboard_canceled(&source->kbd))
1157                 fprintf(stderr, "stop typing.\r\n");
1158
1159         (void)isc_keyboard_close(&source->kbd, 3);
1160 }
1161
1162 static isc_result_t
1163 kbdget(isc_entropysource_t *source, void *arg, isc_boolean_t blocking) {
1164         isc_result_t result;
1165         isc_time_t t;
1166         isc_uint32_t sample;
1167         isc_uint32_t extra;
1168         unsigned char c;
1169
1170         UNUSED(arg);
1171
1172         if (!blocking)
1173                 return (ISC_R_NOTBLOCKING);
1174
1175         result = isc_keyboard_getchar(&source->kbd, &c);
1176         if (result != ISC_R_SUCCESS)
1177                 return (result);
1178
1179         result = isc_time_now(&t);
1180         if (result != ISC_R_SUCCESS)
1181                 return (result);
1182
1183         sample = isc_time_nanoseconds(&t);
1184         extra = c;
1185
1186         result = isc_entropy_addcallbacksample(source, sample, extra);
1187         if (result != ISC_R_SUCCESS) {
1188                 fprintf(stderr, "\r\n");
1189                 return (result);
1190         }
1191
1192         fprintf(stderr, ".");
1193         fflush(stderr);
1194
1195         return (result);
1196 }
1197
1198 isc_result_t
1199 isc_entropy_usebestsource(isc_entropy_t *ectx, isc_entropysource_t **source,
1200                           const char *randomfile, int use_keyboard)
1201 {
1202         isc_result_t result;
1203         isc_result_t final_result = ISC_R_NOENTROPY;
1204         isc_boolean_t userfile = ISC_TRUE;
1205
1206         REQUIRE(VALID_ENTROPY(ectx));
1207         REQUIRE(source != NULL && *source == NULL);
1208         REQUIRE(use_keyboard == ISC_ENTROPY_KEYBOARDYES ||
1209                 use_keyboard == ISC_ENTROPY_KEYBOARDNO  ||
1210                 use_keyboard == ISC_ENTROPY_KEYBOARDMAYBE);
1211
1212 #ifdef PATH_RANDOMDEV
1213         if (randomfile == NULL) {
1214                 randomfile = PATH_RANDOMDEV;
1215                 userfile = ISC_FALSE;
1216         }
1217 #endif
1218
1219         if (randomfile != NULL && use_keyboard != ISC_ENTROPY_KEYBOARDYES) {
1220                 result = isc_entropy_createfilesource(ectx, randomfile);
1221                 if (result == ISC_R_SUCCESS &&
1222                     use_keyboard == ISC_ENTROPY_KEYBOARDMAYBE)
1223                         use_keyboard = ISC_ENTROPY_KEYBOARDNO;
1224                 if (result != ISC_R_SUCCESS && userfile)
1225                         return (result);
1226
1227                 final_result = result;
1228         }
1229
1230         if (use_keyboard != ISC_ENTROPY_KEYBOARDNO) {
1231                 result = isc_entropy_createcallbacksource(ectx, kbdstart,
1232                                                           kbdget, kbdstop,
1233                                                           NULL, source);
1234                 if (result == ISC_R_SUCCESS)
1235                         (*source)->warn_keyboard =
1236                                 ISC_TF(use_keyboard ==
1237                                        ISC_ENTROPY_KEYBOARDMAYBE);
1238
1239                 if (final_result != ISC_R_SUCCESS)
1240                         final_result = result;
1241         }
1242
1243         /*
1244          * final_result is ISC_R_SUCCESS if at least one source of entropy
1245          * could be started, otherwise it is the error from the most recently
1246          * failed operation (or ISC_R_NOENTROPY if PATH_RANDOMDEV is not
1247          * defined and use_keyboard is ISC_ENTROPY_KEYBOARDNO).
1248          */
1249         return (final_result);
1250 }