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

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