[tor-dev] [RFC] Proposal draft: The move to a single guard node

George Kadianakis desnacked at riseup.net
Wed Mar 26 16:36:31 UTC 2014


I promised Nick I would have something for him by today's little-t-tor
meeting.

Here is a draft of the guard node security proposal.
Definitely needs more work:

Filename: xxx-single-guard-node.txt
Title: The move to a single guard node
Author: George Kadianakis
Created: 2014-03-22
Status: Draft and potentially a bad idea

0. Introduction

   It has been suggested that reducing the number of guard nodes of
   each user and increasing the guard node rotation period will make
   Tor more resistant against certain attacks [0].

   For example, an attacker who sets up guard nodes and hopes for a
   client to eventually choose them as their guard will have much less
   probability of succeeding in the long term.

   Currently, every client picks 3 guard nodes and keeps them for 2 to
   3 months (since 0.2.4.12-alpha) before rotating them. In this
   document, we propose the move to a single guard per client and an
   increase of the rotation period to 9 to 10 months.

1. Proposed changes

1.1. Switch to one guard per client

   When this proposal becomes effective, clients will switch to using
   a single guard node.

   That is, in its first startup, Tor picks one guard and stores its
   identity persistently to disk. Tor uses that guard node as the
   first hop of its circuits from thereafter.

   If that Guard node ever becomes unusable, rather than replacing it,
   Tor picks a new guard and adds it to the end of the list. When
   choosing the first hop of a circuit, Tor tries all guard nodes from
   the top of the list sequentially till it finds a usable guard node.

   A Guard node is considered unusable according to section "5. Guard
   nodes" in path-spec.txt. The rest of the rules from that section
   apply here too. XXX which rules specifically?

   XXX Do we need to specify how already existing clients migrate?

1.1.1. Alternative behavior to section 1.1

   Here is an alternative behavior than the one specified in the
   previous section. It's unclear which one is better.

   Instead of picking a new guard when the old guard becomes unusable,
   we pick a number of guards in the beginning but only use the top
   usable guard each time. When our guard becomes unusable, we move to
   the guard below it in the list.

   This behavior _might_ make some attacks harder; for example, an
   attacker who shoots down your guard in the hope that you will pick
   his guard next, is now forced to have evil guards in the network at
   the time you first picked your guards.

   However, this behavior might also influence performance, since a
   guard that was fast enough 7 months ago, might not be this fast
   today. Should we reevaluate our opinion based on the last
   consensus, when we have to pick a new guard? Also, a guard that was
   up 7 months ago might be down today, so we might end up sampling
   from the current network anyway.

1.2. Increase guard rotation period

   When this proposal becomes effective, Tor clients will set the
   lifetime of each guard to a random time between 9 to 10 months.

   If Tor tries to use a guard whose age is over its lifetime value,
   the guard gets discarded (also from persistent storage) and a new
   one is picked in its place.

   XXX We didn't do any analysis on extending the rotation period.
       For example, we don't even know the average age of guards, and
       whether all guards stay around for less than 9 months anyway.
       Maybe we should do some analysis before proceeding?

   XXX The guard lifetime should be controlled using the
       (undocumented?) GuardLifetime consensus option, right?

1.2.1. Alternative behavior to section 1.2

   Here is an alternative behavior than the one specified in the
   previous section. It's unclear which one is better.

   Similar to section 1.2, but instead of rotating to completely new
   guard nodes after 9 months, we pick a few extra guard nodes in the
   beginning, and after 9 months we delete the already used guard
   nodes and use the one after them.

   This has approximately the same tradeoffs as section 1.1.1.

   Also, should we check the age of all of our guards periodically, or
   only check them when we try to use them?

1.3. Age of guard as a factor on guard probabilities

   By increasing the guard rotation period we also increase the lack
   of clients for young guards since clients will rotate guards even
   more infrequently now (see 'Phase three' of [1]).

   We can try to mitigate this phenomenon by giving higher priority to
   young guards to be picked as guards:

   To do so, everytime an authority needs to vote for a guard, it
   reads a set of consensus documents spanning the past NNN months, and
   calculates the age of the guard; that is, in how many consensuses
   its public key has been included in the past.

   The authorities include the age of each guard by appending
   '[SP "Age=" INT]' in the guard's "w" line.

   When a client picks a guard, it applies the age of each guard as a
   weight on its guard probability. XXX unspecified how

   XXX How much should the age of a guard influence its probability?
       Should we say that a guard that just appeared should have 10%
       more chance of being selected as a guard node than the oldest
       guard in town?

   XXX Should the authorities include the age itself, or just the
       weight that clients should apply to the probability?

   XXX Is this risky? Maybe we shouldn't give too much priority to new
       guards, otherwise an adversary can start up a few new relays
       every month, enjoy maximum priority when they get the guard
       flag, leave them running for a bit till the next batch gets the
       guard flag and then trash them.

