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.

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);