Merge remote-tracking branch 'public/bug7801_v2'

12 files changed, 144 insertions, 38 deletions

diff --git a/changes/bug7801 b/changes/bug7801
new file mode 100644
index 000000000..1d6d021f3
--- /dev/null
+++ b/changes/bug7801
@@ -0,0 +1,13 @@
+  o Minor bugfixes:
+    - When choosing which stream on a formerly stalled circuit to wake
+      first, make better use of the platform's weak RNG.  Previously, we
+      had been using the % ("modulo") operator to try to generate a 1/N
+      chance of picking each stream, but this behaves badly with many
+      platforms' choice of weak RNG. Fix for bug 7801; bugfix on
+      0.2.2.20-alpha.
+    - Use our own weak RNG when we need a weak RNG. Windows's rand()
+      and Irix's random() only return 15 bits; Solaris's random()
+      returns more bits but its RAND_MAX says it only returns 15, and
+      so on.  Fixes another aspect of bug 7801; bugfix on
+      0.2.2.20-alpha.
+
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 fa071e555..f9eb4ba0b 100644
--- a/src/common/compat.h
+++ b/src/common/compat.h
@@ -581,11 +581,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..49353a8ee 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -4996,3 +4996,45 @@ 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 these
+   * parameters; they aren't too bad, and should have maximal period over the
+   * range 0..INT32_MAX. We don't want to use the platform rand() or random(),
+   * since some platforms have bad weak RNGs that only return 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..12283fcbb 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.
@@ -1755,11 +1764,18 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn,
   int cells_on_queue;
   int cells_per_conn;
   edge_connection_t *chosen_stream = NULL;
+  int max_to_package;
+
+  if (first_conn == NULL) {
+    /* Don't bother to try to do the rest of this if there are no connections
+     * to resume. */
+    return 0;
+  }
 
   /* How many cells do we have space for?  It will be the minimum of
    * the number needed to exhaust the package window, and the minimum
    * needed to fill the cell queue. */
-  int max_to_package = circ->package_window;
+  max_to_package = circ->package_window;
   if (CIRCUIT_IS_ORIGIN(circ)) {
     cells_on_queue = circ->n_chan_cells.n;
   } else {
@@ -1784,10 +1800,19 @@ 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. */
+       * among the first num_streams streams on first_conn.
+       *
+       * (Note that we iterate over every stream on the circuit, so that after
+       * we've considered the first stream, we've chosen it with P=1; and
+       * after we consider the second stream, we've switched to it with P=1/2
+       * and stayed with the first stream with P=1/2; and after we've
+       * considered the third stream, we've switched to it with P=1/3 and
+       * remained with one of the first two streams with P=(2/3), giving each
+       * one P=(1/2)(2/3) )=(1/3).) */
     }
   }
 
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);
diff --git a/src/test/test_util.c b/src/test/test_util.c
index bed33fac2..a66941b00 100644
--- a/src/test/test_util.c
+++ b/src/test/test_util.c
@@ -3242,6 +3242,34 @@ test_util_set_env_var_in_sl(void *ptr)
 }
 
 static void
+test_util_weak_random(void *arg)
+{
+  int i, j, n[16];
+  tor_weak_rng_t rng;
+  (void) arg;
+
+  tor_init_weak_random(&rng, (unsigned)time(NULL));
+
+  for (i = 1; i <= 256; ++i) {
+    for (j=0;j<100;++j) {
+      int r = tor_weak_random_range(&rng, i);
+      tt_int_op(0, <=, r);
+      tt_int_op(r, <, i);
+    }
+  }
+
+  memset(n,0,sizeof(n));
+  for (j=0;j<8192;++j) {
+    n[tor_weak_random_range(&rng, 16)]++;
+  }
+
+  for (i=0;i<16;++i)
+    tt_int_op(n[i], >, 0);
+ done:
+  ;
+}
+
+static void
 test_util_mathlog(void *arg)
 {
   double d;
@@ -3312,6 +3340,7 @@ struct testcase_t util_tests[] = {
   UTIL_TEST(read_file_eof_two_loops, 0),
   UTIL_TEST(read_file_eof_zero_bytes, 0),
   UTIL_TEST(mathlog, 0),
+  UTIL_TEST(weak_random, 0),
   END_OF_TESTCASES
 };