Mitigate a side-channel leak of which relays Tor chooses for a circuit

Tor's and OpenSSL's current design guarantee that there are other leaks,
but this one is likely to be more easily exploitable, and is easy to fix.

2 files changed, 30 insertions, 4 deletions

diff --git a/changes/pathsel-BUGGY-a b/changes/pathsel-BUGGY-a
new file mode 100644
index 0000000000..cad2af5c0d
--- /dev/null
+++ b/changes/pathsel-BUGGY-a
@@ -0,0 +1,12 @@
+  o Security fixes:
+
+    - Try to leak less information about what relays a client is
+      choosing to a side-channel attacker.  Previously, a Tor client
+      would stop iterating through the list of available relays as
+      soon as it had chosen one, thus leaking information about which
+      relays it picked for a circuit to a timing attack.  (Tor is
+      likely to still leak information about which relays it has
+      chosen for a circuit to other processes on the same computer,
+      through e.g. which cache lines it loads while building the
+      circuit.)
+
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index d21b40c57d..30c20bf6e6 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -1674,6 +1674,8 @@ smartlist_choose_by_bandwidth_weights(smartlist_t *sl,
   double *bandwidths;
   double tmp = 0;
   unsigned int i;
+  unsigned int i_chosen;
+  unsigned int i_has_been_chosen;
   int have_unknown = 0; /* true iff sl contains element not in consensus. */
 
   /* Can't choose exit and guard at same time */
@@ -1835,12 +1837,17 @@ smartlist_choose_by_bandwidth_weights(smartlist_t *sl,
               * from 1 below. See bug 1203 for details. */
 
   /* Last, count through sl until we get to the element we picked */
+  i_chosen = (unsigned)smartlist_len(sl);
+  i_has_been_chosen = 0;
   tmp = 0.0;
   for (i=0; i < (unsigned)smartlist_len(sl); i++) {
     tmp += bandwidths[i];
-    if (tmp >= rand_bw)
-      break;
+    if (tmp >= rand_bw && !i_has_been_chosen) {
+      i_chosen = i;
+      i_has_been_chosen = 1;
+    }
   }
+  i = i_chosen;
 
   if (i == (unsigned)smartlist_len(sl)) {
     /* This was once possible due to round-off error, but shouldn't be able
@@ -1877,6 +1884,8 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule,
                               int statuses)
 {
   unsigned int i;
+  unsigned int i_chosen;
+  unsigned int i_has_been_chosen;
   routerinfo_t *router;
   routerstatus_t *status=NULL;
   int32_t *bandwidths;
@@ -2092,6 +2101,8 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule,
 
   /* Last, count through sl until we get to the element we picked */
   tmp = 0;
+  i_chosen = (unsigned)smartlist_len(sl);
+  i_has_been_chosen = 0;
   for (i=0; i < (unsigned)smartlist_len(sl); i++) {
     is_exit = bitarray_is_set(exit_bits, i);
     is_guard = bitarray_is_set(guard_bits, i);
@@ -2106,9 +2117,12 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule,
     else
       tmp += bandwidths[i];
 
-    if (tmp >= rand_bw)
-      break;
+    if (tmp >= rand_bw && !i_has_been_chosen) {
+      i_chosen = i;
+      i_has_been_chosen = 1;
+    }
   }
+  i = i_chosen;
   if (i == (unsigned)smartlist_len(sl)) {
     /* This was once possible due to round-off error, but shouldn't be able
      * to occur any longer. */