Currently we use non-cryptographically secure random numbers in two places, the error filter (to inject errors at random) and the random plugin. For this we have used either random_r or a home-brew-ish Linear Congruential Generator. Use of random_r is problematic on BSDs because it doesn't exist there. Use of the LCG is simply a bad choice. Replace both uses with a better quality and faster PRNG from David Blackman and Sebastiano Vigna called ‘xoshiro256** 1.0’ (http://xoshiro.di.unimi.it/). This is licensed under a public-domain license so it compatible with the licensing of nbdkit. This also fixes a bug in the random plugin where it could never generate the byte 255 because I used modulo 255 instead of modulo 256 arithmetic. Ooops. --- plugins/random/nbdkit-random-plugin.pod | 5 +- common/include/random.h | 79 +++++++++++++++++++++++++ filters/error/error.c | 28 ++++----- plugins/random/random.c | 46 +++++++------- common/include/Makefile.am | 1 + plugins/random/Makefile.am | 1 + 6 files changed, 115 insertions(+), 45 deletions(-) diff --git a/plugins/random/nbdkit-random-plugin.pod b/plugins/random/nbdkit-random-plugin.pod index 5dfe801..750daab 100644 --- a/plugins/random/nbdkit-random-plugin.pod +++ b/plugins/random/nbdkit-random-plugin.pod @@ -15,9 +15,8 @@ The size of the virtual disk must be specified using the C<size> parameter. If you specify the C<seed> parameter then you will get the same random data over multiple runs with the same seed. -The random data is generated using an I<in>secure method (a Linear -Congruential Generator). This plugin is mainly good for testing NBD -clients. +The random data is generated using an I<insecure> method. This plugin +is mainly good for testing NBD clients. =head1 PARAMETERS diff --git a/common/include/random.h b/common/include/random.h new file mode 100644 index 0000000..e4cc947 --- /dev/null +++ b/common/include/random.h @@ -0,0 +1,79 @@ +/* nbdkit + * Copyright (C) 2018 Red Hat Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * 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. + * + * * Neither the name of Red Hat nor the names of its contributors may be + * used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''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 RED HAT OR + * CONTRIBUTORS 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. + */ + +#ifndef NBDKIT_RANDOM_H +#define NBDKIT_RANDOM_H + +#include <stdint.h> + +/* Generate pseudo-random numbers, quickly, with explicit state. + * + * This is based on the xoshiro/xoroshiro generators by David Blackman + * and Sebastiano Vigna at http://xoshiro.di.unimi.it/ . Specifically + * this is ‘xoshiro256** 1.0’. + * + * This does _NOT_ generate cryptographically secure random numbers + * (CSPRNG) and so should not be used when cryptography or security is + * required - use gcrypt if you need those. + */ + +struct random_state { + uint64_t s[4]; +}; + +static inline uint64_t +rotl (const uint64_t x, int k) +{ + return (x << k) | (x >> (64 - k)); +} + +/* Returns 64 random bits. Updates the state. */ +uint64_t +xrandom (struct random_state *state) +{ + const uint64_t result_starstar = rotl (state->s[1] * 5, 7) * 9; + const uint64_t t = state->s[1] << 17; + + state->s[2] ^= state->s[0]; + state->s[3] ^= state->s[1]; + state->s[1] ^= state->s[2]; + state->s[0] ^= state->s[3]; + + state->s[2] ^= t; + + state->s[3] = rotl (state->s[3], 45); + + return result_starstar; +} + +#endif /* NBDKIT_RANDOM_H */ diff --git a/filters/error/error.c b/filters/error/error.c index 8509a16..6d305b3 100644 --- a/filters/error/error.c +++ b/filters/error/error.c @@ -44,6 +44,8 @@ #include <nbdkit-filter.h> +#include "random.h" + #define THREAD_MODEL NBDKIT_THREAD_MODEL_PARALLEL struct error_settings { @@ -222,17 +224,13 @@ error_config (nbdkit_next_config *next, void *nxdata, " Apply settings only to read/write/trim/zero" struct handle { -#ifdef __GNU_LIBRARY__ - struct random_data rd; - char rd_state[32]; -#endif + struct random_state random_state; }; static void * error_open (nbdkit_next_open *next, void *nxdata, int readonly) { struct handle *h; - time_t t; if (next (nxdata, readonly) == -1) return NULL; @@ -242,11 +240,7 @@ error_open (nbdkit_next_open *next, void *nxdata, int readonly) nbdkit_error ("malloc: %m"); return NULL; } -#ifdef __GNU_LIBRARY__ - memset (&h->rd, 0, sizeof h->rd); - time (&t); - initstate_r (t, (char *) &h->rd_state, sizeof h->rd_state, &h->rd); -#endif + memset (&h->random_state, 0, sizeof h->random_state); return h; } @@ -264,7 +258,7 @@ random_error (struct handle *h, const struct error_settings *error_settings, const char *fn, int *err) { - int32_t rand; + uint64_t rand; if (error_settings->rate <= 0) /* 0% = never inject */ return false; @@ -278,12 +272,12 @@ random_error (struct handle *h, if (error_settings->rate >= 1) /* 100% = always inject */ goto inject; -#ifdef __GNU_LIBRARY__ - random_r (&h->rd, &rand); -#else - rand = random (); -#endif - if (rand >= error_settings->rate * RAND_MAX) + /* To avoid the question if (double)1.0 * UINT64_MAX is + * representable in a 64 bit integer, and because we don't need all + * this precision anyway, let's work in 32 bits. + */ + rand = xrandom (&h->random_state) & UINT32_MAX; + if (rand >= error_settings->rate * UINT32_MAX) return false; inject: diff --git a/plugins/random/random.c b/plugins/random/random.c index 8adc26e..00a6443 100644 --- a/plugins/random/random.c +++ b/plugins/random/random.c @@ -44,32 +44,14 @@ #define NBDKIT_API_VERSION 2 #include <nbdkit-plugin.h> +#include "random.h" + /* The size of disk in bytes (initialized by size=<SIZE> parameter). */ static int64_t size = 0; /* Seed. */ static uint32_t seed; -/* We use a Linear Congruential Generator (LCG) to make low quality - * but easy to compute random numbers. However we're not quite using - * it in the ordinary way. In order to be able to read any byte of - * data without needing to run the LCG from the start, the random data - * is computed from the index and seed through two rounds of LCG: - * - * index i LCG(seed) -> +i -> LCG -> LCG -> mod 256 -> b[i] - * index i+1 LCG(seed) -> +i+1 -> LCG -> LCG -> mod 256 -> b[i+1] - * etc - * - * This LCG is the same one as used in glibc. - */ -static inline uint32_t -LCG (uint32_t s) -{ - s *= 1103515245; - s += 12345; - return s; -} - static void random_load (void) { @@ -135,13 +117,27 @@ random_pread (void *handle, void *buf, uint32_t count, uint64_t offset, { uint32_t i; unsigned char *b = buf; - uint32_t s; + uint64_t s; + struct random_state state; for (i = 0; i < count; ++i) { - s = LCG (seed) + offset + i; - s = LCG (s); - s = LCG (s); - s = s % 255; + /* We use nbdkit common/include/random.h to make random numbers. + * + * However we're not quite using it in the ordinary way. In order + * to be able to read any byte of data without needing to run the + * PRNG from the start, the random data is computed from the index + * and seed through three rounds of PRNG: + * + * index i PRNG(seed+i) -> PRNG -> PRNG -> mod 256 -> b[i] + * index i+1 PRNG(seed+i+1) -> PRNG -> PRNG -> mod 256 -> b[i+1] + * etc + */ + memset (&state, 0, sizeof state); + state.s[0] = seed + offset + i; + xrandom (&state); + xrandom (&state); + s = xrandom (&state); + s &= 255; b[i] = s; } return 0; diff --git a/common/include/Makefile.am b/common/include/Makefile.am index c7416fb..6417b8e 100644 --- a/common/include/Makefile.am +++ b/common/include/Makefile.am @@ -42,4 +42,5 @@ EXTRA_DIST = \ ispowerof2.h \ iszero.h \ nextnonzero.h \ + random.h \ rounding.h diff --git a/plugins/random/Makefile.am b/plugins/random/Makefile.am index d990158..0a84774 100644 --- a/plugins/random/Makefile.am +++ b/plugins/random/Makefile.am @@ -41,6 +41,7 @@ nbdkit_random_plugin_la_SOURCES = \ $(top_srcdir)/include/nbdkit-plugin.h nbdkit_random_plugin_la_CPPFLAGS = \ + -I$(top_srcdir)/common/include \ -I$(top_srcdir)/include nbdkit_random_plugin_la_CFLAGS = \ $(WARNINGS_CFLAGS) -- 2.19.2