123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439 |
- /* 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
- #define CRYPTO_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/thread/threads.h"
- #include "lib/log/util_bug.h"
- #ifdef HAVE_SYS_TYPES_H
- #include <sys/types.h>
- #endif
- #ifdef HAVE_UNISTD_H
- #include <unistd.h>
- #endif
- #include <string.h>
- #ifdef NOINHERIT_CAN_FAIL
- #define CHECK_PID
- #endif
- #ifdef CHECK_PID
- #define PID_FIELD_LEN sizeof(pid_t)
- #else
- #define PID_FIELD_LEN 0
- #endif
- /* 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 - PID_FIELD_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_strongest_rand()?
- *
- * This value may be negative if unit tests are enabled. If so, it
- * indicates that we should never mix in extra data from
- * crypto_strongest_rand().
- */
- int16_t n_till_reseed;
- /** How many bytes are remaining in cbuf.bytes? */
- uint16_t bytes_left;
- #ifdef CHECK_PID
- /** Which process owns this fast_rng? If this value is zero, we do not
- * need to test the owner. */
- pid_t owner;
- #endif
- 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, you should probably look at get_thread_fast_rng(). Alternatively,
- * use crypto_rand(), wrap this in a mutex.
- **/
- crypto_fast_rng_t *
- crypto_fast_rng_new_from_seed(const uint8_t *seed)
- {
- unsigned inherit = INHERIT_RES_KEEP;
- /* 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,
- &inherit);
- 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;
- #ifdef CHECK_PID
- if (inherit == INHERIT_RES_KEEP) {
- /* This value will neither be dropped nor zeroed after fork, so we need to
- * check our pid to make sure we are not sharing it across a fork. This
- * can be expensive if the pid value isn't cached, sadly.
- */
- result->owner = getpid();
- }
- #elif defined(_WIN32)
- /* Windows can't fork(), so there's no need to noinherit. */
- #else
- /* We decided above that noinherit would always do _something_. Assert here
- * that we were correct. */
- tor_assertf(inherit != INHERIT_RES_KEEP,
- "We failed to create a non-inheritable memory region, even "
- "though we believed such a failure to be impossible! This is "
- "probably a bug in Tor support for your platform; please report "
- "it.");
- #endif /* defined(CHECK_PID) || ... */
- return result;
- }
- #ifdef TOR_UNIT_TESTS
- /**
- * Unit tests only: prevent a crypto_fast_rng_t from ever mixing in more
- * entropy.
- */
- void
- crypto_fast_rng_disable_reseed(crypto_fast_rng_t *rng)
- {
- rng->n_till_reseed = -1;
- }
- #endif /* defined(TOR_UNIT_TESTS) */
- /**
- * 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: mix additional entropy into <b>rng</b> by using our XOF to mix the
- * old value for the seed with some additional bytes from
- * crypto_strongest_rand().
- **/
- static void
- crypto_fast_rng_add_entopy(crypto_fast_rng_t *rng)
- {
- 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);
- }
- /**
- * 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)
- {
- rng->n_till_reseed--;
- if (rng->n_till_reseed == 0) {
- /* It's time to reseed the RNG. */
- crypto_fast_rng_add_entopy(rng);
- rng->n_till_reseed = RESEED_AFTER;
- } else if (rng->n_till_reseed < 0) {
- #ifdef TOR_UNIT_TESTS
- /* Reseeding is disabled for testing; never do it on this prng. */
- rng->n_till_reseed = -1;
- #else
- /* If testing is disabled, this shouldn't be able to become negative. */
- tor_assert_unreached();
- #endif /* defined(TOR_UNIT_TESTS) */
- }
- /* 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)
- {
- #ifdef CHECK_PID
- if (rng->owner) {
- /* Note that we only need to do this check when we have owner set: that
- * is, when our attempt to block inheriting failed, and the result was
- * INHERIT_RES_KEEP.
- *
- * If the result was INHERIT_RES_DROP, then any attempt to access the rng
- * memory after forking will crash.
- *
- * If the result was INHERIT_RES_ZERO, then forking will set the bytes_left
- * and n_till_reseed fields to zero. This function will call
- * crypto_fast_rng_refill(), which will in turn reseed the PRNG.
- *
- * So we only need to do this test in the case when mmap_anonymous()
- * returned INHERIT_KEEP. We avoid doing it needlessly, since getpid() is
- * often a system call, and that can be slow.
- */
- tor_assert(rng->owner == getpid());
- }
- #endif /* defined(CHECK_PID) */
- 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 /* defined(TOR_UNIT_TESTS) */
- /**
- * Thread-local instance for our fast RNG.
- **/
- static tor_threadlocal_t thread_rng;
- /**
- * Return a per-thread fast RNG, initializing it if necessary.
- *
- * You do not need to free this yourself.
- *
- * It is NOT safe to share this value across threads.
- **/
- crypto_fast_rng_t *
- get_thread_fast_rng(void)
- {
- crypto_fast_rng_t *rng = tor_threadlocal_get(&thread_rng);
- if (PREDICT_UNLIKELY(rng == NULL)) {
- rng = crypto_fast_rng_new();
- tor_threadlocal_set(&thread_rng, rng);
- }
- return rng;
- }
- /**
- * Used when a thread is exiting: free the per-thread fast RNG if needed.
- * Invoked from the crypto subsystem's thread-cleanup code.
- **/
- void
- destroy_thread_fast_rng(void)
- {
- crypto_fast_rng_t *rng = tor_threadlocal_get(&thread_rng);
- if (!rng)
- return;
- crypto_fast_rng_free(rng);
- tor_threadlocal_set(&thread_rng, NULL);
- }
- #ifdef TOR_UNIT_TESTS
- /**
- * Replace the current thread's rng with <b>rng</b>. For use by the
- * unit tests only. Returns the previous thread rng.
- **/
- crypto_fast_rng_t *
- crypto_replace_thread_fast_rng(crypto_fast_rng_t *rng)
- {
- crypto_fast_rng_t *old_rng = tor_threadlocal_get(&thread_rng);
- tor_threadlocal_set(&thread_rng, rng);
- return old_rng;
- }
- #endif /* defined(TOR_UNIT_TESTS) */
- /**
- * Initialize the global thread-local key that will be used to keep track
- * of per-thread fast RNG instances. Called from the crypto subsystem's
- * initialization code.
- **/
- void
- crypto_rand_fast_init(void)
- {
- tor_threadlocal_init(&thread_rng);
- }
- /**
- * Initialize the global thread-local key that will be used to keep track
- * of per-thread fast RNG instances. Called from the crypto subsystem's
- * shutdown code.
- **/
- void
- crypto_rand_fast_shutdown(void)
- {
- destroy_thread_fast_rng();
- tor_threadlocal_destroy(&thread_rng);
- }
|