[tor-bugs] #6538 [Tor Client]: Use bit-twiddling tricks to make choose-by-bandwith algorithm even more time-invariant

[Tor Bug Tracker & Wiki]

#6538: Use bit-twiddling tricks to make choose-by-bandwith algorithm even more
time-invariant
-------------------------+--------------------------------------------------
 Reporter:  nickm        |          Owner:                    
     Type:  enhancement  |         Status:  needs_review      
 Priority:  normal       |      Milestone:  Tor: 0.2.3.x-final
Component:  Tor Client   |        Version:                    
 Keywords:               |         Parent:                    
   Points:               |   Actualpoints:                    
-------------------------+--------------------------------------------------

Comment(by nickm):

 Replying to [comment:10 arma]:
 >
 > The slow mobile devices question is a good point though. Do you
 seriously think that setting a variable 1000 times vs 1100 times is going
 to be noticeable to even a local network attacker?

 So the offending code in Tor today is:
 {{{
   for (i=0; i < (unsigned)smartlist_len(sl); i++) {
     tmp += bandwidths[i];
     if (tmp >= rand_bw && !i_has_been_chosen) {
       i_chosen = i;
       i_has_been_chosen = 1;
     }
   }
 }}}

 Note that in the part of the loop before we choose the router, the tmp >=
 rand_bw part will be false and the !i_has_been_chosen part will never be
 executed. When we choose the router, both tests are executed and we run
 the conditional block.  After we choose the route, tmp >= rand_bw will be
 true and !i_has_been chosen will be executed and will turn out to be
 false.

 I wouldn't expect any cache misses to be different in these cases.  So
 what we need to worry about is branch mispredictions.  In the worst case,
 let's say that in the first half of the loop, we correctly predict the
 first test, and in the second part of the loop, we mispredict both tests
 every time (because our architecture sucks hard).  So, the biggest
 difference in timing will be on the order of N_ROUTERS *
 branch_misprediction_cost * 2.  Something like 3-10 cycles is a reasonable
 order of magnitude for branch_misprediction_cost on a modern CPU.  I don't
 know where you'll find an embedded device with less than 400 MHz running
 Tor these days, so let's say our minimum clock speed is 200 MHz.  Let's
 say there are 5000 routers.  So in the worst imaginable case, that's 0.25
 ms, which will definitely be detectable locally, and might be detectable
 remotely depending on assumptions, prevailing conditions, and the phase of
 the moon.

 Making some more favorable assumptions, and assuming no huge branch
 mispredictions, assuming that it's only one extra cycle to check
 !i_has_been_chosen, assuming that our clock speed is a nice hefty 1 GHz:
 that's still 5 microseconds, which should be detectable locally.

-- 
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/6538#comment:12>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online