proposals/116-two-hop-paths-from-guard.txt

   1 Filename: 116-two-hop-paths-from-guard.txt
   2 Title: Two hop paths from entry guards
   3 Author: Michael Lieberman
   4 Created: 26-Jun-2007
   5 Status: Dead
   6
   7 This proposal is related to (but different from) Mike Perry's proposal 115
   8 "Two Hop Paths."
   9
  10 Overview:
  11
  12 Volunteers who run entry guards should have the option of using only 2
  13 additional tor nodes when constructing their own tor circuits.
  14
  15 While the option of two hop paths should perhaps be extended to every client
  16 (as discussed in Mike Perry's thread), I believe the anonymity properties of
  17 two hop paths are particularly well-suited to client computers that are also
  18 serving as entry guards.
  19
  20 First I will describe the details of the strategy, as well as possible
  21 avenues of attack. Then I will list advantages and disadvantages. Then, I
  22 will discuss some possibly safer variations of the strategy, and finally
  23 some implementation issues.
  24
  25 Details:
  26
  27 Suppose Alice is an entry guard, and wants to construct a two hop circuit.
  28 Alice chooses a middle node at random (not using the entry guard strategy),
  29 and gains anonymity by having her traffic look just like traffic from
  30 someone else using her as an entry guard.
  31
  32 Can Alice's middle node figure out that she is initiator of the traffic? I
  33 can think of four possible approaches for distinguishing traffic from Alice
  34 with traffic through Alice:
  35
  36 1) Notice that communication from Alice comes too fast: Experimentation is
  37 needed to determine if traffic from Alice can be distinguished from traffic
  38 from a computer with a decent link to Alice.
  39
  40 2) Monitor Alice's network traffic to discover the lack of incoming packets
  41 at the appropriate times. If an adversary has this ability, then Alice
  42 already has problems in the current system, because the adversary can run a
  43 standard timing attack on Alice's traffic.
  44
  45 3) Notice that traffic from Alice is unique in some way such that if Alice
  46 was just one of 3 entry guards for this traffic, then the traffic should be
  47 coming from two other entry guards as well. An example of "unique traffic"
  48 could be always sending 117 packets every 3 minutes to an exit node that
  49 exits to port 4661. However, if such patterns existed with sufficient
  50 precision, then it seems to me that Tor already has a problem. (This "unique
  51 traffic" may not be a problem if clients often end up choosing a single
  52 entry guard because their other two are down. Does anyone know if this is
  53 the case?)
  54
  55 4) First, control the middle node *and* some other part of the traffic,
  56 using standard attacks on a two hop circuit without entry nodes (my recent
  57 paper on Browser-Based Attacks would work well for this
  58 http://petworkshop.org/2007/papers/PET2007_preproc_Browser_based.pdf). With
  59 control of the circuit, we can now cause "unique traffic" as in 3).
  60 Alternatively, if we know something about Alice independently, and we can
  61 see what websites are being visited, we might be able to guess that she is
  62 the kind of person that would visit those websites.
  63
  64 Anonymity Advantages:
  65
  66 -Alice never has the problem of choosing a malicious entry guard. In some
  67 sense, Alice acts as her own entry guard.
  68
  69 Anonymity Disadvantages:
  70
  71 -If Alice's traffic is identified as originating from herself (see above for
  72 how hard that might be), then she has the anonymity of a 2 hop circuit
  73 without entry guards.
  74
  75 Additional advantages:
  76
  77 -A discussion of the latency advantages of two hop circuits is going on in
  78 Mike Perry's thread already.
  79 -Also, we can advertise this change as "Run an entry guard and decrease your
  80 own Tor latency." This incentive has the potential to add nodes to the
  81 network, improving the network as a whole.
  82
  83 Safer variations:
  84
  85 To solve the "unique traffic" problem, Alice could use two hop paths only
  86 1/3 of the time, and choose 2 other entry guards for the other 2/3 of the
  87 time. All the advantages are now 1/3 as useful (possibly more, if the other
  88 2 entry guards are not always up).
  89
  90 To solve the problem that Alice's responses are too fast, Alice could delay
  91 her responses (ideally based on some real data of response time when Alice
  92 is used an entry guard). This loses most of the speed advantages of the two
  93 hop path, but if Alice is a fast entry guard, it doesn't lose everything. It
  94 also still has the (arguable) anonymity advantage that Alice doesn't have to
  95 worry about having a malicious entry guard.
  96
  97 Implementation details:
  98 For Alice to remain anonymous using this strategy, she has to actually be
  99 acting as an entry guard for other nodes. This means the two hop option can
 100 only be available to whatever high-performance threshold is currently set on
 101 entry guards. Alice may need to somehow check her own current status as an
 102 entry guard before choosing this two hop strategy.
 103
 104 Another thing to consider: suppose Alice is also an exit node. If the
 105 fraction of exit nodes in existence is too small, she may rarely or never be
 106 chosen as an entry guard. It would be sad if we offered an incentive to run
 107 an entry guard that didn't extend to exit nodes. I suppose clients of Exit
 108 nodes could pull the same trick, and bypass using Tor altogether (zero hop
 109 paths), though that has additional issues.*
 110
 111 Mike Lieberman
 112 MIT
 113
 114 *Why we shouldn't recommend Exit nodes pull the same trick:
 115 1) Exit nodes would suffer heavily from the problem of "unique traffic"
 116 mentioned above.
 117 2) It would give governments an incentive to confiscate exit nodes to see if
 118 they are pulling this trick.