commit 8cdd8b83539e57fb1891cce5b527dda335ab1452 Author: Nick Mathewson <nickm@torproject.org> Date: Fri Feb 8 16:28:05 2013 -0500 Fix numerous problems with Tor's weak RNG. We need a weak RNG in a couple of places where the strong RNG is both needless and too slow. We had been using the weak RNG from our platform's libc implementation, but that was problematic (because many platforms have exceptionally horrible weak RNGs -- like, ones that only return values between 0 and SHORT_MAX) and because we were using it in a way that was wrong for LCG-based weak RNGs. (We were counting on the low bits of the LCG output to be as random as the high ones, which isn't true.) This patch adds a separate type for a weak RNG, adds an LCG implementation for it, and uses that exclusively where we had been using the platform weak RNG. --- src/common/compat.c | 24 ------------------------ src/common/compat.h | 5 ----- src/common/crypto.c | 8 ++++---- src/common/crypto.h | 2 ++ src/common/util.c | 40 ++++++++++++++++++++++++++++++++++++++++ src/common/util.h | 14 ++++++++++++++ src/or/cpuworker.c | 11 +++++++++-- src/or/main.c | 1 + src/or/relay.c | 12 +++++++++++- src/or/relay.h | 2 ++ 10 files changed, 83 insertions(+), 36 deletions(-) diff --git a/src/common/compat.c b/src/common/compat.c index 3b15f8a..d7ce894 100644 --- a/src/common/compat.c +++ b/src/common/compat.c @@ -2059,30 +2059,6 @@ tor_lookup_hostname(const char *name, uint32_t *addr) return -1; } -/** Initialize the insecure libc RNG. */ -void -tor_init_weak_random(unsigned seed) -{ -#ifdef _WIN32 - srand(seed); -#else - srandom(seed); -#endif -} - -/** Return a randomly chosen value in the range 0..TOR_RAND_MAX. This - * entropy will not be cryptographically strong; do not rely on it - * for anything an adversary should not be able to predict. */ -long -tor_weak_random(void) -{ -#ifdef _WIN32 - return rand(); -#else - return random(); -#endif -} - /** Hold the result of our call to <b>uname</b>. */ static char uname_result[256]; /** True iff uname_result is set. */ diff --git a/src/common/compat.h b/src/common/compat.h index d2944e6..036acfb 100644 --- a/src/common/compat.h +++ b/src/common/compat.h @@ -582,11 +582,6 @@ typedef enum { SOCKS5_ADDRESS_TYPE_NOT_SUPPORTED = 0x08, } socks5_reply_status_t; -/* ===== Insecure rng */ -void tor_init_weak_random(unsigned seed); -long tor_weak_random(void); -#define TOR_RAND_MAX (RAND_MAX) - /* ===== OS compatibility */ const char *get_uname(void); diff --git a/src/common/crypto.c b/src/common/crypto.c index 70bd452..22d57c7 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -2337,12 +2337,12 @@ crypto_dh_free(crypto_dh_t *dh) (OPENSSL_VERSION_NUMBER >= OPENSSL_V(0,9,8,'c')) /** Set the seed of the weak RNG to a random value. */ -static void -seed_weak_rng(void) +void +crypto_seed_weak_rng(tor_weak_rng_t *rng) { unsigned seed; crypto_rand((void*)&seed, sizeof(seed)); - tor_init_weak_random(seed); + tor_init_weak_random(rng, seed); } /** Try to get <b>out_len</b> bytes of the strongest entropy we can generate, @@ -2426,7 +2426,7 @@ crypto_seed_rng(int startup) } memwipe(buf, 0, sizeof(buf)); - seed_weak_rng(); + if (rand_poll_ok || load_entropy_ok) return 0; else diff --git a/src/common/crypto.h b/src/common/crypto.h index 08efc80..12fcfae 100644 --- a/src/common/crypto.h +++ b/src/common/crypto.h @@ -256,6 +256,8 @@ int crypto_strongest_rand(uint8_t *out, size_t out_len); int crypto_rand_int(unsigned int max); uint64_t crypto_rand_uint64(uint64_t max); double crypto_rand_double(void); +struct tor_weak_rng_t; +void crypto_seed_weak_rng(struct tor_weak_rng_t *rng); char *crypto_random_hostname(int min_rand_len, int max_rand_len, const char *prefix, const char *suffix); diff --git a/src/common/util.c b/src/common/util.c index 93e2ba8..0384040 100644 --- a/src/common/util.c +++ b/src/common/util.c @@ -4996,3 +4996,43 @@ tor_check_port_forwarding(const char *filename, } } +/** Initialize the insecure RNG <b>rng</b> from a seed value <b>seed</b>. */ +void +tor_init_weak_random(tor_weak_rng_t *rng, unsigned seed) +{ + rng->state = (uint32_t)(seed & 0x7fffffff); +} + +/** Return a randomly chosen value in the range 0..TOR_WEAK_RANDOM_MAX based + * on the RNG state of <b>rng</b>. This entropy will not be cryptographically + * strong; do not rely on it for anything an adversary should not be able to + * predict. */ +int32_t +tor_weak_random(tor_weak_rng_t *rng) +{ + /* Here's a linear congruential generator. OpenBSD and glibc use it. We + * don't want to use windows's rand(), because that returns values in the + * range 0..INT16_MAX, which just isn't enough. */ + rng->state = (rng->state * 1103515245 + 12345) & 0x7fffffff; + return (int32_t) rng->state; +} + +/** Return a random number in the range [0 , <b>top</b>). {That is, the range + * of integers i such that 0 <= i < top.} Chooses uniformly. Requires that + * top is greater than 0. This randomness is not cryptographically strong; do + * not rely on it for anything an adversary should not be able to predict. */ +int32_t +tor_weak_random_range(tor_weak_rng_t *rng, int32_t top) +{ + /* We don't want to just do tor_weak_random() % top, since random() is often + * implemented with an LCG whose modulus is a power of 2, and those are + * cyclic in their low-order bits. */ + int divisor, result; + tor_assert(top > 0); + divisor = TOR_WEAK_RANDOM_MAX / top; + do { + result = (int32_t)(tor_weak_random(rng) / divisor); + } while (result >= top); + return result; +} + diff --git a/src/common/util.h b/src/common/util.h index 911b1b5..ac88f1c 100644 --- a/src/common/util.h +++ b/src/common/util.h @@ -494,6 +494,20 @@ int tor_terminate_process(process_handle_t *process_handle); void tor_process_handle_destroy(process_handle_t *process_handle, int also_terminate_process); +/* ===== Insecure rng */ +typedef struct tor_weak_rng_t { + uint32_t state; +} tor_weak_rng_t; + +#define TOR_WEAK_RNG_INIT {383745623} +#define TOR_WEAK_RANDOM_MAX (INT_MAX) +void tor_init_weak_random(tor_weak_rng_t *weak_rng, unsigned seed); +int32_t tor_weak_random(tor_weak_rng_t *weak_rng); +int32_t tor_weak_random_range(tor_weak_rng_t *rng, int32_t top); +/** Randomly return true according to <b>rng</b> with probability 1 in + * <b>n</b> */ +#define tor_weak_random_one_in_n(rng, n) (0==tor_weak_random_range((rng),(n))) + #ifdef UTIL_PRIVATE /* Prototypes for private functions only used by util.c (and unit tests) */ diff --git a/src/or/cpuworker.c b/src/or/cpuworker.c index b5740f0..6b52f3b 100644 --- a/src/or/cpuworker.c +++ b/src/or/cpuworker.c @@ -196,8 +196,10 @@ static uint64_t onionskins_usec_roundtrip[MAX_ONION_HANDSHAKE_TYPE+1]; * time. (microseconds) */ #define MAX_BELIEVABLE_ONIONSKIN_DELAY (2*1000*1000) +static tor_weak_rng_t request_sample_rng = TOR_WEAK_RNG_INIT; + /** Return true iff we'd like to measure a handshake of type - * <b>onionskin_type</b>. */ + * <b>onionskin_type</b>. Call only from the main thread. */ static int should_time_request(uint16_t onionskin_type) { @@ -210,7 +212,7 @@ should_time_request(uint16_t onionskin_type) return 1; /** Otherwise, measure with P=1/128. We avoid doing this for every * handshake, since the measurement itself can take a little time. */ - return tor_weak_random() < (TOR_RAND_MAX/128); + return tor_weak_random_one_in_n(&request_sample_rng, 128); } /** Return an estimate of how many microseconds we will need for a single @@ -560,6 +562,7 @@ static void spawn_enough_cpuworkers(void) { int num_cpuworkers_needed = get_num_cpus(get_options()); + int reseed = 0; if (num_cpuworkers_needed < MIN_CPUWORKERS) num_cpuworkers_needed = MIN_CPUWORKERS; @@ -572,7 +575,11 @@ spawn_enough_cpuworkers(void) return; } num_cpuworkers++; + reseed++; } + + if (reseed) + crypto_seed_weak_rng(&request_sample_rng); } /** Take a pending task from the queue and assign it to 'cpuworker'. */ diff --git a/src/or/main.c b/src/or/main.c index 79b0f25..aa601e5 100644 --- a/src/or/main.c +++ b/src/or/main.c @@ -2391,6 +2391,7 @@ tor_init(int argc, char *argv[]) log_err(LD_BUG, "Unable to initialize OpenSSL. Exiting."); return -1; } + stream_choice_seed_weak_rng(); return 0; } diff --git a/src/or/relay.c b/src/or/relay.c index 5d06fd9..cbb2aca 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -70,6 +70,9 @@ uint64_t stats_n_relay_cells_relayed = 0; */ uint64_t stats_n_relay_cells_delivered = 0; +/** Used to tell which stream to read from first on a circuit. */ +static tor_weak_rng_t stream_choice_rng = TOR_WEAK_RNG_INIT; + /** Update digest from the payload of cell. Assign integrity part to * cell. */ @@ -1740,6 +1743,12 @@ circuit_resume_edge_reading(circuit_t *circ, crypt_path_t *layer_hint) circ, layer_hint); } +void +stream_choice_seed_weak_rng(void) +{ + crypto_seed_weak_rng(&stream_choice_rng); +} + /** A helper function for circuit_resume_edge_reading() above. * The arguments are the same, except that <b>conn</b> is the head * of a linked list of edge streams that should each be considered. @@ -1784,10 +1793,11 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, int num_streams = 0; for (conn = first_conn; conn; conn = conn->next_stream) { num_streams++; - if ((tor_weak_random() % num_streams)==0) + if (tor_weak_random_one_in_n(&stream_choice_rng, num_streams)) { chosen_stream = conn; /* Invariant: chosen_stream has been chosen uniformly at random from * among the first num_streams streams on first_conn. */ + } } } diff --git a/src/or/relay.h b/src/or/relay.h index d8da9ea..9e2d8af 100644 --- a/src/or/relay.h +++ b/src/or/relay.h @@ -65,6 +65,8 @@ const uint8_t *decode_address_from_payload(tor_addr_t *addr_out, int payload_len); void circuit_clear_cell_queue(circuit_t *circ, channel_t *chan); +void stream_choice_seed_weak_rng(void); + #ifdef RELAY_PRIVATE int relay_crypt(circuit_t *circ, cell_t *cell, cell_direction_t cell_direction, crypt_path_t **layer_hint, char *recognized);