diff options
| -rw-r--r-- | src/common/compat.c | 24 | ||||
| -rw-r--r-- | src/common/compat.h | 5 | ||||
| -rw-r--r-- | src/common/crypto.c | 8 | ||||
| -rw-r--r-- | src/common/crypto.h | 2 | ||||
| -rw-r--r-- | src/common/util.c | 40 | ||||
| -rw-r--r-- | src/common/util.h | 14 | ||||
| -rw-r--r-- | src/or/cpuworker.c | 11 | ||||
| -rw-r--r-- | src/or/main.c | 1 | ||||
| -rw-r--r-- | src/or/relay.c | 12 | ||||
| -rw-r--r-- | 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 3b15f8ad2..d7ce89479 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 d2944e6f4..036acfba7 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 70bd45299..22d57c7c8 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 08efc801d..12fcfae27 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 93e2ba8e1..03840402b 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 911b1b5a3..ac88f1ca1 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 b5740f091..6b52f3b5d 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 79b0f2577..aa601e5a4 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 5d06fd93f..cbb2aca10 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 d8da9ea1b..9e2d8af1e 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); |