commit f3cbd6426cbb27b9ab4e5492a50a785cce77f805 Author: Nick Mathewson nickm@torproject.org Date: Tue Feb 5 12:49:04 2019 -0500
Implement a fast aes-ctr prng
This module is currently implemented to use the same technique as libottery (later used by the bsds' arc4random replacement), using AES-CTR-256 as its underlying stream cipher. It's backtracking- resistant immediately after each call, and prediction-resistant after a while.
Here's how it works:
We generate psuedorandom bytes using AES-CTR-256. We generate BUFLEN bytes at a time. When we do this, we keep the first SEED_LEN bytes as the key and the IV for our next invocation of AES_CTR, and yield the remaining BUFLEN - SEED_LEN bytes to the user as they invoke the PRNG. As we yield bytes to the user, we clear them from the buffer.
Every RESEED_AFTER times we refill the buffer, we mix in an additional SEED_LEN bytes from our strong PRNG into the seed.
If the user ever asks for a huge number of bytes at once, we pull SEED_LEN bytes from the PRNG and use them with our stream cipher to fill the user's request. --- src/lib/crypt_ops/crypto_rand.h | 32 ++++ src/lib/crypt_ops/crypto_rand_fast.c | 263 ++++++++++++++++++++++++++++++++ src/lib/crypt_ops/crypto_rand_numeric.c | 56 +++++-- src/lib/crypt_ops/include.am | 1 + src/test/test_crypto_rng.c | 117 ++++++++++++++ 5 files changed, 459 insertions(+), 10 deletions(-)
diff --git a/src/lib/crypt_ops/crypto_rand.h b/src/lib/crypt_ops/crypto_rand.h index cc2762842..8a81a4acd 100644 --- a/src/lib/crypt_ops/crypto_rand.h +++ b/src/lib/crypt_ops/crypto_rand.h @@ -16,6 +16,7 @@ #include "lib/cc/compat_compiler.h" #include "lib/cc/torint.h" #include "lib/testsupport/testsupport.h" +#include "lib/malloc/malloc.h"
/* random numbers */ int crypto_seed_rng(void) ATTR_WUR; @@ -24,6 +25,7 @@ void crypto_rand_unmocked(char *to, size_t n); void crypto_strongest_rand(uint8_t *out, size_t out_len); MOCK_DECL(void,crypto_strongest_rand_,(uint8_t *out, size_t out_len)); int crypto_rand_int(unsigned int max); +unsigned crypto_rand_uint(unsigned limit); int crypto_rand_int_range(unsigned int min, unsigned int max); uint64_t crypto_rand_uint64_range(uint64_t min, uint64_t max); time_t crypto_rand_time_range(time_t min, time_t max); @@ -41,6 +43,36 @@ void *smartlist_choose(const struct smartlist_t *sl); void smartlist_shuffle(struct smartlist_t *sl); int crypto_force_rand_ssleay(void);
+/** + * A fast PRNG, for use when the PRNG provided by our crypto library isn't + * fast enough. This one _should_ be cryptographically strong, but + * has seen less auditing than the PRNGs in OpenSSL and NSS. Use with + * caution. + * + * Note that this object is NOT thread-safe. If you need a thread-safe + * prng, use crypto_rand(), or wrap this in a mutex. + **/ +typedef struct crypto_fast_rng_t crypto_fast_rng_t; +/** + * Number of bytes used to seed a crypto_rand_fast_t. + **/ +crypto_fast_rng_t *crypto_fast_rng_new(void); +#define CRYPTO_FAST_RNG_SEED_LEN 48 +crypto_fast_rng_t *crypto_fast_rng_new_from_seed(const uint8_t *seed); +void crypto_fast_rng_getbytes(crypto_fast_rng_t *rng, uint8_t *out, size_t n); +void crypto_fast_rng_free_(crypto_fast_rng_t *); +#define crypto_fast_rng_free(c) \ + FREE_AND_NULL(crypto_fast_rng_t, crypto_fast_rng_free_, (c)) + +unsigned crypto_fast_rng_get_uint(crypto_fast_rng_t *rng, unsigned limit); +uint64_t crypto_fast_rng_get_uint64(crypto_fast_rng_t *rng, uint64_t limit); +double crypto_fast_rng_get_double(crypto_fast_rng_t *rng); + +#if defined(TOR_UNIT_TESTS) +/* Used for white-box testing */ +size_t crypto_fast_rng_get_bytes_used_per_stream(void); +#endif + #ifdef CRYPTO_RAND_PRIVATE
STATIC int crypto_strongest_rand_raw(uint8_t *out, size_t out_len); diff --git a/src/lib/crypt_ops/crypto_rand_fast.c b/src/lib/crypt_ops/crypto_rand_fast.c new file mode 100644 index 000000000..34e763bf5 --- /dev/null +++ b/src/lib/crypt_ops/crypto_rand_fast.c @@ -0,0 +1,263 @@ +/* Copyright (c) 2001, Matej Pfajfar. + * Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2019, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file crypto_rand_fast.c + * + * \brief A fast strong PRNG for use when our underlying cryptographic + * library's PRNG isn't fast enough. + **/ + +/* This library is currently implemented to use the same implementation + * technique as libottery, using AES-CTR-256 as our underlying stream cipher. + * It's backtracking-resistant immediately, and prediction-resistant after + * a while. + * + * Here's how it works: + * + * We generate pseudorandom bytes using AES-CTR-256. We generate BUFLEN bytes + * at a time. When we do this, we keep the first SEED_LEN bytes as the key + * and the IV for our next invocation of AES_CTR, and yield the remaining + * BUFLEN - SEED_LEN bytes to the user as they invoke the PRNG. As we yield + * bytes to the user, we clear them from the buffer. + * + * After we have refilled the buffer RESEED_AFTER times, we mix in an + * additional SEED_LEN bytes from our strong PRNG into the seed. + * + * If the user ever asks for a huge number of bytes at once, we pull SEED_LEN + * bytes from the PRNG and use them with our stream cipher to fill the user's + * request. + */ + +#define CRYPTO_RAND_FAST_PRIVATE + +#include "lib/crypt_ops/crypto_rand.h" +#include "lib/crypt_ops/crypto_cipher.h" +#include "lib/crypt_ops/crypto_digest.h" +#include "lib/crypt_ops/crypto_util.h" +#include "lib/intmath/cmp.h" +#include "lib/cc/ctassert.h" +#include "lib/malloc/map_anon.h" + +#include "lib/log/util_bug.h" + +#include <string.h> + +/* Alias for CRYPTO_FAST_RNG_SEED_LEN to make our code shorter. + */ +#define SEED_LEN (CRYPTO_FAST_RNG_SEED_LEN) + +/* The amount of space that we mmap for a crypto_fast_rng_t. + */ +#define MAPLEN 4096 + +/* The number of random bytes that we can yield to the user after each + * time we fill a crypto_fast_rng_t's buffer. + */ +#define BUFLEN (MAPLEN - 2*sizeof(uint16_t) - SEED_LEN) + +/* The number of buffer refills after which we should fetch more + * entropy from crypto_strongest_rand(). + */ +#define RESEED_AFTER 16 + +/* The length of the stream cipher key we will use for the PRNG, in bytes. + */ +#define KEY_LEN (CRYPTO_FAST_RNG_SEED_LEN - CIPHER_IV_LEN) +/* The length of the stream cipher key we will use for the PRNG, in bits. + */ +#define KEY_BITS (KEY_LEN * 8) + +/* Make sure that we have a key length we can actually use with AES. */ +CTASSERT(KEY_BITS == 128 || KEY_BITS == 192 || KEY_BITS == 256); + +struct crypto_fast_rng_t { + /** How many more fills does this buffer have before we should mix + * in the output of crypto_rand()? */ + uint16_t n_till_reseed; + /** How many bytes are remaining in cbuf.bytes? */ + uint16_t bytes_left; + struct cbuf { + /** The seed (key and IV) that we will use the next time that we refill + * cbuf. */ + uint8_t seed[SEED_LEN]; + /** + * Bytes that we are yielding to the user. The next byte to be + * yielded is at bytes[BUFLEN-bytes_left]; all other bytes in this + * array are set to zero. + */ + uint8_t bytes[BUFLEN]; + } buf; +}; + +/* alignof(uint8_t) should be 1, so there shouldn't be any padding in cbuf. + */ +CTASSERT(sizeof(struct cbuf) == BUFLEN+SEED_LEN); +/* We're trying to fit all of the RNG state into a nice mmapable chunk. + */ +CTASSERT(sizeof(crypto_fast_rng_t) <= MAPLEN); + +/** + * Initialize and return a new fast PRNG, using a strong random seed. + * + * Note that this object is NOT thread-safe. If you need a thread-safe + * prng, use crypto_rand(), or wrap this in a mutex. + **/ +crypto_fast_rng_t * +crypto_fast_rng_new(void) +{ + uint8_t seed[SEED_LEN]; + crypto_strongest_rand(seed, sizeof(seed)); + crypto_fast_rng_t *result = crypto_fast_rng_new_from_seed(seed); + memwipe(seed, 0, sizeof(seed)); + return result; +} + +/** + * Initialize and return a new fast PRNG, using a seed value specified + * in <b>seed</b>. This value must be CRYPTO_FAST_RNG_SEED_LEN bytes + * long. + * + * Note that this object is NOT thread-safe. If you need a thread-safe + * prng, use crypto_rand(), or wrap this in a mutex. + **/ +crypto_fast_rng_t * +crypto_fast_rng_new_from_seed(const uint8_t *seed) +{ + /* We try to allocate this object as securely as we can, to avoid + * having it get dumped, swapped, or shared after fork. + */ + crypto_fast_rng_t *result = tor_mmap_anonymous(sizeof(*result), + ANONMAP_PRIVATE | ANONMAP_NOINHERIT); + + memcpy(result->buf.seed, seed, SEED_LEN); + /* Causes an immediate refill once the user asks for data. */ + result->bytes_left = 0; + result->n_till_reseed = RESEED_AFTER; + return result; +} + +/** + * Helper: create a crypto_cipher_t object from SEED_LEN bytes of + * input. The first KEY_LEN bytes are used as the stream cipher's key, + * and the remaining CIPHER_IV_LEN bytes are used as its IV. + **/ +static inline crypto_cipher_t * +cipher_from_seed(const uint8_t *seed) +{ + return crypto_cipher_new_with_iv_and_bits(seed, seed+KEY_LEN, KEY_BITS); +} + +/** + * Helper: refill the seed bytes and output buffer of <b>rng</b>, using + * the input seed bytes as input (key and IV) for the stream cipher. + * + * If the n_till_reseed counter has reached zero, mix more random bytes into + * the seed before refilling the buffer. + **/ +static void +crypto_fast_rng_refill(crypto_fast_rng_t *rng) +{ + if (rng->n_till_reseed-- == 0) { + /* It's time to reseed the RNG. We'll do this by using our XOF to mix the + * old value for the seed with some additional bytes from + * crypto_strongest_rand(). */ + crypto_xof_t *xof = crypto_xof_new(); + crypto_xof_add_bytes(xof, rng->buf.seed, SEED_LEN); + { + uint8_t seedbuf[SEED_LEN]; + crypto_strongest_rand(seedbuf, SEED_LEN); + crypto_xof_add_bytes(xof, seedbuf, SEED_LEN); + memwipe(seedbuf, 0, SEED_LEN); + } + crypto_xof_squeeze_bytes(xof, rng->buf.seed, SEED_LEN); + crypto_xof_free(xof); + + rng->n_till_reseed = RESEED_AFTER; + } + /* Now fill rng->buf with output from our stream cipher, initialized from + * that seed value. */ + crypto_cipher_t *c = cipher_from_seed(rng->buf.seed); + memset(&rng->buf, 0, sizeof(rng->buf)); + crypto_cipher_crypt_inplace(c, (char*)&rng->buf, sizeof(rng->buf)); + crypto_cipher_free(c); + + rng->bytes_left = sizeof(rng->buf.bytes); +} + +/** + * Release all storage held by <b>rng</b>. + **/ +void +crypto_fast_rng_free_(crypto_fast_rng_t *rng) +{ + if (!rng) + return; + memwipe(rng, 0, sizeof(*rng)); + tor_munmap_anonymous(rng, sizeof(*rng)); +} + +/** + * Helper: extract bytes from the PRNG, refilling it as necessary. Does not + * optimize the case when the user has asked for a huge output. + **/ +static void +crypto_fast_rng_getbytes_impl(crypto_fast_rng_t *rng, uint8_t *out, + const size_t n) +{ + size_t bytes_to_yield = n; + + while (bytes_to_yield) { + if (rng->bytes_left == 0) + crypto_fast_rng_refill(rng); + + const size_t to_copy = MIN(rng->bytes_left, bytes_to_yield); + + tor_assert(sizeof(rng->buf.bytes) >= rng->bytes_left); + uint8_t *copy_from = rng->buf.bytes + + (sizeof(rng->buf.bytes) - rng->bytes_left); + memcpy(out, copy_from, to_copy); + memset(copy_from, 0, to_copy); + + out += to_copy; + bytes_to_yield -= to_copy; + rng->bytes_left -= to_copy; + } +} + +/** + * Extract <b>n</b> bytes from <b>rng</b> into the buffer at <b>out</b>. + **/ +void +crypto_fast_rng_getbytes(crypto_fast_rng_t *rng, uint8_t *out, size_t n) +{ + if (PREDICT_UNLIKELY(n > BUFLEN)) { + /* The user has asked for a lot of output; generate it from a stream + * cipher seeded by the PRNG rather than by pulling it out of the PRNG + * directly. + */ + uint8_t seed[SEED_LEN]; + crypto_fast_rng_getbytes_impl(rng, seed, SEED_LEN); + crypto_cipher_t *c = cipher_from_seed(seed); + memset(out, 0, n); + crypto_cipher_crypt_inplace(c, (char*)out, n); + crypto_cipher_free(c); + memwipe(seed, 0, sizeof(seed)); + return; + } + + crypto_fast_rng_getbytes_impl(rng, out, n); +} + +#if defined(TOR_UNIT_TESTS) +/** for white-box testing: return the number of bytes that are returned from + * the user for each invocation of the stream cipher in this RNG. */ +size_t +crypto_fast_rng_get_bytes_used_per_stream(void) +{ + return BUFLEN; +} +#endif diff --git a/src/lib/crypt_ops/crypto_rand_numeric.c b/src/lib/crypt_ops/crypto_rand_numeric.c index d07657440..d02c5cdcf 100644 --- a/src/lib/crypt_ops/crypto_rand_numeric.c +++ b/src/lib/crypt_ops/crypto_rand_numeric.c @@ -31,9 +31,11 @@ } \ } while (0)
-/** Helper: Return a pseudorandom integer chosen uniformly from the - * values between 0 and limit-1 inclusive. */ -static unsigned +/** + * Return a pseudorandom integer chosen uniformly from the values between 0 + * and <b>limit</b>-1 inclusive. limit must be strictly between 0 and + * UINT_MAX. */ +unsigned crypto_rand_uint(unsigned limit) { tor_assert(limit < UINT_MAX); @@ -108,6 +110,14 @@ crypto_rand_uint64(uint64_t max) crypto_rand((char*)&val, sizeof(val))); }
+#if SIZEOF_INT == 4 +#define UINT_MAX_AS_DOUBLE 4294967296.0 +#elif SIZEOF_INT == 8 +#define UINT_MAX_AS_DOUBLE 1.8446744073709552e+19 +#else +#error SIZEOF_INT is neither 4 nor 8 +#endif /* SIZEOF_INT == 4 || ... */ + /** * Return a pseudorandom double d, chosen uniformly from the range * 0.0 <= d < 1.0. @@ -119,12 +129,38 @@ crypto_rand_double(void) * more than 32 bits of resolution */ unsigned int u; crypto_rand((char*)&u, sizeof(u)); -#if SIZEOF_INT == 4 -#define UINT_MAX_AS_DOUBLE 4294967296.0 -#elif SIZEOF_INT == 8 -#define UINT_MAX_AS_DOUBLE 1.8446744073709552e+19 -#else -#error SIZEOF_INT is neither 4 nor 8 -#endif /* SIZEOF_INT == 4 || ... */ + return ((double)u) / UINT_MAX_AS_DOUBLE; +} + +/** + * As crypto_rand_uint, but extract the result from a crypto_fast_rng_t + */ +unsigned +crypto_fast_rng_get_uint(crypto_fast_rng_t *rng, unsigned limit) +{ + tor_assert(limit < UINT_MAX); + IMPLEMENT_RAND_UNSIGNED(unsigned, UINT_MAX, limit, + crypto_fast_rng_getbytes(rng, (void*)&val, sizeof(val))); +} + +/** + * As crypto_rand_uint64, but extract the result from a crypto_fast_rng_t. + */ +uint64_t +crypto_fast_rng_get_uint64(crypto_fast_rng_t *rng, uint64_t limit) +{ + tor_assert(limit < UINT64_MAX); + IMPLEMENT_RAND_UNSIGNED(uint64_t, UINT64_MAX, limit, + crypto_fast_rng_getbytes(rng, (void*)&val, sizeof(val))); +} + +/** + * As crypto_rand_, but extract the result from a crypto_fast_rng_t. + */ +double +crypto_fast_rng_get_double(crypto_fast_rng_t *rng) +{ + unsigned int u; + crypto_fast_rng_getbytes(rng, (void*)&u, sizeof(u)); return ((double)u) / UINT_MAX_AS_DOUBLE; } diff --git a/src/lib/crypt_ops/include.am b/src/lib/crypt_ops/include.am index 19cfee135..473044014 100644 --- a/src/lib/crypt_ops/include.am +++ b/src/lib/crypt_ops/include.am @@ -17,6 +17,7 @@ src_lib_libtor_crypt_ops_a_SOURCES = \ src/lib/crypt_ops/crypto_ope.c \ src/lib/crypt_ops/crypto_pwbox.c \ src/lib/crypt_ops/crypto_rand.c \ + src/lib/crypt_ops/crypto_rand_fast.c \ src/lib/crypt_ops/crypto_rand_numeric.c \ src/lib/crypt_ops/crypto_rsa.c \ src/lib/crypt_ops/crypto_s2k.c \ diff --git a/src/test/test_crypto_rng.c b/src/test/test_crypto_rng.c index 008753d97..0513d2a80 100644 --- a/src/test/test_crypto_rng.c +++ b/src/test/test_crypto_rng.c @@ -173,6 +173,121 @@ test_crypto_rng_strongest(void *arg) #undef N }
+static void +test_crypto_rng_fast(void *arg) +{ + (void)arg; + crypto_fast_rng_t *rng = crypto_fast_rng_new(); + tt_assert(rng); + + /* Rudimentary black-block test to make sure that our prng outputs + * have all bits sometimes on and all bits sometimes off. */ + uint64_t m1 = 0, m2 = ~(uint64_t)0; + const int N = 128; + + for (int i=0; i < N; ++i) { + uint64_t v; + crypto_fast_rng_getbytes(rng, (void*)&v, sizeof(v)); + m1 |= v; + m2 &= v; + } + + tt_u64_op(m1, OP_EQ, ~(uint64_t)0); + tt_u64_op(m2, OP_EQ, 0); + + /* Check range functions. */ + int counts[5]; + memset(counts, 0, sizeof(counts)); + for (int i=0; i < N; ++i) { + unsigned u = crypto_fast_rng_get_uint(rng, 5); + tt_int_op(u, OP_GE, 0); + tt_int_op(u, OP_LT, 5); + counts[u]++; + + uint64_t u64 = crypto_fast_rng_get_uint64(rng, UINT64_C(1)<<40); + tt_u64_op(u64, OP_GE, 0); + tt_u64_op(u64, OP_LT, UINT64_C(1)<<40); + } + + /* All values should have come up once. */ + for (int i=0; i<5; ++i) { + tt_int_op(counts[i], OP_GT, 0); + } + + done: + crypto_fast_rng_free(rng); +} + +static void +test_crypto_rng_fast_whitebox(void *arg) +{ + (void)arg; + const size_t buflen = crypto_fast_rng_get_bytes_used_per_stream(); + char *buf = tor_malloc_zero(buflen); + char *buf2 = tor_malloc_zero(buflen); + + crypto_cipher_t *cipher = NULL; + uint8_t seed[CRYPTO_FAST_RNG_SEED_LEN]; + memset(seed, 0, sizeof(seed)); + + /* Start with a prng with zero key and zero IV. */ + crypto_fast_rng_t *rng = crypto_fast_rng_new_from_seed(seed); + tt_assert(rng); + + /* We'll use a stream cipher to keep in sync */ + cipher = crypto_cipher_new_with_iv_and_bits(seed, seed+32, 256); + + /* The first 48 bytes are used for the next seed -- let's make sure we have + * them. + */ + memset(seed, 0, sizeof(seed)); + crypto_cipher_crypt_inplace(cipher, (char*)seed, sizeof(seed)); + + /* if we get 128 bytes, they should match the bytes from the aes256-counter + * stream, starting at position 48. + */ + crypto_fast_rng_getbytes(rng, (uint8_t*)buf, 128); + memset(buf2, 0, 128); + crypto_cipher_crypt_inplace(cipher, buf2, 128); + tt_mem_op(buf, OP_EQ, buf2, 128); + + /* Try that again, with an odd number of bytes. */ + crypto_fast_rng_getbytes(rng, (uint8_t*)buf, 199); + memset(buf2, 0, 199); + crypto_cipher_crypt_inplace(cipher, buf2, 199); + tt_mem_op(buf, OP_EQ, buf2, 199); + + /* Make sure that refilling works as expected: skip all but the last 5 bytes + * of this steam. */ + size_t skip = buflen - (199+128) - 5; + crypto_fast_rng_getbytes(rng, (uint8_t*)buf, skip); + crypto_cipher_crypt_inplace(cipher, buf2, skip); + + /* Now get the next 128 bytes. The first 5 will come from this stream, and + * the next 5 will come from the stream keyed by the new value of 'seed'. */ + crypto_fast_rng_getbytes(rng, (uint8_t*)buf, 128); + memset(buf2, 0, 128); + crypto_cipher_crypt_inplace(cipher, buf2, 5); + crypto_cipher_free(cipher); + cipher = crypto_cipher_new_with_iv_and_bits(seed, seed+32, 256); + memset(seed, 0, sizeof(seed)); + crypto_cipher_crypt_inplace(cipher, (char*)seed, sizeof(seed)); + crypto_cipher_crypt_inplace(cipher, buf2+5, 128-5); + tt_mem_op(buf, OP_EQ, buf2, 128); + + /* And check the next 7 bytes to make sure we didn't discard anything. */ + crypto_fast_rng_getbytes(rng, (uint8_t*)buf, 7); + memset(buf2, 0, 7); + crypto_cipher_crypt_inplace(cipher, buf2, 7); + tt_mem_op(buf, OP_EQ, buf2, 7); + + done: + crypto_fast_rng_free(rng); + crypto_cipher_free(cipher); + tor_free(buf); + tor_free(buf2); +} + struct testcase_t crypto_rng_tests[] = { { "rng", test_crypto_rng, 0, NULL, NULL }, { "rng_range", test_crypto_rng_range, 0, NULL, NULL }, @@ -183,5 +298,7 @@ struct testcase_t crypto_rng_tests[] = { &passthrough_setup, (void*)"nofallback" }, { "rng_strongest_broken", test_crypto_rng_strongest, TT_FORK, &passthrough_setup, (void*)"broken" }, + { "fast", test_crypto_rng_fast, 0, NULL, NULL }, + { "fast_whitebox", test_crypto_rng_fast_whitebox, 0, NULL, NULL }, END_OF_TESTCASES };