Proposal: Two hop paths from entry guards

["Michael Lieberman" <mathmike@xxxxxxx>]

Title: Two hop paths from entry guards

This proposal is related to (but different from) Mike Perry's proposal "Two Hop Paths."  See 


http://archives.seul.org/or/dev/May-2007/msg00022.html

Overview: 

Volunteers who run entry guards should have the option of using only 2 additional tor nodes when constructing their own tor circuits.

While the option of two hop paths should perhaps be extended to every client (as discussed in Mike Perry's thread), I believe the anonymity properties of two hop paths are particularly well-suited to client computers that are also serving as entry guards.

First I will describe the details of the strategy, as well as possible avenues of attack. Then I will list advantages and disadvantages. Then, I will discuss some possibly safer variations of the strategy, and finally some implementation issues.

Details:

Suppose Alice is an entry guard, and wants to construct a two hop circuit. Alice chooses a middle node at random (not using the entry guard strategy), and gains anonymity by having her traffic look just like traffic from someone else using her as an entry guard.

Can Alice's middle node figure out that she is initiator of the traffic? I can think of four possible approaches for distinguishing traffic from Alice with traffic 

through Alice:

1) Notice that communication from Alice comes too fast: Experimentation is needed to determine if traffic from Alice can be distinguished from traffic from a computer with a decent link to Alice.

2) Monitor Alice's network traffic to discover the lack of incoming packets at the appropriate times. If an adversary has this ability, then Alice already has problems in the current system, because the adversary can run a standard timing attack on Alice's traffic.

3) Notice that traffic from Alice is unique in some way such that if Alice was just one of 3 entry guards for this traffic, then the traffic should be coming from two other entry guards as well. An example of "unique traffic" could be always sending 117 packets every 3 minutes to an exit node that exits to port 4661. However, if such patterns existed with sufficient precision, then it seems to me that Tor already has a problem. 
(This "unique traffic" may not be a problem if clients often end up choosing a single entry guard because their other two are down. Does anyone know if this is the case?)

4) First, control the middle node *and* some other part of the traffic, using standard attacks on a two hop circuit without entry nodes (my recent paper on Browser-Based Attacks would work well for this 
http://petworkshop.org/2007/papers/PET2007_preproc_Browser_based.pdf
). With control of the circuit, we can now cause "unique traffic" as in 3). Alternatively, if we know something about Alice independently, and we can see what websites are being visited, we might be able to guess that she is the kind of person that would visit those websites. 

Anonymity Advantages: 

-Alice never has the problem of choosing a malicious entry guard. In some sense, Alice acts as her own entry guard.

Anonymity Disadvantages:

-If Alice's traffic is identified as originating from herself (see above for how hard that might be), then she has the anonymity of a 2 hop circuit without entry guards.

Additional advantages:

-A discussion of the latency advantages of two hop circuits is going on in Mike Perry's thread already.
-Also, we can advertise this change as "Run an entry guard and decrease your own Tor latency." This incentive has the potential to add nodes to the network, improving the network as a whole.

Safer variations:

To solve the "unique traffic" problem, Alice could use two hop paths only 1/3 of the time, and choose 2 other entry guards for the other 2/3 of the time. All the advantages are now 1/3 as useful (possibly more, if the other 2 entry guards are not always up). 

To solve the problem that Alice's responses are too fast, Alice could delay her responses (ideally based on some real data of response time when Alice is used an entry guard). This loses most of the speed advantages of the two hop path, but if Alice is a fast entry guard, it doesn't lose everything. It also still has the (arguable) anonymity advantage that Alice doesn't have to worry about having a malicious entry guard.

Implementation details:
For Alice to remain anonymous using this strategy, she has to actually be acting as an entry guard for other nodes. This means the two hop option can only be available to whatever high-performance threshold is currently set on entry guards. Alice may need to somehow check her own current status as an entry guard before choosing this two hop strategy.

Another thing to consider: suppose Alice is also an exit node. If the fraction of exit nodes in existence is too small, she may rarely or never be chosen as an entry guard. It would be sad if we offered an incentive to run an entry guard that didn't extend to exit nodes. I suppose clients of Exit nodes could pull the same trick, and bypass using Tor altogether (zero hop paths), though that has additional issues.*

Mike Lieberman
MIT

*Why we shouldn't recommend Exit nodes pull the same trick:
1) Exit nodes would suffer heavily from the problem of "unique traffic" mentioned above.
2) It would give governments an incentive to confiscate exit nodes to see if they are pulling this trick.