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 released into the public domain (where possible) 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. This also adds a simple sniff test that the random plugin is producing something which at least looks like random data. --- plugins/random/nbdkit-random-plugin.pod | 5 +- common/include/random.h | 101 ++++++++++++++++++++++++ filters/error/error.c | 28 +++---- plugins/random/random.c | 46 +++++------ tests/test-random.c | 23 ++++++ common/include/Makefile.am | 1 + plugins/random/Makefile.am | 1 + 7 files changed, 160 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..9d90352 --- /dev/null +++ b/common/include/random.h @@ -0,0 +1,101 @@ +/* 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. + */ + +/* You can seed ‘struct random_state’ by setting the s[] elements + * directly - but not you must NOT set it all to zero. OR if you have + * a 64 bit seed, you can use xsrandom below to initialize the state. + */ +struct random_state { + uint64_t s[4]; +}; + +static inline uint64_t +snext (uint64_t *seed) +{ + uint64_t z = (*seed += 0x9e3779b97f4a7c15); + z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; + z = (z ^ (z >> 27)) * 0x94d049bb133111eb; + return z ^ (z >> 31); +} + +static inline void +xsrandom (uint64_t seed, struct random_state *state) +{ + state->s[0] = snext (&seed); + state->s[1] = snext (&seed); + state->s[2] = snext (&seed); + state->s[3] = snext (&seed); +} + +static inline uint64_t +rotl (const uint64_t x, int k) +{ + return (x << k) | (x >> (64 - k)); +} + +/* Returns 64 random bits. Updates the state. */ +static inline 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..9f33910 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 + xsrandom (0, &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..72caaed 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; 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 + */ + struct random_state state; + + xsrandom (seed + offset + i, &state); + xrandom (&state); + xrandom (&state); + s = xrandom (&state); + s &= 255; b[i] = s; } return 0; diff --git a/tests/test-random.c b/tests/test-random.c index 168331c..c02fdc2 100644 --- a/tests/test-random.c +++ b/tests/test-random.c @@ -48,6 +48,8 @@ #define SIZE 1024*1024 static char data[SIZE]; +static unsigned histogram[256]; + /* After reading the whole disk above, we then read randomly selected * subsets of the disk and compare the data (it should be identical). */ @@ -98,6 +100,27 @@ main (int argc, char *argv[]) memcpy (data, rdata, SIZE); free (rdata); + /* Test that the data is sufficiently random using a simple + * histogram. This just tests for gross errors and is not a + * complete statistical study. + */ + for (i = 0; i < SIZE; ++i) { + unsigned char c = (unsigned char) data[i]; + histogram[c]++; + } + for (i = 0; i < 256; ++i) { + const unsigned expected = SIZE / 256; + if (histogram[i] < 80 * expected / 100) { + fprintf (stderr, "test-random: " + "random data is not uniformly distributed\n" + "eg. byte %d occurs %u times (expected about %u times)\n", + i, histogram[i], expected); + exit (EXIT_FAILURE); + } + } + + /* Randomly read parts of the disk to ensure we get the same data. + */ srandom (time (NULL)); for (i = 0; i < NR_READS; ++i) { offset = random (); diff --git a/common/include/Makefile.am b/common/include/Makefile.am index 81f4804..f96bab5 100644 --- a/common/include/Makefile.am +++ b/common/include/Makefile.am @@ -41,4 +41,5 @@ EXTRA_DIST = \ isaligned.h \ ispowerof2.h \ iszero.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