From 308f6dad20675c42b29862f4269ad1fbfb00dc9a Mon Sep 17 00:00:00 2001 From: Robert Ransom Date: Thu, 14 Jun 2012 17:15:54 +0000 Subject: 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. --- changes/pathsel-BUGGY-a | 12 ++++++++++++ src/or/routerlist.c | 22 ++++++++++++++++++---- 2 files changed, 30 insertions(+), 4 deletions(-) create mode 100644 changes/pathsel-BUGGY-a 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. */ -- cgit v1.2.3-54-g00ecf From d48cebc5e498b0ae673635f40fc57cdddab45d5b Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Fri, 3 Aug 2012 11:54:11 -0400 Subject: Try to clarify impact of bug 6537 I don't personally agree that this is likely to be easy to exploit, and some initial experimention I've done suggests that cache-miss times are just plain too fast to get useful info out of when they're mixed up with the rest of Tor's timing noise. Nevertheless, I'm leaving Robert's initial changelog entry in the git history so that he can be the voice of reason if I'm wrong. :) --- changes/pathsel-BUGGY-a | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) diff --git a/changes/pathsel-BUGGY-a b/changes/pathsel-BUGGY-a index cad2af5c0d..2e642c7953 100644 --- a/changes/pathsel-BUGGY-a +++ b/changes/pathsel-BUGGY-a @@ -3,10 +3,12 @@ - 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.) - + soon as it had chosen one, thus finishing a little earlier + when it picked a router earlier in the list. If an attacker + can recover this timing information (nontrivial but not + proven to be impossible), they could learn some coarse- + grained information about which relays a client was picking + (middle nodes in particular are likelier to be affected than + exits). The timing attack might be mitigated by other factors + (see bug #6537 for some discussion), but it's best not to + take chances. Fixes bug 6537; bugfix on 0.0.8rc1. -- cgit v1.2.3-54-g00ecf