[tor-bugs] #9072 [Tor]: #9063 enables Guard discovery in about an hour by websites

[Tor Bug Tracker & Wiki]

#9072: #9063 enables Guard discovery in about an hour by websites
----------------------+-----------------------------------------------------
 Reporter:  arma      |          Owner:                     
     Type:  defect    |         Status:  needs_review       
 Priority:  critical  |      Milestone:  Tor: 0.2.3.x-final 
Component:  Tor       |        Version:  Tor: 0.2.4.13-alpha
 Keywords:            |         Parent:                     
   Points:            |   Actualpoints:                     
----------------------+-----------------------------------------------------

Comment(by nickm):

 Replying to [comment:16 robgjansen]:
 > Is there any reason not to simplify this down to the circuit level only?
 Anything based on connections is easily subverted by a sybil attack. And
 you can't consider the time-independent queue length alone because of the
 sybil attack.

 What you say seems plausible.  Though it might not be too bad to do a
 time-independent queue length as "good enough for now" in 0.2.4 and maybe
 0.2.3, then work on the better thing in 0.2.5, targeting a possible
 backport to 0.2.4 if the better thing turns out to be not too hard.  After
 all, if the #9063 solution seemed "good enough as a temporary measure"
 (barring this issue) then surely a queue-length-based solution is not
 worse.

 I think this here (algorithm 1 in 0.2.3 and 0.2.4; work on better stuff
 for 0.2.5 for a possible backport) is my current preferred approach,
 assuming there aren't flaws in it beyond what I know.  Finding the
 exactly-right approach for 0.2.5 seems like it might take a bunch of
 discussion and analysis.

 > The goal is to drive up the cost of the attack while making sure you are
 not killing an honest client's circuit. If you consider a function of the
 queue length and the waiting time of the longest waiting cell for each
 circuit, then a malicious client will have to read cells at a rate at
 least as fast as the slowest honest client *on every sybil* in order to
 cause the relay to target the honest client's circuit. It can be shown
 that the longer the attacker's queue becomes, the faster it must read from
 it to avoid selection because it needs to keep the waiting times of the
 cells in the malicious circuits lower than those of all honest circuits.

 You don't want a function of the longest waiting cell for each circuit, I
 think: a you want a function of the expected time to drain the queue.[*]
 That's why I was looking at connection flush rates -- the speed at which
 the connection is draining, and the lengths of the other circuit queues on
 the connection, determine how long it will take to drain the queue.


 [*] Why look at the expected drain time and not age of the longest waiting
 cell?  Imagine a slow connection where a bunch of legit circuits have had
 modestly long queues for a while, and a new connection has gotten a really
 egregious queue really quickly.  The ones that have been around longer
 seem like they could be the ones to get killed, which isn't so great.

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