From d5861655770012f2a69a575c40f59a3567351672 Mon Sep 17 00:00:00 2001 From: markm Date: Tue, 30 Jun 2015 17:00:45 +0000 Subject: Huge cleanup of random(4) code. * GENERAL - Update copyright. - Make kernel options for RANDOM_YARROW and RANDOM_DUMMY. Set neither to ON, which means we want Fortuna - If there is no 'device random' in the kernel, there will be NO random(4) device in the kernel, and the KERN_ARND sysctl will return nothing. With RANDOM_DUMMY there will be a random(4) that always blocks. - Repair kern.arandom (KERN_ARND sysctl). The old version went through arc4random(9) and was a bit weird. - Adjust arc4random stirring a bit - the existing code looks a little suspect. - Fix the nasty pre- and post-read overloading by providing explictit functions to do these tasks. - Redo read_random(9) so as to duplicate random(4)'s read internals. This makes it a first-class citizen rather than a hack. - Move stuff out of locked regions when it does not need to be there. - Trim RANDOM_DEBUG printfs. Some are excess to requirement, some behind boot verbose. - Use SYSINIT to sequence the startup. - Fix init/deinit sysctl stuff. - Make relevant sysctls also tunables. - Add different harvesting "styles" to allow for different requirements (direct, queue, fast). - Add harvesting of FFS atime events. This needs to be checked for weighing down the FS code. - Add harvesting of slab allocator events. This needs to be checked for weighing down the allocator code. - Fix the random(9) manpage. - Loadable modules are not present for now. These will be re-engineered when the dust settles. - Use macros for locks. - Fix comments. * src/share/man/... - Update the man pages. * src/etc/... - The startup/shutdown work is done in D2924. * src/UPDATING - Add UPDATING announcement. * src/sys/dev/random/build.sh - Add copyright. - Add libz for unit tests. * src/sys/dev/random/dummy.c - Remove; no longer needed. Functionality incorporated into randomdev.*. * live_entropy_sources.c live_entropy_sources.h - Remove; content moved. - move content to randomdev.[ch] and optimise. * src/sys/dev/random/random_adaptors.c src/sys/dev/random/random_adaptors.h - Remove; plugability is no longer used. Compile-time algorithm selection is the way to go. * src/sys/dev/random/random_harvestq.c src/sys/dev/random/random_harvestq.h - Add early (re)boot-time randomness caching. * src/sys/dev/random/randomdev_soft.c src/sys/dev/random/randomdev_soft.h - Remove; no longer needed. * src/sys/dev/random/uint128.h - Provide a fake uint128_t; if a real one ever arrived, we can use that instead. All that is needed here is N=0, N++, N==0, and some localised trickery is used to manufacture a 128-bit 0ULLL. * src/sys/dev/random/unit_test.c src/sys/dev/random/unit_test.h - Improve unit tests; previously the testing human needed clairvoyance; now the test will do a basic check of compressibility. Clairvoyant talent is still a good idea. - This is still a long way off a proper unit test. * src/sys/dev/random/fortuna.c src/sys/dev/random/fortuna.h - Improve messy union to just uint128_t. - Remove unneeded 'static struct fortuna_start_cache'. - Tighten up up arithmetic. - Provide a method to allow eternal junk to be introduced; harden it against blatant by compress/hashing. - Assert that locks are held correctly. - Fix the nasty pre- and post-read overloading by providing explictit functions to do these tasks. - Turn into self-sufficient module (no longer requires randomdev_soft.[ch]) * src/sys/dev/random/yarrow.c src/sys/dev/random/yarrow.h - Improve messy union to just uint128_t. - Remove unneeded 'staic struct start_cache'. - Tighten up up arithmetic. - Provide a method to allow eternal junk to be introduced; harden it against blatant by compress/hashing. - Assert that locks are held correctly. - Fix the nasty pre- and post-read overloading by providing explictit functions to do these tasks. - Turn into self-sufficient module (no longer requires randomdev_soft.[ch]) - Fix some magic numbers elsewhere used as FAST and SLOW. Differential Revision: https://reviews.freebsd.org/D2025 Reviewed by: vsevolod,delphij,rwatson,trasz,jmg Approved by: so (delphij) --- sys/dev/random/randomdev.c | 420 +++++++++++++++++++++++++++++++-------------- 1 file changed, 289 insertions(+), 131 deletions(-) (limited to 'sys/dev/random/randomdev.c') diff --git a/sys/dev/random/randomdev.c b/sys/dev/random/randomdev.c index 9d41aed..1d9dcbe 100644 --- a/sys/dev/random/randomdev.c +++ b/sys/dev/random/randomdev.c @@ -1,6 +1,5 @@ /*- - * Copyright (c) 2000-2013 Mark R V Murray - * Copyright (c) 2013 Arthur Mesh + * Copyright (c) 2000-2015 Mark R V Murray * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -26,28 +25,9 @@ * */ -/* - * NOTE NOTE NOTE - * - * This file is compiled into the kernel unconditionally. Any random(4) - * infrastructure that needs to be in the kernel by default goes here! - * - * Except ... - * - * The adaptor code all goes into random_adaptor.c, which is also compiled - * the kernel by default. The module in that file is initialised before - * this one. - * - * Other modules must be initialised after the above two, and are - * software random processors which plug into random_adaptor.c. - * - */ - #include __FBSDID("$FreeBSD$"); -#include "opt_random.h" - #include #include #include @@ -59,27 +39,42 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include #include +#include +#include #include #include #include #include +#include +#include + +#include #include -#include #include -#define RANDOM_MINOR 0 +#include "opt_random.h" + +#if defined(RANDOM_DUMMY) && defined(RANDOM_YARROW) +#error "Cannot define both RANDOM_DUMMY and RANDOM_YARROW" +#endif +#define RANDOM_MINOR 0 + +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 = random_adaptor_read, - .d_write = random_adaptor_write, - .d_poll = random_adaptor_poll, + .d_read = randomdev_read, + .d_write = randomdev_write, + .d_poll = randomdev_poll, .d_ioctl = randomdev_ioctl, }; @@ -87,163 +82,326 @@ static struct cdevsw random_cdevsw = { static struct cdev *random_dev; /* Set up the sysctl root node for the entropy device */ -SYSCTL_NODE(_kern, OID_AUTO, random, CTLFLAG_RW, 0, "Random Number Generator"); +SYSCTL_NODE(_kern, OID_AUTO, random, CTLFLAG_RW, 0, "Cryptographically Secure Random Number Generator"); MALLOC_DEFINE(M_ENTROPY, "entropy", "Entropy harvesting buffers and data structures"); -/* 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; +#if defined(RANDOM_DUMMY) - default: - error = ENOTTY; +/*- + * Dummy "always block" pseudo algorithm, used when there is no real + * random(4) driver to provide a CSPRNG. + */ - } +static u_int +dummy_random_zero(void) +{ - return (error); + return (0); } -/* Helper routine to enable kproc_exit() to work while the module is - * being (or has been) unloaded. - * This routine is in this file because it is always linked into the kernel, - * and will thus never be unloaded. This is critical for unloadable modules - * that have threads. - */ -void -randomdev_set_wakeup_exit(void *control) +static void +dummy_random(void) { - - wakeup(control); - kproc_exit(0); - /* NOTREACHED */ } -/* ARGSUSED */ -static int -randomdev_modevent(module_t mod __unused, int type, void *data __unused) -{ - int error = 0; +struct random_algorithm random_alg_context = { + .ra_ident = "Dummy", + .ra_reseed = dummy_random, + .ra_seeded = (random_alg_seeded_t *)dummy_random_zero, + .ra_pre_read = dummy_random, + .ra_read = (random_alg_read_t *)dummy_random_zero, + .ra_post_read = dummy_random, + .ra_write = (random_alg_write_t *)dummy_random_zero, + .ra_event_processor = NULL, + .ra_poolcount = 0, +}; - switch (type) { - case MOD_LOAD: - printf("random: entropy device infrastructure driver\n"); - random_dev = make_dev_credf(MAKEDEV_ETERNAL_KLD, &random_cdevsw, - RANDOM_MINOR, NULL, UID_ROOT, GID_WHEEL, 0644, "random"); - make_dev_alias(random_dev, "urandom"); /* compatibility */ - random_adaptors_init(); - break; +#else /* !defined(RANDOM_DUMMY) */ - case MOD_UNLOAD: - random_adaptors_deinit(); - destroy_dev(random_dev); - break; +LIST_HEAD(sources_head, random_sources); +static struct sources_head source_list = LIST_HEAD_INITIALIZER(source_list); +static u_int read_rate; - case MOD_SHUTDOWN: - break; +#endif /* defined(RANDOM_DUMMY) */ - default: - error = EOPNOTSUPP; - break; +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) +{ + uint8_t *random_buf; + int c, error; + ssize_t nbytes; + + random_buf = malloc(PAGE_SIZE, M_ENTROPY, M_WAITOK); + random_alg_context.ra_pre_read(); + /* (Un)Blocking logic */ + error = 0; + while (!random_alg_context.ra_seeded() && error == 0) { + if (flags & O_NONBLOCK) { + error = EWOULDBLOCK; + break; + } + tsleep(&random_alg_context, 0, "randrd", hz/10); + /* keep tapping away at the pre-read until we seed/unblock. */ + random_alg_context.ra_pre_read(); + printf("random: %s unblock (error = %d)\n", __func__, error); } - + if (error == 0) { +#if !defined(RANDOM_DUMMY) + /* XXX: FIX!! Next line as an atomic operation? */ + read_rate += (uio->uio_resid + sizeof(uint32_t))/sizeof(uint32_t); +#endif + nbytes = uio->uio_resid; + while (uio->uio_resid && !error) { + c = MIN(uio->uio_resid, PAGE_SIZE); + random_alg_context.ra_read(random_buf, c); + error = uiomove(random_buf, c, uio); + } + random_alg_context.ra_post_read(); + if (nbytes != uio->uio_resid && (error == ERESTART || error == EINTR) ) + /* Return partial read, not error. */ + error = 0; + } + free(random_buf, M_ENTROPY); return (error); } -DEV_MODULE_ORDERED(randomdev, randomdev_modevent, NULL, SI_ORDER_SECOND); -MODULE_VERSION(randomdev, 1); - -/* ================ - * Harvesting stubs - * ================ +/*- + * 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, total_read, c; + uint8_t local_buf[len + RANDOM_BLOCKSIZE]; + + KASSERT(random_buf != NULL, ("No suitable random buffer in %s", __func__)); + random_alg_context.ra_pre_read(); + /* (Un)Blocking logic; if not seeded, return nothing. */ + if (random_alg_context.ra_seeded()) { +#if !defined(RANDOM_DUMMY) + /* XXX: FIX!! Next line as an atomic operation? */ + read_rate += (len + sizeof(uint32_t))/sizeof(uint32_t); +#endif + read_len = len; + total_read = 0; + while (read_len) { + c = MIN(read_len, PAGE_SIZE); + random_alg_context.ra_read(&local_buf[total_read], c); + read_len -= c; + total_read += c; + } + memcpy(random_buf, local_buf, len); + } else + len = 0; + random_alg_context.ra_post_read(); + return (len); +} -/* Internal stub/fake routine for when no entropy processor is loaded. - * If the entropy device is not loaded, don't act on harvesting calls - * and just return. - */ /* ARGSUSED */ -static void -random_harvest_phony(const void *entropy __unused, u_int count __unused, - u_int bits __unused, enum random_entropy_source origin __unused) +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; + random_alg_context.ra_write(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); } -/* Hold the address of the routine which is actually called */ -static void (*reap_func)(const void *, u_int, u_int, enum random_entropy_source) = random_harvest_phony; +/* ARGSUSED */ +static int +randomdev_poll(struct cdev *dev __unused, int events, struct thread *td __unused) +{ -/* Initialise the harvester when/if it is loaded */ + if (events & (POLLIN | POLLRDNORM)) { + if (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_init_harvester(void (*reaper)(const void *, u_int, u_int, enum random_entropy_source)) +randomdev_unblock(void) { - reap_func = reaper; + 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); } -/* Deinitialise the harvester when/if it is unloaded */ -void -randomdev_deinit_harvester(void) +/* 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; + } - reap_func = random_harvest_phony; + return (error); } -/* Entropy harvesting routine. - * Implemented as in indirect call to allow non-inclusion of - * the entropy device. - */ void -random_harvest(const void *entropy, u_int count, u_int bits, enum random_entropy_source origin) +random_source_register(struct random_source *rsource) { +#if defined(RANDOM_DUMMY) + (void)rsource; +#else /* !defined(RANDOM_DUMMY) */ + struct random_sources *rrs; - (*reap_func)(entropy, count, bits, origin); -} + KASSERT(rsource != NULL, ("invalid input to %s", __func__)); -/* ================================ - * Internal reading stubs and fakes - * ================================ - */ + rrs = malloc(sizeof(*rrs), M_ENTROPY, M_WAITOK); + rrs->rrs_source = rsource; -/* Hold the address of the routine which is actually called */ -static void (*read_func)(uint8_t *, u_int) = dummy_random_read_phony; + printf("random: registering fast source %s\n", rsource->rs_ident); + LIST_INSERT_HEAD(&source_list, rrs, rrs_entries); +#endif /* defined(RANDOM_DUMMY) */ +} -/* Initialise the reader when/if it is loaded */ void -randomdev_init_reader(void (*reader)(uint8_t *, u_int)) +random_source_deregister(struct random_source *rsource) { - - read_func = reader; +#if defined(RANDOM_DUMMY) + (void)rsource; +#else /* !defined(RANDOM_DUMMY) */ + 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); +#endif /* defined(RANDOM_DUMMY) */ } -/* Deinitialise the reader when/if it is unloaded */ +#if !defined(RANDOM_DUMMY) +/* + * Run through all fast sources reading entropy for the given + * number of rounds, which should be a multiple of the number + * of entropy accumulation pools in use; 2 for Yarrow and 32 + * for Fortuna. + * + * BEWARE!!! + * This function runs inside the RNG thread! Don't do anything silly! + */ void -randomdev_deinit_reader(void) +random_sources_feed(void) { + uint32_t entropy[HARVESTSIZE]; + struct random_sources *rrs; + u_int i, n, local_read_rate; + + /* + * Step over all of live entropy sources, and feed their output + * to the system-wide RNG. + */ + /* XXX: FIX!! Next lines as an atomic operation? */ + local_read_rate = read_rate; + read_rate = RANDOM_ALG_READ_RATE_MINIMUM; + LIST_FOREACH(rrs, &source_list, rrs_entries) { + for (i = 0; i < random_alg_context.ra_poolcount*local_read_rate; i++) { + n = rrs->rrs_source->rs_read(entropy, sizeof(entropy)); + KASSERT((n > 0 && n <= sizeof(entropy)), ("very bad return from rs_read (= %d) in %s", n, __func__)); + random_harvest_direct(entropy, n, (n*8)/2, rrs->rrs_source->rs_source); + } + } + explicit_bzero(entropy, sizeof(entropy)); +} - read_func = dummy_random_read_phony; +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."); +#endif /* !defined(RANDOM_DUMMY) */ -/* Kernel API version of read_random(). - * Implemented as in indirect call to allow non-inclusion of - * the entropy device. - */ -int -read_random(void *buf, int count) +/* ARGSUSED */ +static int +randomdev_modevent(module_t mod __unused, int type, void *data __unused) { + int error = 0; - if (count < 0) - return 0; + switch (type) { + case MOD_LOAD: + printf("random: entropy device external interface\n"); + random_dev = make_dev_credf(MAKEDEV_ETERNAL_KLD, &random_cdevsw, + RANDOM_MINOR, 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); +} - read_func(buf, count); +static moduledata_t randomdev_mod = { + "random_device", + randomdev_modevent, + 0 +}; - return count; -} +DECLARE_MODULE(random_device, randomdev_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST); +MODULE_VERSION(random_device, 1); -- cgit v1.1