contrib/bind9/lib/isc/entropy.c

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