Re: [tor-bugs] #12595 [Tor]: Think of better data structures for guard nodes

["Tor Bug Tracker & Wiki" <blackhole@xxxxxxxxxxxxxx>]

#12595: Think of better data structures for guard nodes
------------------------+--------------------------------
     Reporter:  asn     |      Owner:
         Type:  defect  |     Status:  new
     Priority:  normal  |  Milestone:  Tor: 0.2.6.x-final
    Component:  Tor     |    Version:
   Resolution:          |   Keywords:  tor-guard
Actual Points:          |  Parent ID:
       Points:          |
------------------------+--------------------------------

Comment (by asn):

 Another thing that the new data structures should fix is the #12450
 behavior. That is, the part of Tor that figures out that the net was
 disabled and just came back up, and hence we need to retry our previous
 guards.

 Currently, the logic is as follows:
 https://gitweb.torproject.org/tor.git/blob/d064773595f1d0bf1b76dd6f7439bff653a3c8ce:/src/or/entrynodes.c#l776

   If we just added a new entry guard to our list and we managed to connect
 to it, then we assume that the network just came back up: we enable the
 `can_retry` field of all previous guards and kill the current connection
 to the new guard. Then we retry guards from the beginning.

 The assumption here is that since we had to add a new entry guard to the
 list we have already exhausted all the already existing entry guards, and
 hence we had a ''network down'' scenario.

 This assumption is OK but not complete since it does not consider some
 edge cases

 As an example, it causes the #12450 bug, where the network comes back up
 before we exhaust all the already existing entry guards. Since we didn't
 have to add a new entry guard to the list, the ''network up'' event is not
 detected and we keep on using that entry guard we ended up with.

 The new data structures and methods should take this into account.

 ----

 There are various kludg!^Wways to fix this issue. Some ideas:

 a) Everytime we manage to connect to a guard, if it's not the first guard
 in our list, we mark all previous guards as retriable, and try from the
 top.
 b) Everytime we manage to connect to a guard, if we have previously failed
 to connect to other guards in this session, we mark '''all other guards'''
 as retriable and try from the top.
 c) Everytime we manage to connect to a guard, if we have previously failed
 to connect to a guard in this session, we mark '''those previously
 attempted''' guards as retriable and try from the top.

 All the above ideas will also need some way to stop them from infinite
 looping.

 ----

 From the above ideas, I can see some problems with (b) and (c) because its
 memory is restricted to a single session. Example: Network goes down, Tor
 tries some guards and marks them as unreachable. Tor gets shut down. Tor
 starts up again when the network is back up, manages to connect to a guard
 and stays with that guard (which is not the top one).

 (a) is a bit more bulletproof since it will always try to use the top
 guards, but it also has its problems. First of all, there needs to be a
 system to stop it from infinite looping, since if your first guard is
 actually down, we shouldn't keep on retrying it.

 Assuming that there is some sort of infinite loop protection, you can
 imagine the following (unlikely) race condition problem. Tor starts up,
 network down, Tor tries various guards. Network goes up and we connect to
 a guard. We notice that network goes up, and we mark all previous guards
 as retriable. Before starting from the top, network goes down again, Tor
 finds the first few guards unreachable, and then network goes up again and
 we connect to the entry guard we were examining at that point (which is
 not the top one).

 Furthermore, it's worth having in mind that such probing behaviors can
 also act as a guard fingerprint (similar to #10969). For example, let's
 assume the (a) behavior and assume that the first two guards of your entry
 guard list are actually down (quite common). Everytime you mark your
 guards as retriable and go from the top, you will also probe those two
 entry guards that are down. Your ISP will be able to see both of those
 probes plus the connection to the third guard that actually succeeds.
 These three connections should be enough to form a fingerprint.

 Guess what, more research is needed.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/12595#comment:5>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online
_______________________________________________
tor-bugs mailing list
tor-bugs@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs