contrib/bind-9.3/lib/isc/entropy.c

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