Until now, utilities wishing access to a quality source of cryptographically secure random numbers would have to either forego security and just use the xorshift, or use one of a few very slow entropy options like get_entropy_or_die or OpenSSL's RAND_bytes() calls. Both of these are quality tested mechanisms, but the drawback is a very long time to execute (measured 10m iterations of rand_bytes taking roughly 5.14s to complete).
This change adds a ChaCha20 based CSPRNG, which is known to be a high quality CSPRNG. The benefits are very fast execution time (the same 10m iterations only take 0.059s vs. the PRNG taking 0.018s). The implementation heavily relies on referencing the following: * RFC 8439, "ChaCha20 and Poly1305 for IETF Protocols" * libevent/arc4random.c, "Arc4 random number generator for OpenBSD." * glibc/stdlib/arc4random.c, "Psuedo random number generator" * Ben Tasker, "Writing (and backdooring) a ChaCha20 based CSPRNG" Signed-off-by: Aaron Conole <[email protected]> --- lib/random.c | 157 ++++++++++++++++++++++++++++++++++++++++++++ lib/random.h | 15 +++++ tests/library.at | 1 + tests/test-random.c | 67 +++++++++++++++++++ 4 files changed, 240 insertions(+) diff --git a/lib/random.c b/lib/random.c index c0bc659d19..d1f6d5b5aa 100644 --- a/lib/random.c +++ b/lib/random.c @@ -21,6 +21,7 @@ #include <stdlib.h> #include <sys/time.h> +#include "byte-order.h" #include "entropy.h" #include "hash.h" #include "ovs-thread.h" @@ -117,3 +118,159 @@ random_next(void) return *seedp; } + + +/* This is the 32-bit CSPRNG adapted from the ChaCha20 algorithm from + * arc4random(3) and from the Linux kernel's get_random_u32(). + * + * This is intended to provide a high-speed CSPRNG implementation that + * can be used with some subsystems (such as conntrack) to generate + * quality RNG values from a high quality source of entropy. + */ + +#define CHACHA_ROUNDS 20 +#define CHACHA_KEYLEN 32 /* 256-bit key. */ + +/* Refill a page worth of keystream at a time to amortize the block cost. */ +#define CSPRNG_BUFSZ 4096 + +/* Reseed from the OS entropy pool after this many bytes served, matching + * the arc4random policy of periodic reseeding. */ +#define CSPRNG_RESEED (1600 * 1024) + +#define ROTL32(v, n) (((v) << (n)) | ((v) >> (32 - (n)))) + +#define QUARTERROUND(a, b, c, d) \ + a += b; d ^= a; d = ROTL32(d, 16); \ + c += d; b ^= c; b = ROTL32(b, 12); \ + a += b; d ^= a; d = ROTL32(d, 8); \ + c += d; b ^= c; b = ROTL32(b, 7) + +struct csprng { + uint32_t state[16]; /* ChaCha20 state: + * constant|key|counter|nonce. */ + uint8_t buf[CSPRNG_BUFSZ]; /* Buffered keystream. */ + size_t pos; /* Next unused byte in 'buf'. */ + size_t served; /* Bytes served since last reseed. */ + int initialized; +}; + +/* ChaCha20 constant: "expand 32-byte k". */ +static const uint8_t chacha_sigma[CHACHA_K_INPUT + 1] = "expand 32-byte k"; + +/* Current random state. */ +DEFINE_STATIC_PER_THREAD_DATA(struct csprng, cs_state, { .initialized = 0 }); + +/* Produces one 64-byte ChaCha20 block from 'input' (16 words) into 'out'. */ +void +chacha20_block(const uint32_t input[CHACHA_K_INPUT], uint8_t out[CHACHA_BLOCK]) +{ + uint32_t x[CHACHA_K_INPUT]; + int i; + + for (i = 0; i < 16; i++) { + x[i] = input[i]; + } + + for (i = 0; i < CHACHA_ROUNDS; i += 2) { + /* Column rounds. */ + QUARTERROUND(x[0], x[4], x[8], x[12]); + QUARTERROUND(x[1], x[5], x[9], x[13]); + QUARTERROUND(x[2], x[6], x[10], x[14]); + QUARTERROUND(x[3], x[7], x[11], x[15]); + /* Diagonal rounds. */ + QUARTERROUND(x[0], x[5], x[10], x[15]); + QUARTERROUND(x[1], x[6], x[11], x[12]); + QUARTERROUND(x[2], x[7], x[8], x[13]); + QUARTERROUND(x[3], x[4], x[9], x[14]); + } + + for (i = 0; i < 16; i++) { + ovs_store_le32(out + i * 4, x[i] + input[i]); + } +} + +/* (Re)keys the generator from 'key' (32 bytes) and resets the counter. */ +static void +csprng_rekey(struct csprng *c, const uint8_t key[CHACHA_KEYLEN]) +{ + int i; + + for (i = 0; i < 4; i++) { + c->state[i] = ovs_load_le32(chacha_sigma + i * 4); + } + for (i = 0; i < 8; i++) { + c->state[4 + i] = ovs_load_le32(key + i * 4); + } + /* Words 12..15: 64-bit counter + 64-bit nonce, all zeroed. */ + for (i = 12; i < 16; i++) { + c->state[i] = 0; + } +} + +static void +csprng_seed(struct csprng *c) +{ + uint8_t key[CHACHA_KEYLEN]; + + get_entropy_or_die(key, sizeof key); + csprng_rekey(c, key); + memset(key, 0, sizeof key); + + c->pos = sizeof c->buf; + c->served = 0; + c->initialized = 1; +} + +/* Fills csprng with fresh keystream, reserving the first 32 bytes to re-key + * the generator (fast key erasure / forward secrecy). */ +static void +csprng_refill(struct csprng *c) +{ + size_t off; + + for (off = 0; off < sizeof c->buf; off += CHACHA_BLOCK) { + chacha20_block(c->state, c->buf + off); + /* Increment the 64-bit block counter (words 12..13). */ + if (++c->state[12] == 0) { + c->state[13]++; + } + } + + /* Re-key from the first 32 bytes, then make them unavailable as output. */ + csprng_rekey(c, c->buf); + memset(c->buf, 0, CHACHA_KEYLEN); + c->pos = CHACHA_KEYLEN; +} + +void +cs_random_bytes(void *b, size_t l) +{ + struct csprng *c = cs_state_get(); + + /* c->buf isn't fully available for reading due to + * the initial 32-bytes from the block being used as a + * seeding counter. */ + ovs_assert(l < sizeof c->buf - CHACHA_KEYLEN); + + if (!c->initialized || c->served >= CSPRNG_RESEED) { + csprng_seed(c); + } + + if (c->pos + l > sizeof c->buf) { + csprng_refill(c); + } + + memcpy(b, c->buf + c->pos, l); + memset(c->buf + c->pos, 0, l); + c->pos += l; + c->served += l; +} + +uint32_t +cs_random_uint32(void) +{ + uint32_t r; + cs_random_bytes(&r, sizeof r); + return r; +} diff --git a/lib/random.h b/lib/random.h index 5fe50b725a..2d4e9a08d5 100644 --- a/lib/random.h +++ b/lib/random.h @@ -45,4 +45,19 @@ random_uint16(void) return random_uint32(); } +#define CHACHA_K_INPUT 16 /* ChaCha20 inblock size in bytes. */ +#define CHACHA_BLOCK 64 /* ChaCha20 block size in bytes. */ + +/* Used by the internal CSPRNG and by the block selftest. */ +void chacha20_block(const uint32_t input[CHACHA_K_INPUT], + uint8_t out[CHACHA_BLOCK]); + +void cs_random_bytes(void *, size_t); +uint32_t cs_random_uint32(void); + +static inline uint16_t cs_random_uint16(void) +{ + return cs_random_uint32(); +} + #endif /* random.h */ diff --git a/tests/library.at b/tests/library.at index 80ebe6ed8a..7f4e0b2732 100644 --- a/tests/library.at +++ b/tests/library.at @@ -149,6 +149,7 @@ nibble 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6 620 640 621 606 603 644 628 633 620 597 653 591 637 658 634 615 7 636 645 679 593 598 609 612 612 623 626 638 669 603 629 606 622 (expected values are 625) +ok: RFC 8439 2.3.2 block function ]) AT_CLEANUP diff --git a/tests/test-random.c b/tests/test-random.c index 542a49823f..e6c5bc5014 100644 --- a/tests/test-random.c +++ b/tests/test-random.c @@ -17,10 +17,19 @@ #include <config.h> #undef NDEBUG #include "random.h" +#include <assert.h> #include <stdio.h> #include <string.h> +#include "timeval.h" #include "ovstest.h" +static double +elapsed_sec(const struct timeval *start, const struct timeval *end) +{ + return (end->tv_sec - start->tv_sec) + + (end->tv_usec - start->tv_usec) / 1000000.0; +} + static void test_random_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) { @@ -74,6 +83,64 @@ test_random_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) printf("\n"); } printf("(expected values are %d)\n", N_ROUNDS / 16); + + /* Now for ChaCha20 test. */ + /* RFC 8439 section 2.3.2: the ChaCha20 block function. Key = 00..1f, + * block counter = 1, nonce = 00:00:00:09 00:00:00:4a 00:00:00:00. Note + * this is the RFC's 32-bit-counter/96-bit-nonce layout; chacha20_block() + * is agnostic to how words 12..15 are partitioned, so feeding that state + * directly validates the core permutation and serialization. */ + { + const uint32_t input[16] = { + 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574, + 0x03020100, 0x07060504, 0x0b0a0908, 0x0f0e0d0c, + 0x13121110, 0x17161514, 0x1b1a1918, 0x1f1e1d1c, + 0x00000001, 0x09000000, 0x4a000000, 0x00000000, + }; + static const uint8_t expected[64] = { + 0x10, 0xf1, 0xe7, 0xe4, 0xd1, 0x3b, 0x59, 0x15, + 0x50, 0x0f, 0xdd, 0x1f, 0xa3, 0x20, 0x71, 0xc4, + 0xc7, 0xd1, 0xf4, 0xc7, 0x33, 0xc0, 0x68, 0x03, + 0x04, 0x22, 0xaa, 0x9a, 0xc3, 0xd4, 0x6c, 0x4e, + 0xd2, 0x82, 0x64, 0x46, 0x07, 0x9f, 0xaa, 0x09, + 0x14, 0xc2, 0xd7, 0x05, 0xd9, 0x8b, 0x02, 0xa2, + 0xb5, 0x12, 0x9c, 0xd1, 0xde, 0x16, 0x4e, 0xb9, + 0xcb, 0xd0, 0x83, 0xe8, 0xa2, 0x50, 0x3c, 0x4e, + }; + uint8_t out[64]; + + chacha20_block(input, out); + + ovs_assert(!memcmp(out, expected, sizeof out)); + printf("ok: RFC 8439 2.3.2 block function\n"); + } +} + +static void +test_bench_random(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) +{ + enum { N_ROUNDS = 10000 }; + struct timeval start, end; + uint32_t x = 0; + int i; + + /* Benchmark the CSPRNG and PRNG performance. */ + xgettimeofday(&start); + for (i = 0; i < N_ROUNDS * N_ROUNDS; i++) { + x += random_uint32(); + } + xgettimeofday(&end); + printf("random_uint32: %f seconds\n", elapsed_sec(&start, &end)); + + xgettimeofday(&start); + for (i = 0; i < N_ROUNDS * N_ROUNDS; i++) { + x += cs_random_uint32(); + } + xgettimeofday(&end); + printf("cs_random_uint32: %f seconds\n", elapsed_sec(&start, &end)); + printf("accumulator: %u\n", x); /* NOTE: Keep this to prevent compiler + * from optimizing out the calls above. */ } OVSTEST_REGISTER("test-random", test_random_main); +OVSTEST_REGISTER("test-bench-random", test_bench_random); -- 2.55.0 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
