Annotation of embedaddon/ntp/lib/isc/entropy.c, revision 1.1
1.1 ! misho 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.332.2 2009/01/18 23:47:41 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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>