162587Sitojun/* $NetBSD$ */ 262587Sitojun 362587Sitojun/* 462587Sitojun * Copyright (C) 2004-2007, 2009, 2010 Internet Systems Consortium, Inc. ("ISC") 562587Sitojun * Copyright (C) 2000-2003 Internet Software Consortium. 662587Sitojun * 762587Sitojun * Permission to use, copy, modify, and/or distribute this software for any 862587Sitojun * purpose with or without fee is hereby granted, provided that the above 962587Sitojun * copyright notice and this permission notice appear in all copies. 1062587Sitojun * 1162587Sitojun * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 1262587Sitojun * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 1362587Sitojun * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 1462587Sitojun * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 1562587Sitojun * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 1662587Sitojun * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 1762587Sitojun * PERFORMANCE OF THIS SOFTWARE. 1862587Sitojun */ 1962587Sitojun 2062587Sitojun/* Id: entropy.c,v 1.22 2010/08/10 23:48:19 tbox Exp */ 2162587Sitojun 2262587Sitojun/*! \file 2362587Sitojun * \brief 2462587Sitojun * This is the system independent part of the entropy module. It is 2562587Sitojun * compiled via inclusion from the relevant OS source file, ie, 2662587Sitojun * \link unix/entropy.c unix/entropy.c \endlink or win32/entropy.c. 2762587Sitojun * 2862587Sitojun * \author Much of this code is modeled after the NetBSD /dev/random implementation, 2962587Sitojun * written by Michael Graff <explorer@netbsd.org>. 3062587Sitojun */ 3162587Sitojun 3262587Sitojun#include <errno.h> 3362587Sitojun#include <fcntl.h> 3462587Sitojun#include <stdio.h> 3562587Sitojun 3662587Sitojun#include <isc/buffer.h> 3762587Sitojun#include <isc/entropy.h> 3862587Sitojun#include <isc/keyboard.h> 3962587Sitojun#include <isc/list.h> 4062587Sitojun#include <isc/magic.h> 4162587Sitojun#include <isc/mem.h> 4262587Sitojun#include <isc/msgs.h> 4362587Sitojun#include <isc/mutex.h> 4462587Sitojun#include <isc/platform.h> 4562587Sitojun#include <isc/region.h> 4662587Sitojun#include <isc/sha1.h> 4762587Sitojun#include <isc/string.h> 4862587Sitojun#include <isc/time.h> 4962587Sitojun#include <isc/util.h> 5062587Sitojun 5162587Sitojun 5262587Sitojun#define ENTROPY_MAGIC ISC_MAGIC('E', 'n', 't', 'e') 5362587Sitojun#define SOURCE_MAGIC ISC_MAGIC('E', 'n', 't', 's') 5462587Sitojun 5562587Sitojun#define VALID_ENTROPY(e) ISC_MAGIC_VALID(e, ENTROPY_MAGIC) 5662587Sitojun#define VALID_SOURCE(s) ISC_MAGIC_VALID(s, SOURCE_MAGIC) 5762587Sitojun 5862587Sitojun/*** 5962587Sitojun *** "constants." Do not change these unless you _really_ know what 6062587Sitojun *** you are doing. 6162587Sitojun ***/ 6262587Sitojun 6362587Sitojun/*% 6462587Sitojun * Size of entropy pool in 32-bit words. This _MUST_ be a power of 2. 6562587Sitojun */ 6662587Sitojun#define RND_POOLWORDS 128 6762587Sitojun/*% Pool in bytes. */ 6862587Sitojun#define RND_POOLBYTES (RND_POOLWORDS * 4) 6962587Sitojun/*% Pool in bits. */ 7062587Sitojun#define RND_POOLBITS (RND_POOLWORDS * 32) 7162587Sitojun 7262587Sitojun/*% 7362587Sitojun * Number of bytes returned per hash. This must be true: 7462587Sitojun * threshold * 2 <= digest_size_in_bytes 7562587Sitojun */ 7662587Sitojun#define RND_ENTROPY_THRESHOLD 10 7762587Sitojun#define THRESHOLD_BITS (RND_ENTROPY_THRESHOLD * 8) 7862587Sitojun 7962587Sitojun/*% 8062587Sitojun * Size of the input event queue in samples. 8162587Sitojun */ 8262587Sitojun#define RND_EVENTQSIZE 32 8362587Sitojun 8462587Sitojun/*% 8562587Sitojun * The number of times we'll "reseed" for pseudorandom seeds. This is an 8662587Sitojun * extremely weak pseudorandom seed. If the caller is using lots of 8762587Sitojun * pseudorandom data and they cannot provide a stronger random source, 8862587Sitojun * there is little we can do other than hope they're smart enough to 8962587Sitojun * call _adddata() with something better than we can come up with. 9062587Sitojun */ 9162587Sitojun#define RND_INITIALIZE 128 9262587Sitojun 9362587Sitojun/*% Entropy Pool */ 9462587Sitojuntypedef struct { 9562587Sitojun isc_uint32_t cursor; /*%< current add point in the pool */ 9662587Sitojun isc_uint32_t entropy; /*%< current entropy estimate in bits */ 9762587Sitojun isc_uint32_t pseudo; /*%< bits extracted in pseudorandom */ 9862587Sitojun isc_uint32_t rotate; /*%< how many bits to rotate by */ 9962587Sitojun isc_uint32_t pool[RND_POOLWORDS]; /*%< random pool data */ 10062587Sitojun} isc_entropypool_t; 10162587Sitojun 10262587Sitojunstruct isc_entropy { 10362587Sitojun unsigned int magic; 10462587Sitojun isc_mem_t *mctx; 10562587Sitojun isc_mutex_t lock; 10662587Sitojun unsigned int refcnt; 10762587Sitojun isc_uint32_t initialized; 10862587Sitojun isc_uint32_t initcount; 10962587Sitojun isc_entropypool_t pool; 11062587Sitojun unsigned int nsources; 11162587Sitojun isc_entropysource_t *nextsource; 11262587Sitojun ISC_LIST(isc_entropysource_t) sources; 11362587Sitojun}; 11462587Sitojun 11562587Sitojun/*% Sample Queue */ 11662587Sitojuntypedef struct { 11762587Sitojun isc_uint32_t last_time; /*%< last time recorded */ 11862587Sitojun isc_uint32_t last_delta; /*%< last delta value */ 11962587Sitojun isc_uint32_t last_delta2; /*%< last delta2 value */ 12062587Sitojun isc_uint32_t nsamples; /*%< number of samples filled in */ 12162587Sitojun isc_uint32_t *samples; /*%< the samples */ 12262587Sitojun isc_uint32_t *extra; /*%< extra samples added in */ 12362587Sitojun} sample_queue_t; 12462587Sitojun 12562587Sitojuntypedef struct { 12662587Sitojun sample_queue_t samplequeue; 12762587Sitojun} isc_entropysamplesource_t; 12862587Sitojun 12962587Sitojuntypedef struct { 13062587Sitojun isc_boolean_t start_called; 13162587Sitojun isc_entropystart_t startfunc; 13262587Sitojun isc_entropyget_t getfunc; 13362587Sitojun isc_entropystop_t stopfunc; 13462587Sitojun void *arg; 13562587Sitojun sample_queue_t samplequeue; 13662587Sitojun} isc_cbsource_t; 13762587Sitojun 13862587Sitojuntypedef struct { 13962587Sitojun FILESOURCE_HANDLE_TYPE handle; 14062587Sitojun} isc_entropyfilesource_t; 14162587Sitojun 14262587Sitojunstruct isc_entropysource { 14362587Sitojun unsigned int magic; 14462587Sitojun unsigned int type; 14562587Sitojun isc_entropy_t *ent; 14662587Sitojun isc_uint32_t total; /*%< entropy from this source */ 14762587Sitojun ISC_LINK(isc_entropysource_t) link; 14862587Sitojun char name[32]; 14962587Sitojun isc_boolean_t bad; 15062587Sitojun isc_boolean_t warn_keyboard; 15162587Sitojun isc_keyboard_t kbd; 15262587Sitojun union { 15362587Sitojun isc_entropysamplesource_t sample; 15462587Sitojun isc_entropyfilesource_t file; 15562587Sitojun isc_cbsource_t callback; 15662587Sitojun isc_entropyusocketsource_t usocket; 15762587Sitojun } sources; 15862587Sitojun}; 15962587Sitojun 16062587Sitojun#define ENTROPY_SOURCETYPE_SAMPLE 1 /*%< Type is a sample source */ 16162587Sitojun#define ENTROPY_SOURCETYPE_FILE 2 /*%< Type is a file source */ 16262587Sitojun#define ENTROPY_SOURCETYPE_CALLBACK 3 /*%< Type is a callback source */ 16362587Sitojun#define ENTROPY_SOURCETYPE_USOCKET 4 /*%< Type is a Unix socket source */ 16462587Sitojun 16562587Sitojun/*@{*/ 16662587Sitojun/*% 16762587Sitojun * The random pool "taps" 16862587Sitojun */ 16962587Sitojun#define TAP1 99 17062587Sitojun#define TAP2 59 17162587Sitojun#define TAP3 31 17262587Sitojun#define TAP4 9 17362587Sitojun#define TAP5 7 17462587Sitojun/*@}*/ 17562587Sitojun 17662587Sitojun/*@{*/ 17762587Sitojun/*% 17862587Sitojun * Declarations for function provided by the system dependent sources that 17962587Sitojun * include this file. 18062587Sitojun */ 18162587Sitojunstatic void 18262587Sitojunfillpool(isc_entropy_t *, unsigned int, isc_boolean_t); 18362587Sitojun 18462587Sitojunstatic int 18562587Sitojunwait_for_sources(isc_entropy_t *); 18662587Sitojun 18762587Sitojunstatic void 18862587Sitojundestroyfilesource(isc_entropyfilesource_t *source); 18962587Sitojun 19062587Sitojunstatic void 19162587Sitojundestroyusocketsource(isc_entropyusocketsource_t *source); 19262587Sitojun 19362587Sitojun/*@}*/ 19462587Sitojun 19562587Sitojunstatic void 19662587Sitojunsamplequeue_release(isc_entropy_t *ent, sample_queue_t *sq) { 19762587Sitojun REQUIRE(sq->samples != NULL); 19862587Sitojun REQUIRE(sq->extra != NULL); 19962587Sitojun 20062587Sitojun isc_mem_put(ent->mctx, sq->samples, RND_EVENTQSIZE * 4); 20162587Sitojun isc_mem_put(ent->mctx, sq->extra, RND_EVENTQSIZE * 4); 20262587Sitojun sq->samples = NULL; 20362587Sitojun sq->extra = NULL; 20462587Sitojun} 20562587Sitojun 20662587Sitojunstatic isc_result_t 20762587Sitojunsamplesource_allocate(isc_entropy_t *ent, sample_queue_t *sq) { 20862587Sitojun sq->samples = isc_mem_get(ent->mctx, RND_EVENTQSIZE * 4); 20962587Sitojun if (sq->samples == NULL) 21062587Sitojun return (ISC_R_NOMEMORY); 21162587Sitojun 21262587Sitojun sq->extra = isc_mem_get(ent->mctx, RND_EVENTQSIZE * 4); 21362587Sitojun if (sq->extra == NULL) { 21462587Sitojun isc_mem_put(ent->mctx, sq->samples, RND_EVENTQSIZE * 4); 21562587Sitojun sq->samples = NULL; 21662587Sitojun return (ISC_R_NOMEMORY); 21762587Sitojun } 21862587Sitojun 21962587Sitojun sq->nsamples = 0; 22062587Sitojun 22162587Sitojun return (ISC_R_SUCCESS); 22262587Sitojun} 22362587Sitojun 22462587Sitojun/*% 22562587Sitojun * Add in entropy, even when the value we're adding in could be 22662587Sitojun * very large. 22762587Sitojun */ 22862587Sitojunstatic inline void 22962587Sitojunadd_entropy(isc_entropy_t *ent, isc_uint32_t entropy) { 23062587Sitojun /* clamp input. Yes, this must be done. */ 23162587Sitojun entropy = ISC_MIN(entropy, RND_POOLBITS); 23262587Sitojun /* Add in the entropy we already have. */ 23362587Sitojun entropy += ent->pool.entropy; 23462587Sitojun /* Clamp. */ 23562587Sitojun ent->pool.entropy = ISC_MIN(entropy, RND_POOLBITS); 23662587Sitojun} 23762587Sitojun 23862587Sitojun/*% 23962587Sitojun * Decrement the amount of entropy the pool has. 24062587Sitojun */ 24162587Sitojunstatic inline void 24262587Sitojunsubtract_entropy(isc_entropy_t *ent, isc_uint32_t entropy) { 24362587Sitojun entropy = ISC_MIN(entropy, ent->pool.entropy); 24462587Sitojun ent->pool.entropy -= entropy; 24562587Sitojun} 24662587Sitojun 24762587Sitojun/*! 24862587Sitojun * Add in entropy, even when the value we're adding in could be 24962587Sitojun * very large. 25062587Sitojun */ 25162587Sitojunstatic inline void 25262587Sitojunadd_pseudo(isc_entropy_t *ent, isc_uint32_t pseudo) { 25362587Sitojun /* clamp input. Yes, this must be done. */ 25462587Sitojun pseudo = ISC_MIN(pseudo, RND_POOLBITS * 8); 25562587Sitojun /* Add in the pseudo we already have. */ 25662587Sitojun pseudo += ent->pool.pseudo; 25762587Sitojun /* Clamp. */ 25862587Sitojun ent->pool.pseudo = ISC_MIN(pseudo, RND_POOLBITS * 8); 25962587Sitojun} 26062587Sitojun 26162587Sitojun/*! 26262587Sitojun * Decrement the amount of pseudo the pool has. 26362587Sitojun */ 26462587Sitojunstatic inline void 26562587Sitojunsubtract_pseudo(isc_entropy_t *ent, isc_uint32_t pseudo) { 26662587Sitojun pseudo = ISC_MIN(pseudo, ent->pool.pseudo); 26762587Sitojun ent->pool.pseudo -= pseudo; 26862587Sitojun} 26962587Sitojun 27062587Sitojun/*! 27162587Sitojun * Add one word to the pool, rotating the input as needed. 27262587Sitojun */ 27362587Sitojunstatic inline void 27462587Sitojunentropypool_add_word(isc_entropypool_t *rp, isc_uint32_t val) { 27562587Sitojun /* 27662587Sitojun * Steal some values out of the pool, and xor them into the 27762587Sitojun * word we were given. 27862587Sitojun * 27962587Sitojun * Mix the new value into the pool using xor. This will 28062587Sitojun * prevent the actual values from being known to the caller 28162587Sitojun * since the previous values are assumed to be unknown as well. 28262587Sitojun */ 28362587Sitojun val ^= rp->pool[(rp->cursor + TAP1) & (RND_POOLWORDS - 1)]; 28462587Sitojun val ^= rp->pool[(rp->cursor + TAP2) & (RND_POOLWORDS - 1)]; 28562587Sitojun val ^= rp->pool[(rp->cursor + TAP3) & (RND_POOLWORDS - 1)]; 28662587Sitojun val ^= rp->pool[(rp->cursor + TAP4) & (RND_POOLWORDS - 1)]; 28762587Sitojun val ^= rp->pool[(rp->cursor + TAP5) & (RND_POOLWORDS - 1)]; 28862587Sitojun if (rp->rotate == 0) 28962587Sitojun rp->pool[rp->cursor++] ^= val; 29062587Sitojun else 29162587Sitojun rp->pool[rp->cursor++] ^= 29262587Sitojun ((val << rp->rotate) | (val >> (32 - rp->rotate))); 29362587Sitojun 29462587Sitojun /* 29562587Sitojun * If we have looped around the pool, increment the rotate 29662587Sitojun * variable so the next value will get xored in rotated to 29762587Sitojun * a different position. 29862587Sitojun * Increment by a value that is relatively prime to the word size 29962587Sitojun * to try to spread the bits throughout the pool quickly when the 30062587Sitojun * pool is empty. 30162587Sitojun */ 30262587Sitojun if (rp->cursor == RND_POOLWORDS) { 30362587Sitojun rp->cursor = 0; 30462587Sitojun rp->rotate = (rp->rotate + 7) & 31; 30562587Sitojun } 30662587Sitojun} 30762587Sitojun 30862587Sitojun/*! 30962587Sitojun * Add a buffer's worth of data to the pool. 31062587Sitojun * 31162587Sitojun * Requires that the lock is held on the entropy pool. 31262587Sitojun */ 31362587Sitojunstatic void 31462587Sitojunentropypool_adddata(isc_entropy_t *ent, void *p, unsigned int len, 31562587Sitojun isc_uint32_t entropy) 31662587Sitojun{ 31762587Sitojun isc_uint32_t val; 31862587Sitojun unsigned long addr; 31962587Sitojun isc_uint8_t *buf; 32062587Sitojun 32162587Sitojun addr = (unsigned long)p; 32262587Sitojun buf = p; 32362587Sitojun 32462587Sitojun if ((addr & 0x03U) != 0U) { 32562587Sitojun val = 0; 32662587Sitojun switch (len) { 32762587Sitojun case 3: 32862587Sitojun val = *buf++; 32962587Sitojun len--; 33062587Sitojun case 2: 33162587Sitojun val = val << 8 | *buf++; 33262587Sitojun len--; 33362587Sitojun case 1: 33462587Sitojun val = val << 8 | *buf++; 33562587Sitojun len--; 33662587Sitojun } 33762587Sitojun 33862587Sitojun entropypool_add_word(&ent->pool, val); 33962587Sitojun } 34062587Sitojun 34162587Sitojun for (; len > 3; len -= 4) { 34262587Sitojun val = *((isc_uint32_t *)buf); 34362587Sitojun 34462587Sitojun entropypool_add_word(&ent->pool, val); 34562587Sitojun buf += 4; 34662587Sitojun } 34762587Sitojun 34862587Sitojun if (len != 0) { 34962587Sitojun val = 0; 35062587Sitojun switch (len) { 35162587Sitojun case 3: 35262587Sitojun val = *buf++; 35362587Sitojun case 2: 35462587Sitojun val = val << 8 | *buf++; 35562587Sitojun case 1: 35662587Sitojun val = val << 8 | *buf++; 35762587Sitojun } 35862587Sitojun 35962587Sitojun entropypool_add_word(&ent->pool, val); 36062587Sitojun } 36162587Sitojun 36262587Sitojun add_entropy(ent, entropy); 36362587Sitojun subtract_pseudo(ent, entropy); 36462587Sitojun} 36562587Sitojun 36662587Sitojunstatic inline void 36762587Sitojunreseed(isc_entropy_t *ent) { 36862587Sitojun isc_time_t t; 36962587Sitojun pid_t pid; 37062587Sitojun 37162587Sitojun if (ent->initcount == 0) { 37262587Sitojun pid = getpid(); 37362587Sitojun entropypool_adddata(ent, &pid, sizeof(pid), 0); 37462587Sitojun pid = getppid(); 37562587Sitojun entropypool_adddata(ent, &pid, sizeof(pid), 0); 37662587Sitojun } 37762587Sitojun 37862587Sitojun /*! 37962587Sitojun * After we've reseeded 100 times, only add new timing info every 38062587Sitojun * 50 requests. This will keep us from using lots and lots of 38162587Sitojun * CPU just to return bad pseudorandom data anyway. 38262587Sitojun */ 38362587Sitojun if (ent->initcount > 100) 38462587Sitojun if ((ent->initcount % 50) != 0) 38562587Sitojun return; 38662587Sitojun 38762587Sitojun TIME_NOW(&t); 38862587Sitojun entropypool_adddata(ent, &t, sizeof(t), 0); 38962587Sitojun ent->initcount++; 39062587Sitojun} 39162587Sitojun 39262587Sitojunstatic inline unsigned int 39362587Sitojunestimate_entropy(sample_queue_t *sq, isc_uint32_t t) { 39462587Sitojun isc_int32_t delta; 39562587Sitojun isc_int32_t delta2; 39662587Sitojun isc_int32_t delta3; 39762587Sitojun 39862587Sitojun /*! 39962587Sitojun * If the time counter has overflowed, calculate the real difference. 40062587Sitojun * If it has not, it is simpler. 40162587Sitojun */ 40262587Sitojun if (t < sq->last_time) 40362587Sitojun delta = UINT_MAX - sq->last_time + t; 40462587Sitojun else 40562587Sitojun delta = sq->last_time - t; 40662587Sitojun 40762587Sitojun if (delta < 0) 40862587Sitojun delta = -delta; 40962587Sitojun 41062587Sitojun /* 41162587Sitojun * Calculate the second and third order differentials 41262587Sitojun */ 41362587Sitojun delta2 = sq->last_delta - delta; 41462587Sitojun if (delta2 < 0) 41562587Sitojun delta2 = -delta2; 41662587Sitojun 41762587Sitojun delta3 = sq->last_delta2 - delta2; 41862587Sitojun if (delta3 < 0) 41962587Sitojun delta3 = -delta3; 420 421 sq->last_time = t; 422 sq->last_delta = delta; 423 sq->last_delta2 = delta2; 424 425 /* 426 * If any delta is 0, we got no entropy. If all are non-zero, we 427 * might have something. 428 */ 429 if (delta == 0 || delta2 == 0 || delta3 == 0) 430 return 0; 431 432 /* 433 * We could find the smallest delta and claim we got log2(delta) 434 * bits, but for now return that we found 1 bit. 435 */ 436 return 1; 437} 438 439static unsigned int 440crunchsamples(isc_entropy_t *ent, sample_queue_t *sq) { 441 unsigned int ns; 442 unsigned int added; 443 444 if (sq->nsamples < 6) 445 return (0); 446 447 added = 0; 448 sq->last_time = sq->samples[0]; 449 sq->last_delta = 0; 450 sq->last_delta2 = 0; 451 452 /* 453 * Prime the values by adding in the first 4 samples in. This 454 * should completely initialize the delta calculations. 455 */ 456 for (ns = 0; ns < 4; ns++) 457 (void)estimate_entropy(sq, sq->samples[ns]); 458 459 for (ns = 4; ns < sq->nsamples; ns++) 460 added += estimate_entropy(sq, sq->samples[ns]); 461 462 entropypool_adddata(ent, sq->samples, sq->nsamples * 4, added); 463 entropypool_adddata(ent, sq->extra, sq->nsamples * 4, 0); 464 465 /* 466 * Move the last 4 samples into the first 4 positions, and start 467 * adding new samples from that point. 468 */ 469 for (ns = 0; ns < 4; ns++) { 470 sq->samples[ns] = sq->samples[sq->nsamples - 4 + ns]; 471 sq->extra[ns] = sq->extra[sq->nsamples - 4 + ns]; 472 } 473 474 sq->nsamples = 4; 475 476 return (added); 477} 478 479static unsigned int 480get_from_callback(isc_entropysource_t *source, unsigned int desired, 481 isc_boolean_t blocking) 482{ 483 isc_entropy_t *ent = source->ent; 484 isc_cbsource_t *cbs = &source->sources.callback; 485 unsigned int added; 486 unsigned int got; 487 isc_result_t result; 488 489 if (desired == 0) 490 return (0); 491 492 if (source->bad) 493 return (0); 494 495 if (!cbs->start_called && cbs->startfunc != NULL) { 496 result = cbs->startfunc(source, cbs->arg, blocking); 497 if (result != ISC_R_SUCCESS) 498 return (0); 499 cbs->start_called = ISC_TRUE; 500 } 501 502 added = 0; 503 result = ISC_R_SUCCESS; 504 while (desired > 0 && result == ISC_R_SUCCESS) { 505 result = cbs->getfunc(source, cbs->arg, blocking); 506 if (result == ISC_R_QUEUEFULL) { 507 got = crunchsamples(ent, &cbs->samplequeue); 508 added += got; 509 desired -= ISC_MIN(got, desired); 510 result = ISC_R_SUCCESS; 511 } else if (result != ISC_R_SUCCESS && 512 result != ISC_R_NOTBLOCKING) 513 source->bad = ISC_TRUE; 514 515 } 516 517 return (added); 518} 519 520/* 521 * Extract some number of bytes from the random pool, decreasing the 522 * estimate of randomness as each byte is extracted. 523 * 524 * Do this by stiring the pool and returning a part of hash as randomness. 525 * Note that no secrets are given away here since parts of the hash are 526 * xored together before returned. 527 * 528 * Honor the request from the caller to only return good data, any data, 529 * etc. 530 */ 531isc_result_t 532isc_entropy_getdata(isc_entropy_t *ent, void *data, unsigned int length, 533 unsigned int *returned, unsigned int flags) 534{ 535 unsigned int i; 536 isc_sha1_t hash; 537 unsigned char digest[ISC_SHA1_DIGESTLENGTH]; 538 isc_uint32_t remain, deltae, count, total; 539 isc_uint8_t *buf; 540 isc_boolean_t goodonly, partial, blocking; 541 542 REQUIRE(VALID_ENTROPY(ent)); 543 REQUIRE(data != NULL); 544 REQUIRE(length > 0); 545 546 goodonly = ISC_TF((flags & ISC_ENTROPY_GOODONLY) != 0); 547 partial = ISC_TF((flags & ISC_ENTROPY_PARTIAL) != 0); 548 blocking = ISC_TF((flags & ISC_ENTROPY_BLOCKING) != 0); 549 550 REQUIRE(!partial || returned != NULL); 551 552 LOCK(&ent->lock); 553 554 remain = length; 555 buf = data; 556 total = 0; 557 while (remain != 0) { 558 count = ISC_MIN(remain, RND_ENTROPY_THRESHOLD); 559 560 /* 561 * If we are extracting good data only, make certain we 562 * have enough data in our pool for this pass. If we don't, 563 * get some, and fail if we can't, and partial returns 564 * are not ok. 565 */ 566 if (goodonly) { 567 unsigned int fillcount; 568 569 fillcount = ISC_MAX(remain * 8, count * 8); 570 571 /* 572 * If, however, we have at least THRESHOLD_BITS 573 * of entropy in the pool, don't block here. It is 574 * better to drain the pool once in a while and 575 * then refill it than it is to constantly keep the 576 * pool full. 577 */ 578 if (ent->pool.entropy >= THRESHOLD_BITS) 579 fillpool(ent, fillcount, ISC_FALSE); 580 else 581 fillpool(ent, fillcount, blocking); 582 583 /* 584 * Verify that we got enough entropy to do one 585 * extraction. If we didn't, bail. 586 */ 587 if (ent->pool.entropy < THRESHOLD_BITS) { 588 if (!partial) 589 goto zeroize; 590 else 591 goto partial_output; 592 } 593 } else { 594 /* 595 * If we've extracted half our pool size in bits 596 * since the last refresh, try to refresh here. 597 */ 598 if (ent->initialized < THRESHOLD_BITS) 599 fillpool(ent, THRESHOLD_BITS, blocking); 600 else 601 fillpool(ent, 0, ISC_FALSE); 602 603 /* 604 * If we've not initialized with enough good random 605 * data, seed with our crappy code. 606 */ 607 if (ent->initialized < THRESHOLD_BITS) 608 reseed(ent); 609 } 610 611 isc_sha1_init(&hash); 612 isc_sha1_update(&hash, (void *)(ent->pool.pool), 613 RND_POOLBYTES); 614 isc_sha1_final(&hash, digest); 615 616 /* 617 * Stir the extracted data (all of it) back into the pool. 618 */ 619 entropypool_adddata(ent, digest, ISC_SHA1_DIGESTLENGTH, 0); 620 621 for (i = 0; i < count; i++) 622 buf[i] = digest[i] ^ digest[i + RND_ENTROPY_THRESHOLD]; 623 624 buf += count; 625 remain -= count; 626 627 deltae = count * 8; 628 deltae = ISC_MIN(deltae, ent->pool.entropy); 629 total += deltae; 630 subtract_entropy(ent, deltae); 631 add_pseudo(ent, count * 8); 632 } 633 634 partial_output: 635 memset(digest, 0, sizeof(digest)); 636 637 if (returned != NULL) 638 *returned = (length - remain); 639 640 UNLOCK(&ent->lock); 641 642 return (ISC_R_SUCCESS); 643 644 zeroize: 645 /* put the entropy we almost extracted back */ 646 add_entropy(ent, total); 647 memset(data, 0, length); 648 memset(digest, 0, sizeof(digest)); 649 if (returned != NULL) 650 *returned = 0; 651 652 UNLOCK(&ent->lock); 653 654 return (ISC_R_NOENTROPY); 655} 656 657static void 658isc_entropypool_init(isc_entropypool_t *pool) { 659 pool->cursor = RND_POOLWORDS - 1; 660 pool->entropy = 0; 661 pool->pseudo = 0; 662 pool->rotate = 0; 663 memset(pool->pool, 0, RND_POOLBYTES); 664} 665 666static void 667isc_entropypool_invalidate(isc_entropypool_t *pool) { 668 pool->cursor = 0; 669 pool->entropy = 0; 670 pool->pseudo = 0; 671 pool->rotate = 0; 672 memset(pool->pool, 0, RND_POOLBYTES); 673} 674 675isc_result_t 676isc_entropy_create(isc_mem_t *mctx, isc_entropy_t **entp) { 677 isc_result_t result; 678 isc_entropy_t *ent; 679 680 REQUIRE(mctx != NULL); 681 REQUIRE(entp != NULL && *entp == NULL); 682 683 ent = isc_mem_get(mctx, sizeof(isc_entropy_t)); 684 if (ent == NULL) 685 return (ISC_R_NOMEMORY); 686 687 /* 688 * We need a lock. 689 */ 690 result = isc_mutex_init(&ent->lock); 691 if (result != ISC_R_SUCCESS) 692 goto errout; 693 694 /* 695 * From here down, no failures will/can occur. 696 */ 697 ISC_LIST_INIT(ent->sources); 698 ent->nextsource = NULL; 699 ent->nsources = 0; 700 ent->mctx = NULL; 701 isc_mem_attach(mctx, &ent->mctx); 702 ent->refcnt = 1; 703 ent->initialized = 0; 704 ent->initcount = 0; 705 ent->magic = ENTROPY_MAGIC; 706 707 isc_entropypool_init(&ent->pool); 708 709 *entp = ent; 710 return (ISC_R_SUCCESS); 711 712 errout: 713 isc_mem_put(mctx, ent, sizeof(isc_entropy_t)); 714 715 return (result); 716} 717 718/*! 719 * Requires "ent" be locked. 720 */ 721static void 722destroysource(isc_entropysource_t **sourcep) { 723 isc_entropysource_t *source; 724 isc_entropy_t *ent; 725 isc_cbsource_t *cbs; 726 727 source = *sourcep; 728 *sourcep = NULL; 729 ent = source->ent; 730 731 ISC_LIST_UNLINK(ent->sources, source, link); 732 ent->nextsource = NULL; 733 REQUIRE(ent->nsources > 0); 734 ent->nsources--; 735 736 switch (source->type) { 737 case ENTROPY_SOURCETYPE_FILE: 738 if (! source->bad) 739 destroyfilesource(&source->sources.file); 740 break; 741 case ENTROPY_SOURCETYPE_USOCKET: 742 if (! source->bad) 743 destroyusocketsource(&source->sources.usocket); 744 break; 745 case ENTROPY_SOURCETYPE_SAMPLE: 746 samplequeue_release(ent, &source->sources.sample.samplequeue); 747 break; 748 case ENTROPY_SOURCETYPE_CALLBACK: 749 cbs = &source->sources.callback; 750 if (cbs->start_called && cbs->stopfunc != NULL) { 751 cbs->stopfunc(source, cbs->arg); 752 cbs->start_called = ISC_FALSE; 753 } 754 samplequeue_release(ent, &cbs->samplequeue); 755 break; 756 } 757 758 memset(source, 0, sizeof(isc_entropysource_t)); 759 760 isc_mem_put(ent->mctx, source, sizeof(isc_entropysource_t)); 761} 762 763static inline isc_boolean_t 764destroy_check(isc_entropy_t *ent) { 765 isc_entropysource_t *source; 766 767 if (ent->refcnt > 0) 768 return (ISC_FALSE); 769 770 source = ISC_LIST_HEAD(ent->sources); 771 while (source != NULL) { 772 switch (source->type) { 773 case ENTROPY_SOURCETYPE_FILE: 774 case ENTROPY_SOURCETYPE_USOCKET: 775 break; 776 default: 777 return (ISC_FALSE); 778 } 779 source = ISC_LIST_NEXT(source, link); 780 } 781 782 return (ISC_TRUE); 783} 784 785static void 786destroy(isc_entropy_t **entp) { 787 isc_entropy_t *ent; 788 isc_entropysource_t *source; 789 isc_mem_t *mctx; 790 791 REQUIRE(entp != NULL && *entp != NULL); 792 ent = *entp; 793 *entp = NULL; 794 795 LOCK(&ent->lock); 796 797 REQUIRE(ent->refcnt == 0); 798 799 /* 800 * Here, detach non-sample sources. 801 */ 802 source = ISC_LIST_HEAD(ent->sources); 803 while (source != NULL) { 804 switch(source->type) { 805 case ENTROPY_SOURCETYPE_FILE: 806 case ENTROPY_SOURCETYPE_USOCKET: 807 destroysource(&source); 808 break; 809 } 810 source = ISC_LIST_HEAD(ent->sources); 811 } 812 813 /* 814 * If there are other types of sources, we've found a bug. 815 */ 816 REQUIRE(ISC_LIST_EMPTY(ent->sources)); 817 818 mctx = ent->mctx; 819 820 isc_entropypool_invalidate(&ent->pool); 821 822 UNLOCK(&ent->lock); 823 824 DESTROYLOCK(&ent->lock); 825 826 memset(ent, 0, sizeof(isc_entropy_t)); 827 isc_mem_put(mctx, ent, sizeof(isc_entropy_t)); 828 isc_mem_detach(&mctx); 829} 830 831void 832isc_entropy_destroysource(isc_entropysource_t **sourcep) { 833 isc_entropysource_t *source; 834 isc_entropy_t *ent; 835 isc_boolean_t killit; 836 837 REQUIRE(sourcep != NULL); 838 REQUIRE(VALID_SOURCE(*sourcep)); 839 840 source = *sourcep; 841 *sourcep = NULL; 842 843 ent = source->ent; 844 REQUIRE(VALID_ENTROPY(ent)); 845 846 LOCK(&ent->lock); 847 848 destroysource(&source); 849 850 killit = destroy_check(ent); 851 852 UNLOCK(&ent->lock); 853 854 if (killit) 855 destroy(&ent); 856} 857 858isc_result_t 859isc_entropy_createcallbacksource(isc_entropy_t *ent, 860 isc_entropystart_t start, 861 isc_entropyget_t get, 862 isc_entropystop_t stop, 863 void *arg, 864 isc_entropysource_t **sourcep) 865{ 866 isc_result_t result; 867 isc_entropysource_t *source; 868 isc_cbsource_t *cbs; 869 870 REQUIRE(VALID_ENTROPY(ent)); 871 REQUIRE(get != NULL); 872 REQUIRE(sourcep != NULL && *sourcep == NULL); 873 874 LOCK(&ent->lock); 875 876 source = isc_mem_get(ent->mctx, sizeof(isc_entropysource_t)); 877 if (source == NULL) { 878 result = ISC_R_NOMEMORY; 879 goto errout; 880 } 881 source->bad = ISC_FALSE; 882 883 cbs = &source->sources.callback; 884 885 result = samplesource_allocate(ent, &cbs->samplequeue); 886 if (result != ISC_R_SUCCESS) 887 goto errout; 888 889 cbs->start_called = ISC_FALSE; 890 cbs->startfunc = start; 891 cbs->getfunc = get; 892 cbs->stopfunc = stop; 893 cbs->arg = arg; 894 895 /* 896 * From here down, no failures can occur. 897 */ 898 source->magic = SOURCE_MAGIC; 899 source->type = ENTROPY_SOURCETYPE_CALLBACK; 900 source->ent = ent; 901 source->total = 0; 902 memset(source->name, 0, sizeof(source->name)); 903 ISC_LINK_INIT(source, link); 904 905 /* 906 * Hook it into the entropy system. 907 */ 908 ISC_LIST_APPEND(ent->sources, source, link); 909 ent->nsources++; 910 911 *sourcep = source; 912 913 UNLOCK(&ent->lock); 914 return (ISC_R_SUCCESS); 915 916 errout: 917 if (source != NULL) 918 isc_mem_put(ent->mctx, source, sizeof(isc_entropysource_t)); 919 920 UNLOCK(&ent->lock); 921 922 return (result); 923} 924 925void 926isc_entropy_stopcallbacksources(isc_entropy_t *ent) { 927 isc_entropysource_t *source; 928 isc_cbsource_t *cbs; 929 930 REQUIRE(VALID_ENTROPY(ent)); 931 932 LOCK(&ent->lock); 933 934 source = ISC_LIST_HEAD(ent->sources); 935 while (source != NULL) { 936 if (source->type == ENTROPY_SOURCETYPE_CALLBACK) { 937 cbs = &source->sources.callback; 938 if (cbs->start_called && cbs->stopfunc != NULL) { 939 cbs->stopfunc(source, cbs->arg); 940 cbs->start_called = ISC_FALSE; 941 } 942 } 943 944 source = ISC_LIST_NEXT(source, link); 945 } 946 947 UNLOCK(&ent->lock); 948} 949 950isc_result_t 951isc_entropy_createsamplesource(isc_entropy_t *ent, 952 isc_entropysource_t **sourcep) 953{ 954 isc_result_t result; 955 isc_entropysource_t *source; 956 sample_queue_t *sq; 957 958 REQUIRE(VALID_ENTROPY(ent)); 959 REQUIRE(sourcep != NULL && *sourcep == NULL); 960 961 LOCK(&ent->lock); 962 963 source = isc_mem_get(ent->mctx, sizeof(isc_entropysource_t)); 964 if (source == NULL) { 965 result = ISC_R_NOMEMORY; 966 goto errout; 967 } 968 969 sq = &source->sources.sample.samplequeue; 970 result = samplesource_allocate(ent, sq); 971 if (result != ISC_R_SUCCESS) 972 goto errout; 973 974 /* 975 * From here down, no failures can occur. 976 */ 977 source->magic = SOURCE_MAGIC; 978 source->type = ENTROPY_SOURCETYPE_SAMPLE; 979 source->ent = ent; 980 source->total = 0; 981 memset(source->name, 0, sizeof(source->name)); 982 ISC_LINK_INIT(source, link); 983 984 /* 985 * Hook it into the entropy system. 986 */ 987 ISC_LIST_APPEND(ent->sources, source, link); 988 ent->nsources++; 989 990 *sourcep = source; 991 992 UNLOCK(&ent->lock); 993 return (ISC_R_SUCCESS); 994 995 errout: 996 if (source != NULL) 997 isc_mem_put(ent->mctx, source, sizeof(isc_entropysource_t)); 998 999 UNLOCK(&ent->lock); 1000 1001 return (result); 1002} 1003 1004/*! 1005 * Add a sample, and return ISC_R_SUCCESS if the queue has become full, 1006 * ISC_R_NOENTROPY if it has space remaining, and ISC_R_NOMORE if the 1007 * queue was full when this function was called. 1008 */ 1009static isc_result_t 1010addsample(sample_queue_t *sq, isc_uint32_t sample, isc_uint32_t extra) { 1011 if (sq->nsamples >= RND_EVENTQSIZE) 1012 return (ISC_R_NOMORE); 1013 1014 sq->samples[sq->nsamples] = sample; 1015 sq->extra[sq->nsamples] = extra; 1016 sq->nsamples++; 1017 1018 if (sq->nsamples >= RND_EVENTQSIZE) 1019 return (ISC_R_QUEUEFULL); 1020 1021 return (ISC_R_SUCCESS); 1022} 1023 1024isc_result_t 1025isc_entropy_addsample(isc_entropysource_t *source, isc_uint32_t sample, 1026 isc_uint32_t extra) 1027{ 1028 isc_entropy_t *ent; 1029 sample_queue_t *sq; 1030 unsigned int entropy; 1031 isc_result_t result; 1032 1033 REQUIRE(VALID_SOURCE(source)); 1034 1035 ent = source->ent; 1036 1037 LOCK(&ent->lock); 1038 1039 sq = &source->sources.sample.samplequeue; 1040 result = addsample(sq, sample, extra); 1041 if (result == ISC_R_QUEUEFULL) { 1042 entropy = crunchsamples(ent, sq); 1043 add_entropy(ent, entropy); 1044 } 1045 1046 UNLOCK(&ent->lock); 1047 1048 return (result); 1049} 1050 1051isc_result_t 1052isc_entropy_addcallbacksample(isc_entropysource_t *source, isc_uint32_t sample, 1053 isc_uint32_t extra) 1054{ 1055 sample_queue_t *sq; 1056 isc_result_t result; 1057 1058 REQUIRE(VALID_SOURCE(source)); 1059 REQUIRE(source->type == ENTROPY_SOURCETYPE_CALLBACK); 1060 1061 sq = &source->sources.callback.samplequeue; 1062 result = addsample(sq, sample, extra); 1063 1064 return (result); 1065} 1066 1067void 1068isc_entropy_putdata(isc_entropy_t *ent, void *data, unsigned int length, 1069 isc_uint32_t entropy) 1070{ 1071 REQUIRE(VALID_ENTROPY(ent)); 1072 1073 LOCK(&ent->lock); 1074 1075 entropypool_adddata(ent, data, length, entropy); 1076 1077 if (ent->initialized < THRESHOLD_BITS) 1078 ent->initialized = THRESHOLD_BITS; 1079 1080 UNLOCK(&ent->lock); 1081} 1082 1083static void 1084dumpstats(isc_entropy_t *ent, FILE *out) { 1085 fprintf(out, 1086 isc_msgcat_get(isc_msgcat, ISC_MSGSET_ENTROPY, 1087 ISC_MSG_ENTROPYSTATS, 1088 "Entropy pool %p: refcnt %u cursor %u," 1089 " rotate %u entropy %u pseudo %u nsources %u" 1090 " nextsource %p initialized %u initcount %u\n"), 1091 ent, ent->refcnt, 1092 ent->pool.cursor, ent->pool.rotate, 1093 ent->pool.entropy, ent->pool.pseudo, 1094 ent->nsources, ent->nextsource, ent->initialized, 1095 ent->initcount); 1096} 1097 1098/* 1099 * This function ignores locking. Use at your own risk. 1100 */ 1101void 1102isc_entropy_stats(isc_entropy_t *ent, FILE *out) { 1103 REQUIRE(VALID_ENTROPY(ent)); 1104 1105 LOCK(&ent->lock); 1106 dumpstats(ent, out); 1107 UNLOCK(&ent->lock); 1108} 1109 1110unsigned int 1111isc_entropy_status(isc_entropy_t *ent) { 1112 unsigned int estimate; 1113 1114 LOCK(&ent->lock); 1115 estimate = ent->pool.entropy; 1116 UNLOCK(&ent->lock); 1117 1118 return estimate; 1119} 1120 1121void 1122isc_entropy_attach(isc_entropy_t *ent, isc_entropy_t **entp) { 1123 REQUIRE(VALID_ENTROPY(ent)); 1124 REQUIRE(entp != NULL && *entp == NULL); 1125 1126 LOCK(&ent->lock); 1127 1128 ent->refcnt++; 1129 *entp = ent; 1130 1131 UNLOCK(&ent->lock); 1132} 1133 1134void 1135isc_entropy_detach(isc_entropy_t **entp) { 1136 isc_entropy_t *ent; 1137 isc_boolean_t killit; 1138 1139 REQUIRE(entp != NULL && VALID_ENTROPY(*entp)); 1140 ent = *entp; 1141 *entp = NULL; 1142 1143 LOCK(&ent->lock); 1144 1145 REQUIRE(ent->refcnt > 0); 1146 ent->refcnt--; 1147 1148 killit = destroy_check(ent); 1149 1150 UNLOCK(&ent->lock); 1151 1152 if (killit) 1153 destroy(&ent); 1154} 1155 1156static isc_result_t 1157kbdstart(isc_entropysource_t *source, void *arg, isc_boolean_t blocking) { 1158 /* 1159 * The intent of "first" is to provide a warning message only once 1160 * during the run of a program that might try to gather keyboard 1161 * entropy multiple times. 1162 */ 1163 static isc_boolean_t first = ISC_TRUE; 1164 1165 UNUSED(arg); 1166 1167 if (! blocking) 1168 return (ISC_R_NOENTROPY); 1169 1170 if (first) { 1171 if (source->warn_keyboard) 1172 fprintf(stderr, "You must use the keyboard to create " 1173 "entropy, since your system is lacking\n" 1174 "/dev/random (or equivalent)\n\n"); 1175 first = ISC_FALSE; 1176 } 1177 fprintf(stderr, "start typing:\n"); 1178 1179 return (isc_keyboard_open(&source->kbd)); 1180} 1181 1182static void 1183kbdstop(isc_entropysource_t *source, void *arg) { 1184 1185 UNUSED(arg); 1186 1187 if (! isc_keyboard_canceled(&source->kbd)) 1188 fprintf(stderr, "stop typing.\r\n"); 1189 1190 (void)isc_keyboard_close(&source->kbd, 3); 1191} 1192 1193static isc_result_t 1194kbdget(isc_entropysource_t *source, void *arg, isc_boolean_t blocking) { 1195 isc_result_t result; 1196 isc_time_t t; 1197 isc_uint32_t sample; 1198 isc_uint32_t extra; 1199 unsigned char c; 1200 1201 UNUSED(arg); 1202 1203 if (!blocking) 1204 return (ISC_R_NOTBLOCKING); 1205 1206 result = isc_keyboard_getchar(&source->kbd, &c); 1207 if (result != ISC_R_SUCCESS) 1208 return (result); 1209 1210 TIME_NOW(&t); 1211 1212 sample = isc_time_nanoseconds(&t); 1213 extra = c; 1214 1215 result = isc_entropy_addcallbacksample(source, sample, extra); 1216 if (result != ISC_R_SUCCESS) { 1217 fprintf(stderr, "\r\n"); 1218 return (result); 1219 } 1220 1221 fprintf(stderr, "."); 1222 fflush(stderr); 1223 1224 return (result); 1225} 1226 1227isc_result_t 1228isc_entropy_usebestsource(isc_entropy_t *ectx, isc_entropysource_t **source, 1229 const char *randomfile, int use_keyboard) 1230{ 1231 isc_result_t result; 1232 isc_result_t final_result = ISC_R_NOENTROPY; 1233 isc_boolean_t userfile = ISC_TRUE; 1234 1235 REQUIRE(VALID_ENTROPY(ectx)); 1236 REQUIRE(source != NULL && *source == NULL); 1237 REQUIRE(use_keyboard == ISC_ENTROPY_KEYBOARDYES || 1238 use_keyboard == ISC_ENTROPY_KEYBOARDNO || 1239 use_keyboard == ISC_ENTROPY_KEYBOARDMAYBE); 1240 1241#ifdef PATH_RANDOMDEV 1242 if (randomfile == NULL) { 1243 randomfile = PATH_RANDOMDEV; 1244 userfile = ISC_FALSE; 1245 } 1246#endif 1247 1248 if (randomfile != NULL && use_keyboard != ISC_ENTROPY_KEYBOARDYES) { 1249 result = isc_entropy_createfilesource(ectx, randomfile); 1250 if (result == ISC_R_SUCCESS && 1251 use_keyboard == ISC_ENTROPY_KEYBOARDMAYBE) 1252 use_keyboard = ISC_ENTROPY_KEYBOARDNO; 1253 if (result != ISC_R_SUCCESS && userfile) 1254 return (result); 1255 1256 final_result = result; 1257 } 1258 1259 if (use_keyboard != ISC_ENTROPY_KEYBOARDNO) { 1260 result = isc_entropy_createcallbacksource(ectx, kbdstart, 1261 kbdget, kbdstop, 1262 NULL, source); 1263 if (result == ISC_R_SUCCESS) 1264 (*source)->warn_keyboard = 1265 ISC_TF(use_keyboard == 1266 ISC_ENTROPY_KEYBOARDMAYBE); 1267 1268 if (final_result != ISC_R_SUCCESS) 1269 final_result = result; 1270 } 1271 1272 /* 1273 * final_result is ISC_R_SUCCESS if at least one source of entropy 1274 * could be started, otherwise it is the error from the most recently 1275 * failed operation (or ISC_R_NOENTROPY if PATH_RANDOMDEV is not 1276 * defined and use_keyboard is ISC_ENTROPY_KEYBOARDNO). 1277 */ 1278 return (final_result); 1279} 1280