[tor-dev] Guard nodes and network down events

[George Kadianakis]

Hello friends :)

This is a post to discuss how Tor should treat its entry guards when
its network goes down. This is part of ticket #12595 [0] which aims to
design better interfaces and data structures for entry guards.

This thread investigates what should happen when the network goes down
and Tor's connection to a guard fails. How should Tor recognize that
and connect back to that guard when the network goes up again?

I recently sent an email to tor-dev [1] which explains Tor's current
behavior and its problems. tl;dr there are edge cases [2] where Tor
will not detect the "network back up" event and will connect to low
priority guards instead of connecting to its primary guards.

The fundamental issue here is that Tor does not have a primitive that
detects whether the network is up or down, since any such primitive
stands out to a network attacker [3]. This means that when Tor fails
to connect to an entry guard, Tor can never be sure whether the guard
was actually down or whether the network is down, and that complicates
its algorithm significantly.

In #12595, I laid down a few different ways that Tor could improve its
current "network down" entry guard algorithm [4]. After thinking some
more, I've been leaning towards algorithm (a), which is:

  Everytime we manage to connect to a guard, if it's not the top
  guard in our list, mark all previous guards as retriable and try
  again from the top.

For me, this seems like the most complete way of ensuring that the
guards in the top of the list are always going to get a fair hearing
even if the network was down when they were first probed.

However, that algorithm is not without its problems. Here are some
notes:

- This algorithm suffers from an infinite loop.

  The naive version suffers from an obvious infinite loop if the first
  guards in our list are actually down. To protect against that, we
  will probably need to rewrite the algorithm to:

    Everytime we manage to connect to a guard, if it's not the top
    guard in our list, mark all previous guards as retriable and try
    again from the top: this time pick whichever guard we can connect
    to even if it's not the top one.

- This algorithm is not actually robust.

  If we wanted to design a truly robust algorithm, it would have to be
  robust even against adversarial "network down" events. That is, the
  algorithm would need to work well even if you imagine the network as
  an "on"/"off" switch that the adversary can toggle at will.

  Here is how that algorithm can fail against such an adversary:

  1) Tor starts up. Adversary switches network off.
  2) Tor starts going through guards and fails to connect to them.
  3) Adversary switches network on.
  4) Tor detects "network up" event, marks all guards as up and goes from the top.
  5) Adversary switches network off.
  6) Tor starts going through guards and fails to connect to them.
  7) Adversary switches network on, and Tor establishes a circuit to
     the guard that it was currently walking over.

  If the adversary is a LAN adversary, she learns the order of the
  guards in Tor's list, so she can basically choose whichever guard
  she wants.

  FWIW, whether such an adversary is realistic is up for debate.

- This algorithm is not very elegant.

- This algorithm might make guard fingerprinting worse.

  Imagine that the first 2 guards in your list are actually
  down. Everytime Tor detects a "network up" event, it will attempt to
  connect to those 2 dead guards before connecting to the third guard
  which is up.

. A LAN/WAN adversary will be able to see those failed connections and
  the third successful connection, which form a nice tight guard
  fingerprinting vector (similar to #10969).

And that's all folks.

I'm looking forward to some feedback on the proposed algorithms as
well as improvements and suggestions.

PS: I think that Tor was doing a trick with UDP to learn its public IP
    address or something. I need to read up on that trick, and see if
    it can be used to build a "network up" primitive.

[0]: https://trac.torproject.org/projects/tor/ticket/12595

[1]: https://lists.torproject.org/pipermail/tor-dev/2014-June/007042.html

[2]: https://trac.torproject.org/projects/tor/ticket/12450

[3]: http://stackoverflow.com/questions/3764291/checking-network-connection
     https://trac.torproject.org/projects/tor/ticket/12595#comment:6

[4]: https://trac.torproject.org/projects/tor/ticket/12595#comment:5