Index: head/sys/dev/random/fortuna.c =================================================================== --- head/sys/dev/random/fortuna.c (revision 298592) +++ head/sys/dev/random/fortuna.c (revision 298593) @@ -1,422 +1,422 @@ /*- * Copyright (c) 2013-2015 Mark R V Murray * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer * in this position and unchanged. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * */ /* * This implementation of Fortuna is based on the descriptions found in * ISBN 978-0-470-47424-2 "Cryptography Engineering" by Ferguson, Schneier * and Kohno ("FS&K"). */ #include __FBSDID("$FreeBSD$"); #include #ifdef _KERNEL #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #else /* !_KERNEL */ #include #include #include #include #include #include #include "unit_test.h" #include #include #include #include #include #include #endif /* _KERNEL */ /* Defined in FS&K */ #define RANDOM_FORTUNA_NPOOLS 32 /* The number of accumulation pools */ #define RANDOM_FORTUNA_DEFPOOLSIZE 64 /* The default pool size/length for a (re)seed */ #define RANDOM_FORTUNA_MAX_READ (1 << 20) /* Max bytes in a single read */ /* * The allowable range of RANDOM_FORTUNA_DEFPOOLSIZE. The default value is above. * Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds, * and too small may compromise initial security but get faster reseeds. */ #define RANDOM_FORTUNA_MINPOOLSIZE 16 #define RANDOM_FORTUNA_MAXPOOLSIZE UINT_MAX CTASSERT(RANDOM_FORTUNA_MINPOOLSIZE <= RANDOM_FORTUNA_DEFPOOLSIZE); CTASSERT(RANDOM_FORTUNA_DEFPOOLSIZE <= RANDOM_FORTUNA_MAXPOOLSIZE); /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */ CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t)); CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE); /* Probes for dtrace(1) */ SDT_PROVIDER_DECLARE(random); SDT_PROVIDER_DEFINE(random); SDT_PROBE_DEFINE2(random, fortuna, event_processor, debug, "u_int", "struct fs_pool *"); /* * This is the beastie that needs protecting. It contains all of the * state that we are excited about. Exactly one is instantiated. */ static struct fortuna_state { struct fs_pool { /* P_i */ u_int fsp_length; /* Only the first one is used by Fortuna */ struct randomdev_hash fsp_hash; } fs_pool[RANDOM_FORTUNA_NPOOLS]; u_int fs_reseedcount; /* ReseedCnt */ uint128_t fs_counter; /* C */ struct randomdev_key fs_key; /* K */ u_int fs_minpoolsize; /* Extras */ /* Extras for the OS */ #ifdef _KERNEL /* For use when 'pacing' the reseeds */ sbintime_t fs_lasttime; #endif /* Reseed lock */ mtx_t fs_mtx; } fortuna_state; #ifdef _KERNEL static struct sysctl_ctx_list random_clist; RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE); #else static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE]; #endif static void random_fortuna_pre_read(void); static void random_fortuna_read(uint8_t *, u_int); static bool random_fortuna_seeded(void); static void random_fortuna_process_event(struct harvest_event *); static void random_fortuna_init_alg(void *); static void random_fortuna_deinit_alg(void *); static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount); struct random_algorithm random_alg_context = { .ra_ident = "Fortuna", .ra_init_alg = random_fortuna_init_alg, .ra_deinit_alg = random_fortuna_deinit_alg, .ra_pre_read = random_fortuna_pre_read, .ra_read = random_fortuna_read, .ra_seeded = random_fortuna_seeded, .ra_event_processor = random_fortuna_process_event, .ra_poolcount = RANDOM_FORTUNA_NPOOLS, }; /* ARGSUSED */ static void random_fortuna_init_alg(void *unused __unused) { int i; #ifdef _KERNEL struct sysctl_oid *random_fortuna_o; #endif RANDOM_RESEED_INIT_LOCK(); /* * Fortuna parameters. Do not adjust these unless you have * have a very good clue about what they do! */ fortuna_state.fs_minpoolsize = RANDOM_FORTUNA_DEFPOOLSIZE; #ifdef _KERNEL fortuna_state.fs_lasttime = 0; random_fortuna_o = SYSCTL_ADD_NODE(&random_clist, SYSCTL_STATIC_CHILDREN(_kern_random), OID_AUTO, "fortuna", CTLFLAG_RW, 0, "Fortuna Parameters"); SYSCTL_ADD_PROC(&random_clist, SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO, "minpoolsize", CTLTYPE_UINT | CTLFLAG_RWTUN, &fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE, random_check_uint_fs_minpoolsize, "IU", "Minimum pool size necessary to cause a reseed"); KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup")); #endif /*- * FS&K - InitializePRNG() * - P_i = \epsilon * - ReseedCNT = 0 */ for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) { randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash); fortuna_state.fs_pool[i].fsp_length = 0; } fortuna_state.fs_reseedcount = 0; /*- * FS&K - InitializeGenerator() * - C = 0 * - K = 0 */ fortuna_state.fs_counter = UINT128_ZERO; explicit_bzero(&fortuna_state.fs_key, sizeof(fortuna_state.fs_key)); } /* ARGSUSED */ static void random_fortuna_deinit_alg(void *unused __unused) { RANDOM_RESEED_DEINIT_LOCK(); explicit_bzero(&fortuna_state, sizeof(fortuna_state)); #ifdef _KERNEL sysctl_ctx_free(&random_clist); #endif } /*- * FS&K - AddRandomEvent() * Process a single stochastic event off the harvest queue */ static void random_fortuna_process_event(struct harvest_event *event) { u_int pl; RANDOM_RESEED_LOCK(); /*- * FS&K - P_i = P_i| * Accumulate the event into the appropriate pool * where each event carries the destination information. * * The hash_init() and hash_finish() calls are done in * random_fortuna_pre_read(). * * We must be locked against pool state modification which can happen * during accumulation/reseeding and reading/regating. */ pl = event->he_destination % RANDOM_FORTUNA_NPOOLS; randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash, event, sizeof(*event)); /*- * Don't wrap the length. Doing the the hard way so as not to wrap at MAXUINT. * This is a "saturating" add. * XXX: FIX!!: We don't actually need lengths for anything but fs_pool[0], * but it's been useful debugging to see them all. */ if (RANDOM_FORTUNA_MAXPOOLSIZE - fortuna_state.fs_pool[pl].fsp_length > event->he_size) fortuna_state.fs_pool[pl].fsp_length += event->he_size; else fortuna_state.fs_pool[pl].fsp_length = RANDOM_FORTUNA_MAXPOOLSIZE; explicit_bzero(event, sizeof(*event)); RANDOM_RESEED_UNLOCK(); } /*- * FS&K - Reseed() * This introduces new key material into the output generator. * Additionaly it increments the output generator's counter * variable C. When C > 0, the output generator is seeded and * will deliver output. * The entropy_data buffer passed is a very specific size; the * product of RANDOM_FORTUNA_NPOOLS and RANDOM_KEYSIZE. */ static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount) { struct randomdev_hash context; uint8_t hash[RANDOM_KEYSIZE]; RANDOM_RESEED_ASSERT_LOCK_OWNED(); /*- * FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m)) * - C = C + 1 */ randomdev_hash_init(&context); randomdev_hash_iterate(&context, zero_region, RANDOM_ZERO_BLOCKSIZE); randomdev_hash_iterate(&context, &fortuna_state.fs_key, sizeof(fortuna_state.fs_key)); randomdev_hash_iterate(&context, entropy_data, RANDOM_KEYSIZE*blockcount); randomdev_hash_finish(&context, hash); randomdev_hash_init(&context); randomdev_hash_iterate(&context, hash, RANDOM_KEYSIZE); randomdev_hash_finish(&context, hash); randomdev_encrypt_init(&fortuna_state.fs_key, hash); explicit_bzero(hash, sizeof(hash)); /* Unblock the device if this is the first time we are reseeding. */ if (uint128_is_zero(fortuna_state.fs_counter)) randomdev_unblock(); uint128_increment(&fortuna_state.fs_counter); } /*- * FS&K - GenerateBlocks() * Generate a number of complete blocks of random output. */ static __inline void random_fortuna_genblocks(uint8_t *buf, u_int blockcount) { u_int i; RANDOM_RESEED_ASSERT_LOCK_OWNED(); for (i = 0; i < blockcount; i++) { /*- * FS&K - r = r|E(K,C) * - C = C + 1 */ randomdev_encrypt(&fortuna_state.fs_key, &fortuna_state.fs_counter, buf, RANDOM_BLOCKSIZE); buf += RANDOM_BLOCKSIZE; uint128_increment(&fortuna_state.fs_counter); } } /*- * FS&K - PseudoRandomData() * This generates no more than 2^20 bytes of data, and cleans up its * internal state when finished. It is assumed that a whole number of * blocks are available for writing; any excess generated will be * ignored. */ static __inline void random_fortuna_genrandom(uint8_t *buf, u_int bytecount) { static uint8_t temp[RANDOM_BLOCKSIZE*(RANDOM_KEYS_PER_BLOCK)]; u_int blockcount; RANDOM_RESEED_ASSERT_LOCK_OWNED(); /*- * FS&K - assert(n < 2^20 (== 1 MB) * - r = first-n-bytes(GenerateBlocks(ceil(n/16))) * - K = GenerateBlocks(2) */ KASSERT((bytecount <= RANDOM_FORTUNA_MAX_READ), ("invalid single read request to Fortuna of %d bytes", bytecount)); - blockcount = (bytecount + RANDOM_BLOCKSIZE - 1)/RANDOM_BLOCKSIZE; + blockcount = howmany(bytecount, RANDOM_BLOCKSIZE); random_fortuna_genblocks(buf, blockcount); random_fortuna_genblocks(temp, RANDOM_KEYS_PER_BLOCK); randomdev_encrypt_init(&fortuna_state.fs_key, temp); explicit_bzero(temp, sizeof(temp)); } /*- * FS&K - RandomData() (Part 1) * Used to return processed entropy from the PRNG. There is a pre_read * required to be present (but it can be a stub) in order to allow * specific actions at the begin of the read. */ void random_fortuna_pre_read(void) { #ifdef _KERNEL sbintime_t now; #endif struct randomdev_hash context; uint32_t s[RANDOM_FORTUNA_NPOOLS*RANDOM_KEYSIZE_WORDS]; uint8_t temp[RANDOM_KEYSIZE]; u_int i; KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0")); #ifdef _KERNEL /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */ now = getsbinuptime(); #endif RANDOM_RESEED_LOCK(); if (fortuna_state.fs_pool[0].fsp_length >= fortuna_state.fs_minpoolsize #ifdef _KERNEL /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */ && (now - fortuna_state.fs_lasttime > hz/10) #endif ) { #ifdef _KERNEL fortuna_state.fs_lasttime = now; #endif /* FS&K - ReseedCNT = ReseedCNT + 1 */ fortuna_state.fs_reseedcount++; /* s = \epsilon at start */ for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) { /* FS&K - if Divides(ReseedCnt, 2^i) ... */ if ((fortuna_state.fs_reseedcount % (1 << i)) == 0) { /*- * FS&K - temp = (P_i) * - P_i = \epsilon * - s = s|H(temp) */ randomdev_hash_finish(&fortuna_state.fs_pool[i].fsp_hash, temp); randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash); fortuna_state.fs_pool[i].fsp_length = 0; randomdev_hash_init(&context); randomdev_hash_iterate(&context, temp, RANDOM_KEYSIZE); randomdev_hash_finish(&context, s + i*RANDOM_KEYSIZE_WORDS); } else break; } SDT_PROBE2(random, fortuna, event_processor, debug, fortuna_state.fs_reseedcount, fortuna_state.fs_pool); /* FS&K */ random_fortuna_reseed_internal(s, i < RANDOM_FORTUNA_NPOOLS ? i + 1 : RANDOM_FORTUNA_NPOOLS); /* Clean up and secure */ explicit_bzero(s, sizeof(s)); explicit_bzero(temp, sizeof(temp)); explicit_bzero(&context, sizeof(context)); } RANDOM_RESEED_UNLOCK(); } /*- * FS&K - RandomData() (Part 2) * Main read from Fortuna, continued. May be called multiple times after * the random_fortuna_pre_read() above. * The supplied buf MUST be a multiple of RANDOM_BLOCKSIZE in size. * Lots of code presumes this for efficiency, both here and in other * routines. You are NOT allowed to break this! */ void random_fortuna_read(uint8_t *buf, u_int bytecount) { KASSERT((bytecount % RANDOM_BLOCKSIZE) == 0, ("%s(): bytecount (= %d) must be a multiple of %d", __func__, bytecount, RANDOM_BLOCKSIZE )); RANDOM_RESEED_LOCK(); random_fortuna_genrandom(buf, bytecount); RANDOM_RESEED_UNLOCK(); } bool random_fortuna_seeded(void) { return (!uint128_is_zero(fortuna_state.fs_counter)); } Index: head/sys/dev/random/randomdev.c =================================================================== --- head/sys/dev/random/randomdev.c (revision 298592) +++ head/sys/dev/random/randomdev.c (revision 298593) @@ -1,402 +1,399 @@ /*- * Copyright (c) 2000-2015 Mark R V Murray * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer * in this position and unchanged. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define RANDOM_UNIT 0 #if defined(RANDOM_LOADABLE) #define READ_RANDOM_UIO _read_random_uio #define READ_RANDOM _read_random static int READ_RANDOM_UIO(struct uio *, bool); static u_int READ_RANDOM(void *, u_int); #else #define READ_RANDOM_UIO read_random_uio #define READ_RANDOM read_random #endif -/* Return the largest number >= x that is a multiple of m */ -#define CEIL_TO_MULTIPLE(x, m) ((((x) + (m) - 1)/(m))*(m)) - static d_read_t randomdev_read; static d_write_t randomdev_write; static d_poll_t randomdev_poll; static d_ioctl_t randomdev_ioctl; static struct cdevsw random_cdevsw = { .d_name = "random", .d_version = D_VERSION, .d_read = randomdev_read, .d_write = randomdev_write, .d_poll = randomdev_poll, .d_ioctl = randomdev_ioctl, }; /* For use with make_dev(9)/destroy_dev(9). */ static struct cdev *random_dev; static void random_alg_context_ra_init_alg(void *data) { p_random_alg_context = &random_alg_context; p_random_alg_context->ra_init_alg(data); #if defined(RANDOM_LOADABLE) random_infra_init(READ_RANDOM_UIO, READ_RANDOM); #endif } static void random_alg_context_ra_deinit_alg(void *data) { #if defined(RANDOM_LOADABLE) random_infra_uninit(); #endif p_random_alg_context->ra_deinit_alg(data); p_random_alg_context = NULL; } SYSINIT(random_device, SI_SUB_RANDOM, SI_ORDER_THIRD, random_alg_context_ra_init_alg, NULL); SYSUNINIT(random_device, SI_SUB_RANDOM, SI_ORDER_THIRD, random_alg_context_ra_deinit_alg, NULL); static struct selinfo rsel; /* * This is the read uio(9) interface for random(4). */ /* ARGSUSED */ static int randomdev_read(struct cdev *dev __unused, struct uio *uio, int flags) { return (READ_RANDOM_UIO(uio, (flags & O_NONBLOCK) != 0)); } int READ_RANDOM_UIO(struct uio *uio, bool nonblock) { uint8_t *random_buf; int error, spamcount; ssize_t read_len, total_read, c; random_buf = malloc(PAGE_SIZE, M_ENTROPY, M_WAITOK); p_random_alg_context->ra_pre_read(); error = 0; spamcount = 0; /* (Un)Blocking logic */ while (!p_random_alg_context->ra_seeded()) { if (nonblock) { error = EWOULDBLOCK; break; } /* keep tapping away at the pre-read until we seed/unblock. */ p_random_alg_context->ra_pre_read(); /* Only bother the console every 10 seconds or so */ if (spamcount == 0) printf("random: %s unblock wait\n", __func__); spamcount = (spamcount + 1)%100; error = tsleep(&random_alg_context, PCATCH, "randseed", hz/10); if (error == ERESTART || error == EINTR) break; } if (error == 0) { read_rate_increment((uio->uio_resid + sizeof(uint32_t))/sizeof(uint32_t)); total_read = 0; while (uio->uio_resid && !error) { read_len = uio->uio_resid; /* * Belt-and-braces. * Round up the read length to a crypto block size multiple, * which is what the underlying generator is expecting. * See the random_buf size requirements in the Yarrow/Fortuna code. */ - read_len = CEIL_TO_MULTIPLE(read_len, RANDOM_BLOCKSIZE); + read_len = roundup(read_len, RANDOM_BLOCKSIZE); /* Work in chunks page-sized or less */ read_len = MIN(read_len, PAGE_SIZE); p_random_alg_context->ra_read(random_buf, read_len); c = MIN(uio->uio_resid, read_len); error = uiomove(random_buf, c, uio); total_read += c; } if (total_read != uio->uio_resid && (error == ERESTART || error == EINTR)) /* Return partial read, not error. */ error = 0; } free(random_buf, M_ENTROPY); return (error); } /*- * Kernel API version of read_random(). * This is similar to random_alg_read(), * except it doesn't interface with uio(9). * It cannot assumed that random_buf is a multiple of * RANDOM_BLOCKSIZE bytes. */ u_int READ_RANDOM(void *random_buf, u_int len) { u_int read_len; uint8_t local_buf[len + RANDOM_BLOCKSIZE]; KASSERT(random_buf != NULL, ("No suitable random buffer in %s", __func__)); p_random_alg_context->ra_pre_read(); /* (Un)Blocking logic; if not seeded, return nothing. */ if (p_random_alg_context->ra_seeded()) { read_rate_increment((len + sizeof(uint32_t))/sizeof(uint32_t)); if (len > 0) { /* * Belt-and-braces. * Round up the read length to a crypto block size multiple, * which is what the underlying generator is expecting. */ - read_len = CEIL_TO_MULTIPLE(len, RANDOM_BLOCKSIZE); + read_len = roundup(len, RANDOM_BLOCKSIZE); p_random_alg_context->ra_read(local_buf, read_len); memcpy(random_buf, local_buf, len); } } else len = 0; return (len); } static __inline void randomdev_accumulate(uint8_t *buf, u_int count) { static u_int destination = 0; static struct harvest_event event; static struct randomdev_hash hash; static uint32_t entropy_data[RANDOM_KEYSIZE_WORDS]; uint32_t timestamp; int i; /* Extra timing here is helpful to scrape scheduler jitter entropy */ randomdev_hash_init(&hash); timestamp = (uint32_t)get_cyclecount(); randomdev_hash_iterate(&hash, ×tamp, sizeof(timestamp)); randomdev_hash_iterate(&hash, buf, count); timestamp = (uint32_t)get_cyclecount(); randomdev_hash_iterate(&hash, ×tamp, sizeof(timestamp)); randomdev_hash_finish(&hash, entropy_data); explicit_bzero(&hash, sizeof(hash)); for (i = 0; i < RANDOM_KEYSIZE_WORDS; i += sizeof(event.he_entropy)/sizeof(event.he_entropy[0])) { event.he_somecounter = (uint32_t)get_cyclecount(); event.he_size = sizeof(event.he_entropy); event.he_bits = event.he_size/8; event.he_source = RANDOM_CACHED; event.he_destination = destination++; /* Harmless cheating */ memcpy(event.he_entropy, entropy_data + i, sizeof(event.he_entropy)); p_random_alg_context->ra_event_processor(&event); } explicit_bzero(entropy_data, sizeof(entropy_data)); } /* ARGSUSED */ static int randomdev_write(struct cdev *dev __unused, struct uio *uio, int flags __unused) { uint8_t *random_buf; int c, error = 0; ssize_t nbytes; random_buf = malloc(PAGE_SIZE, M_ENTROPY, M_WAITOK); nbytes = uio->uio_resid; while (uio->uio_resid > 0 && error == 0) { c = MIN(uio->uio_resid, PAGE_SIZE); error = uiomove(random_buf, c, uio); if (error) break; randomdev_accumulate(random_buf, c); tsleep(&random_alg_context, 0, "randwr", hz/10); } if (nbytes != uio->uio_resid && (error == ERESTART || error == EINTR)) /* Partial write, not error. */ error = 0; free(random_buf, M_ENTROPY); return (error); } /* ARGSUSED */ static int randomdev_poll(struct cdev *dev __unused, int events, struct thread *td __unused) { if (events & (POLLIN | POLLRDNORM)) { if (p_random_alg_context->ra_seeded()) events &= (POLLIN | POLLRDNORM); else selrecord(td, &rsel); } return (events); } /* This will be called by the entropy processor when it seeds itself and becomes secure */ void randomdev_unblock(void) { selwakeuppri(&rsel, PUSER); wakeup(&random_alg_context); printf("random: unblocking device.\n"); /* Do random(9) a favour while we are about it. */ (void)atomic_cmpset_int(&arc4rand_iniseed_state, ARC4_ENTR_NONE, ARC4_ENTR_HAVE); } /* ARGSUSED */ static int randomdev_ioctl(struct cdev *dev __unused, u_long cmd, caddr_t addr __unused, int flags __unused, struct thread *td __unused) { int error = 0; switch (cmd) { /* Really handled in upper layer */ case FIOASYNC: case FIONBIO: break; default: error = ENOTTY; } return (error); } void random_source_register(struct random_source *rsource) { struct random_sources *rrs; KASSERT(rsource != NULL, ("invalid input to %s", __func__)); rrs = malloc(sizeof(*rrs), M_ENTROPY, M_WAITOK); rrs->rrs_source = rsource; printf("random: registering fast source %s\n", rsource->rs_ident); LIST_INSERT_HEAD(&source_list, rrs, rrs_entries); } void random_source_deregister(struct random_source *rsource) { struct random_sources *rrs = NULL; KASSERT(rsource != NULL, ("invalid input to %s", __func__)); LIST_FOREACH(rrs, &source_list, rrs_entries) if (rrs->rrs_source == rsource) { LIST_REMOVE(rrs, rrs_entries); break; } if (rrs != NULL) free(rrs, M_ENTROPY); } static int random_source_handler(SYSCTL_HANDLER_ARGS) { struct random_sources *rrs; struct sbuf sbuf; int error, count; sbuf_new_for_sysctl(&sbuf, NULL, 64, req); count = 0; LIST_FOREACH(rrs, &source_list, rrs_entries) { sbuf_cat(&sbuf, (count++ ? ",'" : "'")); sbuf_cat(&sbuf, rrs->rrs_source->rs_ident); sbuf_cat(&sbuf, "'"); } error = sbuf_finish(&sbuf); sbuf_delete(&sbuf); return (error); } SYSCTL_PROC(_kern_random, OID_AUTO, random_sources, CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0, random_source_handler, "A", "List of active fast entropy sources."); /* ARGSUSED */ static int randomdev_modevent(module_t mod __unused, int type, void *data __unused) { int error = 0; switch (type) { case MOD_LOAD: printf("random: entropy device external interface\n"); random_dev = make_dev_credf(MAKEDEV_ETERNAL_KLD, &random_cdevsw, RANDOM_UNIT, NULL, UID_ROOT, GID_WHEEL, 0644, "random"); make_dev_alias(random_dev, "urandom"); /* compatibility */ break; case MOD_UNLOAD: destroy_dev(random_dev); break; case MOD_SHUTDOWN: break; default: error = EOPNOTSUPP; break; } return (error); } static moduledata_t randomdev_mod = { "random_device", randomdev_modevent, 0 }; DECLARE_MODULE(random_device, randomdev_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST); MODULE_VERSION(random_device, 1); MODULE_DEPEND(random_device, crypto, 1, 1, 1); MODULE_DEPEND(random_device, random_harvestq, 1, 1, 1); Index: head/sys/dev/random/yarrow.c =================================================================== --- head/sys/dev/random/yarrow.c (revision 298592) +++ head/sys/dev/random/yarrow.c (revision 298593) @@ -1,395 +1,395 @@ /*- * Copyright (c) 2000-2015 Mark R V Murray * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer * in this position and unchanged. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * */ #include __FBSDID("$FreeBSD$"); #ifdef _KERNEL #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #else /* !_KERNEL */ #include #include #include #include #include #include #include #include "unit_test.h" #include #include #include #include #include #include #endif /* _KERNEL */ #define RANDOM_YARROW_TIMEBIN 16 /* max value for Pt/t */ #define RANDOM_YARROW_FAST 0 #define RANDOM_YARROW_SLOW 1 #define RANDOM_YARROW_NPOOLS 2 /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */ CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t)); CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE); /* Probes for dtrace(1) */ SDT_PROVIDER_DECLARE(random); SDT_PROVIDER_DEFINE(random); SDT_PROBE_DEFINE3(random, yarrow, event_processor, debug, "boolean", "u_int", "struct ys_pool *"); /* * This is the beastie that needs protecting. It contains all of the * state that we are excited about. Exactly one is instantiated. */ static struct yarrow_state { uint128_t ys_counter; /* C */ struct randomdev_key ys_key; /* K */ u_int ys_gengateinterval; /* Pg */ u_int ys_bins; /* Pt/t */ u_int ys_outputblocks; /* count output blocks for gates */ u_int ys_slowoverthresh; /* slow pool overthreshhold reseed count */ struct ys_pool { u_int ysp_source_bits[ENTROPYSOURCE]; /* estimated bits of entropy per source */ u_int ysp_thresh; /* pool reseed threshhold */ struct randomdev_hash ysp_hash; /* accumulated entropy */ } ys_pool[RANDOM_YARROW_NPOOLS];/* pool[0] is fast, pool[1] is slow */ bool ys_seeded; /* Reseed lock */ mtx_t ys_mtx; } yarrow_state; #ifdef _KERNEL static struct sysctl_ctx_list random_clist; RANDOM_CHECK_UINT(gengateinterval, 4, 64); RANDOM_CHECK_UINT(bins, RANDOM_YARROW_NPOOLS, 16); RANDOM_CHECK_UINT(fastthresh, (RANDOM_BLOCKSIZE*8)/4, (RANDOM_BLOCKSIZE*8)); /* Bit counts */ RANDOM_CHECK_UINT(slowthresh, (RANDOM_BLOCKSIZE*8)/4, (RANDOM_BLOCKSIZE*8)); /* Bit counts */ RANDOM_CHECK_UINT(slowoverthresh, 1, 5); #endif /* _KERNEL */ static void random_yarrow_pre_read(void); static void random_yarrow_read(uint8_t *, u_int); static bool random_yarrow_seeded(void); static void random_yarrow_process_event(struct harvest_event *); static void random_yarrow_init_alg(void *); static void random_yarrow_deinit_alg(void *); static void random_yarrow_reseed_internal(u_int); struct random_algorithm random_alg_context = { .ra_ident = "Yarrow", .ra_init_alg = random_yarrow_init_alg, .ra_deinit_alg = random_yarrow_deinit_alg, .ra_pre_read = random_yarrow_pre_read, .ra_read = random_yarrow_read, .ra_seeded = random_yarrow_seeded, .ra_event_processor = random_yarrow_process_event, .ra_poolcount = RANDOM_YARROW_NPOOLS, }; /* ARGSUSED */ static void random_yarrow_init_alg(void *unused __unused) { int i, j; #ifdef _KERNEL struct sysctl_oid *random_yarrow_o; #endif RANDOM_RESEED_INIT_LOCK(); /* Start unseeded, therefore blocked. */ yarrow_state.ys_seeded = false; #ifdef _KERNEL /* * Yarrow parameters. Do not adjust these unless you have * have a very good clue about what they do! */ random_yarrow_o = SYSCTL_ADD_NODE(&random_clist, SYSCTL_STATIC_CHILDREN(_kern_random), OID_AUTO, "yarrow", CTLFLAG_RW, 0, "Yarrow Parameters"); SYSCTL_ADD_PROC(&random_clist, SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, "gengateinterval", CTLTYPE_UINT | CTLFLAG_RWTUN, &yarrow_state.ys_gengateinterval, 0, random_check_uint_gengateinterval, "UI", "Generation gate interval"); SYSCTL_ADD_PROC(&random_clist, SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, "bins", CTLTYPE_UINT | CTLFLAG_RWTUN, &yarrow_state.ys_bins, 0, random_check_uint_bins, "UI", "Execution time tuner"); SYSCTL_ADD_PROC(&random_clist, SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, "fastthresh", CTLTYPE_UINT | CTLFLAG_RWTUN, &yarrow_state.ys_pool[0].ysp_thresh, 0, random_check_uint_fastthresh, "UI", "Fast reseed threshold"); SYSCTL_ADD_PROC(&random_clist, SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, "slowthresh", CTLTYPE_UINT | CTLFLAG_RWTUN, &yarrow_state.ys_pool[1].ysp_thresh, 0, random_check_uint_slowthresh, "UI", "Slow reseed threshold"); SYSCTL_ADD_PROC(&random_clist, SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, "slowoverthresh", CTLTYPE_UINT | CTLFLAG_RWTUN, &yarrow_state.ys_slowoverthresh, 0, random_check_uint_slowoverthresh, "UI", "Slow over-threshold reseed"); #endif /* _KERNEL */ yarrow_state.ys_gengateinterval = 10; yarrow_state.ys_bins = 10; yarrow_state.ys_pool[RANDOM_YARROW_FAST].ysp_thresh = (3*(RANDOM_BLOCKSIZE*8))/4; yarrow_state.ys_pool[RANDOM_YARROW_SLOW].ysp_thresh = (RANDOM_BLOCKSIZE*8); yarrow_state.ys_slowoverthresh = 2; /* Ensure that the first time we read, we are gated. */ yarrow_state.ys_outputblocks = yarrow_state.ys_gengateinterval; /* Initialise the fast and slow entropy pools */ for (i = RANDOM_YARROW_FAST; i <= RANDOM_YARROW_SLOW; i++) { randomdev_hash_init(&yarrow_state.ys_pool[i].ysp_hash); for (j = RANDOM_START; j < ENTROPYSOURCE; j++) yarrow_state.ys_pool[i].ysp_source_bits[j] = 0; } /* Clear the counter */ yarrow_state.ys_counter = UINT128_ZERO; } /* ARGSUSED */ static void random_yarrow_deinit_alg(void *unused __unused) { RANDOM_RESEED_DEINIT_LOCK(); explicit_bzero(&yarrow_state, sizeof(yarrow_state)); #ifdef _KERNEL sysctl_ctx_free(&random_clist); #endif } /* Process a single stochastic event off the harvest queue */ static void random_yarrow_process_event(struct harvest_event *event) { u_int pl, overthreshhold[RANDOM_YARROW_NPOOLS]; enum random_entropy_source src; RANDOM_RESEED_LOCK(); /* * Accumulate the event into the appropriate pool * where each event carries the destination information. * We lock against pool state modification which can happen * during accumulation/reseeding and reading/regating */ pl = event->he_destination % RANDOM_YARROW_NPOOLS; randomdev_hash_iterate(&yarrow_state.ys_pool[pl].ysp_hash, event, sizeof(*event)); yarrow_state.ys_pool[pl].ysp_source_bits[event->he_source] += event->he_bits; /* Count the over-threshold sources in each pool */ for (pl = RANDOM_YARROW_FAST; pl <= RANDOM_YARROW_SLOW; pl++) { overthreshhold[pl] = 0; for (src = RANDOM_START; src < ENTROPYSOURCE; src++) { if (yarrow_state.ys_pool[pl].ysp_source_bits[src] > yarrow_state.ys_pool[pl].ysp_thresh) overthreshhold[pl]++; } } /* * If enough slow sources are over threshhold, then slow reseed * else if any fast source over threshhold, then fast reseed. */ if (overthreshhold[RANDOM_YARROW_SLOW] >= yarrow_state.ys_slowoverthresh) random_yarrow_reseed_internal(RANDOM_YARROW_SLOW); else if (overthreshhold[RANDOM_YARROW_FAST] > 0 && yarrow_state.ys_seeded) random_yarrow_reseed_internal(RANDOM_YARROW_FAST); explicit_bzero(event, sizeof(*event)); RANDOM_RESEED_UNLOCK(); } static void random_yarrow_reseed_internal(u_int fastslow) { /* * Interrupt-context stack is a limited resource; make large * structures static. */ static uint8_t v[RANDOM_YARROW_TIMEBIN][RANDOM_KEYSIZE]; /* v[i] */ static uint128_t temp; static struct randomdev_hash context; u_int i; enum random_entropy_source j; KASSERT(yarrow_state.ys_pool[RANDOM_YARROW_FAST].ysp_thresh > 0, ("random: Yarrow fast threshold = 0")); KASSERT(yarrow_state.ys_pool[RANDOM_YARROW_SLOW].ysp_thresh > 0, ("random: Yarrow slow threshold = 0")); RANDOM_RESEED_ASSERT_LOCK_OWNED(); SDT_PROBE3(random, yarrow, event_processor, debug, yarrow_state.ys_seeded, yarrow_state.ys_slowoverthresh, yarrow_state.ys_pool); /* 1. Hash the accumulated entropy into v[0] */ randomdev_hash_init(&context); /* Feed the slow pool hash in if slow */ if (fastslow == RANDOM_YARROW_SLOW) { randomdev_hash_finish(&yarrow_state.ys_pool[RANDOM_YARROW_SLOW].ysp_hash, &temp); randomdev_hash_iterate(&context, &temp, sizeof(temp)); } randomdev_hash_finish(&yarrow_state.ys_pool[RANDOM_YARROW_FAST].ysp_hash, &temp); randomdev_hash_iterate(&context, &temp, sizeof(temp)); randomdev_hash_finish(&context, v[0]); /*- * 2. Compute hash values for all v. _Supposed_ to be computationally * intensive. */ if (yarrow_state.ys_bins > RANDOM_YARROW_TIMEBIN) yarrow_state.ys_bins = RANDOM_YARROW_TIMEBIN; for (i = 1; i < yarrow_state.ys_bins; i++) { randomdev_hash_init(&context); /* v[i] #= h(v[i - 1]) */ randomdev_hash_iterate(&context, v[i - 1], RANDOM_KEYSIZE); /* v[i] #= h(v[0]) */ randomdev_hash_iterate(&context, v[0], RANDOM_KEYSIZE); /* v[i] #= h(i) */ randomdev_hash_iterate(&context, &i, sizeof(i)); /* Return the hashval */ randomdev_hash_finish(&context, v[i]); } /*- * 3. Compute a new key; h' is the identity function here; * it is not being ignored! */ randomdev_hash_init(&context); randomdev_hash_iterate(&context, &yarrow_state.ys_key, RANDOM_KEYSIZE); for (i = 1; i < yarrow_state.ys_bins; i++) randomdev_hash_iterate(&context, v[i], RANDOM_KEYSIZE); randomdev_hash_finish(&context, &temp); randomdev_encrypt_init(&yarrow_state.ys_key, &temp); /* 4. Recompute the counter */ yarrow_state.ys_counter = UINT128_ZERO; randomdev_encrypt(&yarrow_state.ys_key, &yarrow_state.ys_counter, &temp, RANDOM_BLOCKSIZE); yarrow_state.ys_counter = temp; /* 5. Reset entropy estimate accumulators to zero */ for (i = 0; i <= fastslow; i++) for (j = RANDOM_START; j < ENTROPYSOURCE; j++) yarrow_state.ys_pool[i].ysp_source_bits[j] = 0; /* 6. Wipe memory of intermediate values */ explicit_bzero(v, sizeof(v)); explicit_bzero(&temp, sizeof(temp)); explicit_bzero(&context, sizeof(context)); /* Not defined so writes ain't gonna happen. Kept for documenting. */ #ifdef RANDOM_RWFILE_WRITE_IS_OK /*- * 7. Dump to seed file. * This pseudo-code is documentation. Please leave it alone. */ seed_file = ""; error = randomdev_write_file(seed_file, , PAGE_SIZE); if (error == 0) printf("random: entropy seed file '%s' successfully written\n", seed_file); #endif /* Unblock the device if it was blocked due to being unseeded */ if (!yarrow_state.ys_seeded) { yarrow_state.ys_seeded = true; randomdev_unblock(); } } static __inline void random_yarrow_generator_gate(void) { u_int i; uint8_t temp[RANDOM_KEYSIZE]; RANDOM_RESEED_ASSERT_LOCK_OWNED(); uint128_increment(&yarrow_state.ys_counter); for (i = 0; i < RANDOM_KEYSIZE; i += RANDOM_BLOCKSIZE) randomdev_encrypt(&yarrow_state.ys_key, &yarrow_state.ys_counter, temp + i, RANDOM_BLOCKSIZE); randomdev_encrypt_init(&yarrow_state.ys_key, temp); explicit_bzero(temp, sizeof(temp)); } /*- * Used to return processed entropy from the PRNG. There is a pre_read * required to be present (but it can be a stub) in order to allow * specific actions at the begin of the read. * Yarrow does its reseeding in its own thread; _pre_read() is not used * by Yarrow but must be kept for completeness. */ void random_yarrow_pre_read(void) { } /*- * Main read from Yarrow. * The supplied buf MUST be a multiple (>=0) of RANDOM_BLOCKSIZE in size. * Lots of code presumes this for efficiency, both here and in other * routines. You are NOT allowed to break this! */ void random_yarrow_read(uint8_t *buf, u_int bytecount) { u_int blockcount, i; KASSERT((bytecount % RANDOM_BLOCKSIZE) == 0, ("%s(): bytecount (= %d) must be a multiple of %d", __func__, bytecount, RANDOM_BLOCKSIZE )); RANDOM_RESEED_LOCK(); - blockcount = (bytecount + RANDOM_BLOCKSIZE - 1)/RANDOM_BLOCKSIZE; + blockcount = howmany(bytecount, RANDOM_BLOCKSIZE); for (i = 0; i < blockcount; i++) { if (yarrow_state.ys_outputblocks++ >= yarrow_state.ys_gengateinterval) { random_yarrow_generator_gate(); yarrow_state.ys_outputblocks = 0; } uint128_increment(&yarrow_state.ys_counter); randomdev_encrypt(&yarrow_state.ys_key, &yarrow_state.ys_counter, buf, RANDOM_BLOCKSIZE); buf += RANDOM_BLOCKSIZE; } RANDOM_RESEED_UNLOCK(); } bool random_yarrow_seeded(void) { return (yarrow_state.ys_seeded); }