1.4. Raise the bandwidth threshold for being a guard

   From dir-spec.txt:
      "Guard" -- A router is a possible 'Guard' if its Weighted Fractional
       Uptime is at least the median for "familiar" active routers, and if
       its bandwidth is at least median or at least 250KB/s.

   When this proposal becomes effective, authorities should change the
   bandwidth threshold for being a guard node to 2000KB/s instead of
   250KB/s.

   Implications of raising the bandwidth threshold are discussed in
   section 2.3.

   XXX Is this insane? It's an 8-fold increase.

2. Discussion

2.1. Guard node set fingerprinting

   With the old behavior of three guard nodes per user, it was
   extremely unlikely for two users to have the same guard node
   set. Hence the set of guard nodes acted as a fingerprint to each
   user.

   When this proposal becomes effective, each user will have one guard
   node. We believe that this slightly reduces the effectiveness of
   this fingerprint since users who pick a popular guard node will now
   blend in with thousands of other users. However, clients who pick a
   slow guard will still have a small anonymity set [2].

   All in all, this proposal slightly improves the situation of guard
   node fingerprinting, but does not solve it. See the next section
   for a suggested scheme that would further fix the guard node set
   fingerprinting problem

2.1.1. Potential fingerprinting solution: Guard buckets

   One of the suggested alternatives that moves us closer to solving
   the guard node fingerprinting problem, would be to split the list
   of N guard nodes into buckets of K guards, and have each client
   pick a bucket [3].

   This reduces the fingerprint from N-choose-k to N/k guard set
   choices; it also allows users to have multiple guard nodes which
   provides reliability and performance.

   Unfortunately, the implementation of this idea is not as easy and
   its anonymity effects are not well understood so we had to reject
   this alternative for now.

2.2. What about 'multipath' schemes like Conflux?

   By switching to one guard, we rule out the deployment of
   'multipath' systems like Conflux [4] which build multiple circuits
   through the Tor network and attempt to detect and use the most
   efficient circuits.

   On the other hand, the 'Guard buckets' idea outlined in section
   2.1.1 works well with Conflux-type schemes so it's still worth
   considering.

2.3. Implications of raising the bandwidth threshold for guards

   By raising the bandwidth threshold for being a guard we directly
   affect the performance and anonymity of Tor clients. We performed a
   brief analysis of the implications of switching to one guard and
   the results imply that the changes are not tragic [2].

   Specifically, it seems that the performance of about half of the
   clients will degrade slightly, but the performance of the other
   half will remain the same or even improve.

   Also, it seems that the powerful guard nodes of the Tor network
   have enough total bandwidth capacity to handle client traffic even
   if some slow guard nodes get discarded.

   On the anonymity side, by increasing the bandwidth threshold to
   2MB/s we half our guard nodes; we discard 1000 out of 2000
   guards. Even if this seems like a substantial diversity loss, it
   seems that the 1000 discarded guard nodes had a very small chance
   of being selected in the first place (7% chance of any of the being
   selected).

   However, it's worth noting that the performed analysis was quite
   brief and the implications of this proposal are complex, so we
   should be prepared for surprises.

2.4. Should we stop building circuits after a number of guard failures?

   Inspired by academic papers like the Sniper attack [5], a powerful
   attacker can choose to shut down guard nodes till a client is
   forced to pick an attacker controlled guard node. Similarly, a
   local network attacker can kill all connections towards all guards
   except the ones she controls.

   This is a very powerful attack that is hard to defend against. A
   naive way of defending against it would be for Tor to refuse to
   build any more circuits after a number of guard node failures have
   been experienced.

   Unfortunately, we believe that this is not a sufficiently strong
   countermeasure since puzzled users will not comprehend the
   confusing warning message about guard node failures and they will
   instead just uninstall and reinstall TBB to fix the issue.

2.5. What this proposal does not propose

   Finally, this proposal does not aim to solve all the problems with
   guard nodes. This proposal only tries to solve some of the problems
   whose solution is analyzed sufficiently and seems harmless enough
   to us.

   For example, this proposal does not try to solve:
   - Guard enumeration attacks. We need guard layers or virtual
     circuits for this [6].
   - The guard node set fingerprinting problem [7]
   - The fact that each isolation profile or virtual identity should
     have its own guards.

XXX It would also be nice to have some way to easily revert back to 3
    guards if we later decide that a single guard was a very stupid
    idea.

References:

[0]: https://blog.torproject.org/blog/improving-tors-anonymity-changing-guard-parameters
     http://freehaven.net/anonbib/#wpes12-cogs

[1]: https://blog.torproject.org/blog/lifecycle-of-a-new-relay

[2]: https://lists.torproject.org/pipermail/tor-dev/2014-March/006458.html

[3]: https://trac.torproject.org/projects/tor/ticket/9273#comment:4

[4]: http://freehaven.net/anonbib/#pets13-splitting

[5]: https://blog.torproject.org/blog/new-tor-denial-service-attacks-and-defenses

[6]: https://trac.torproject.org/projects/tor/ticket/9001

[7]: https://trac.torproject.org/projects/tor/ticket/10969


More information about the tor-dev mailing list