commit 640a51684ce5a6cdae5c5f92cd2f932922380c00 Author: Nick Mathewson nickm@torproject.org Date: Thu Aug 9 12:37:40 2012 -0400
Remove remaining timing-dependency in choosing nodes by bandwidth
The old approach, because of its "tmp >= rand_bw && !i_has_been_chosen" check, would run through the second part of the loop slightly slower than the first part. Now, we remove i_has_been_chosen, and instead set rand_bw = UINT64_MAX, so that every instance of the loop will do exactly the same amount of work regardless of the initial value of rand_bw.
Fix for bug 6538. --- changes/bug6538 | 8 ++++++++ src/or/routerlist.c | 12 ++++-------- 2 files changed, 12 insertions(+), 8 deletions(-)
diff --git a/changes/bug6538 b/changes/bug6538 index 1e882eb..fc9e583 100644 --- a/changes/bug6538 +++ b/changes/bug6538 @@ -2,3 +2,11 @@ - Switch weighted node selection rule from using a list of doubles to using a list of int64_t. This should make the process slightly easier to debug and maintain. Needed for fix for bug 6538. + + o Security features: + - Switch to a completely time-invariant approach for picking nodes + weighted by bandwidth. Our old approach would run through the + part of the loop after it had made its choice slightly slower + than it ran through the part of the loop before it had made its + choice. Fix for bug 6538. + diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 382d457..75cb3f2 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -1710,7 +1710,6 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl, uint64_t tmp; 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 */ @@ -1881,13 +1880,12 @@ smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl,
/* 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; for (i=0; i < (unsigned)smartlist_len(sl); i++) { tmp += bandwidths[i]; - if (tmp >= rand_bw && !i_has_been_chosen) { + if (tmp >= rand_bw) { i_chosen = i; - i_has_been_chosen = 1; + rand_bw = UINT64_MAX; } } i = i_chosen; @@ -1926,7 +1924,6 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, { unsigned int i; unsigned int i_chosen; - unsigned int i_has_been_chosen; int32_t *bandwidths; int is_exit; int is_guard; @@ -2127,7 +2124,6 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, /* 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); @@ -2142,9 +2138,9 @@ smartlist_choose_node_by_bandwidth(smartlist_t *sl, else tmp += bandwidths[i];
- if (tmp >= rand_bw && !i_has_been_chosen) { + if (tmp >= rand_bw) { i_chosen = i; - i_has_been_chosen = 1; + rand_bw = UINT64_MAX; } } i = i_chosen;