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.

4 files changed, 23 insertions, 3 deletions

diff --git a/src/or/cpuworker.c b/src/or/cpuworker.c
index b5740f091d..6b52f3b5d7 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 79b0f25778..aa601e5a4f 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 5d06fd93fd..cbb2aca10d 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 d8da9ea1bd..9e2d8af1e9 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);