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 following references can help with understanding the implementation: * 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" Assisted-by: LLM (claude, opencode, sonnet, opus, qwen3.8) Signed-off-by: Aaron Conole <[email protected]> --- v2->v3: * Update the verbiage around the implementations origins * Still exists the possiblity to abort on reseed * Fixed the CHACHA_K_INPUT comment * Fixed the chacha_sigma constant definition + comment * Documented maximum length in csprng_random_bytes * Introduce ovs_memzero that will clear memory without eliding the operations * Zero out the chacha20_block lib/random.c | 159 ++++++++++++++++++++++++++++++++++++++++++++ lib/random.h | 17 +++++ lib/util.c | 14 ++++ lib/util.h | 5 ++ tests/library.at | 1 + tests/test-random.c | 66 ++++++++++++++++++ 6 files changed, 262 insertions(+) diff --git a/lib/random.c b/lib/random.c index c0bc659d19..d2f28866a2 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,161 @@ random_next(void) return *seedp; } + + +/* This is a 32-bit CSPRNG adapted from the ChaCha20 algorithm described in + * RFC 7539 and RFC 8439, similar to arc4random(3) and 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". Must be at least 16 bytes + NUL. */ +static const uint8_t chacha_sigma[] = "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]); + } + + ovs_memzero(x, sizeof x); +} + +/* (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); + ovs_memzero(key, 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); + ovs_memzero(c->buf, 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 because the first 32 bytes + * of every refill are consumed as the next key. */ + 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); + ovs_memzero(c->buf + c->pos, 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..77792e28f1 100644 --- a/lib/random.h +++ b/lib/random.h @@ -45,4 +45,21 @@ random_uint16(void) return random_uint32(); } +#define CHACHA_K_INPUT 16 /* ChaCha20 input block size in words. */ +#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]); + +/* Fills 'b' with 'l' cryptographically secure random bytes. 'l' must not be + * larger than 4064; callers needing more bytes should make multiple calls. */ +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/lib/util.c b/lib/util.c index 06a692ea22..905d126391 100644 --- a/lib/util.c +++ b/lib/util.c @@ -408,6 +408,20 @@ ovs_strzcpy(char *dst, const char *src, size_t size) } } +/* Zeroes 'size' bytes of memory at 'ptr'. Unlike memset(), the compiler is + * not allowed to optimize this away, so it may be used to scrub sensitive + * data, such as keying material, from memory. */ +void +ovs_memzero(void *ptr, size_t size) +{ + volatile uint8_t *p = ptr; + size_t i; + + for (i = 0; i < size; i++) { + p[i] = 0; + } +} + /* * Returns true if 'str' ends with given 'suffix'. */ diff --git a/lib/util.h b/lib/util.h index 03f0c151f9..e494703416 100644 --- a/lib/util.h +++ b/lib/util.h @@ -201,6 +201,11 @@ nullable_memset(void *dst, int c, size_t n) } } +/* Zeroes 'size' bytes of memory at 'ptr'. Unlike memset(), the compiler is + * not allowed to optimize this away, so it may be used to scrub sensitive + * data, such as keying material, from memory. */ +void ovs_memzero(void *ptr, size_t size); + /* Copy string SRC to DST, but no more bytes than the shorter of DST or SRC. * DST and SRC must both be char arrays, not pointers, and with GNU C, this * raises a compiler error if either DST or SRC is a pointer instead of an 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..bb1d393962 100644 --- a/tests/test-random.c +++ b/tests/test-random.c @@ -19,8 +19,16 @@ #include "random.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 +82,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_BENCH = 10000000 }; + struct timeval start, end; + uint32_t x = 0; + int i; + + /* Benchmark the CSPRNG and PRNG performance. */ + xgettimeofday(&start); + for (i = 0; i < N_BENCH; i++) { + x += random_uint32(); + } + xgettimeofday(&end); + printf("random_uint32: %f seconds\n", elapsed_sec(&start, &end)); + + xgettimeofday(&start); + for (i = 0; i < N_BENCH; 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.56.0 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
