Re: Proposal: Two hop paths from entry guards

[Kraktus <kraktus@xxxxxxxxxxxxxx>]

(Response to an old message on or-dev, pasted below)

Could not we accomplish the about same thing by using a standard,
three hop circuit, where the middleman is also and exit node?

Alice (who is an entry guard) -> entry node -> middleman node (who
also allows exits) -> exit node

The entry node would then not know if it was an entry or a middleman
node, since the next hop would allow exits, no?

This would have the same weaknesses as below, but if someone did
figure out you were playing this game, you would still have the
standard three-hop circuit.  Hence, it would be less risky for exit
nodes to try it, although it still would not work as well for them.
Also, the entry node might notice the middleman node was taking rather
long to respond.

Of course, if many people did this, it would put further strain on
exit nodes.  However, since it is only useful to people running Tor
nodes, perhaps it would not be too much strain.

------ Original Message -----
Title: Proposal: Two hop paths from entry guards
To: or-dev@xxxxxxxx
Subject: Proposal: Two hop paths from entry guards
From: "Michael Lieberman" <mathmike@xxxxxxx>
Date: Tue, 26 Jun 2007 10:45:15 -0700
Delivered-to: archiver@xxxxxxxx
Delivered-to: or-dev-outgoing@xxxxxxxx
Delivered-to: or-dev@xxxxxxxx
Delivery-date: Tue, 26 Jun 2007 13:45:23 -0400
Dkim-signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta;
h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:mime-version:content-type:x-google-sender-auth;
b=g43+Q+LNWxyC9U0XnpEoImKrOuKznOfydSjIXYnJWEU/ORTb64FjBX6TWDLfZ3DllnMczp+bJmXSgJKM/VdWLlYBGVlNJQdMwYLFwYlAhqs9FyL0e1Cll3Qn/2fQiN4+vFdzlTz3WamFksQL+pGybmF3dXk/tIe7lwDuqyLqkfg=
Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta;
h=received:message-id:date:from:sender:to:subject:mime-version:content-type:x-google-sender-auth;
b=QH9tpeHRmV7nCy6HSeAwg6EtqNU5Zt8cHLzoM7nyOQ6MTvLXVdB8f0RxL7YxbJZD3Cq2AIF4/GkCVTIS0qwBW9rEbLKs9IudoRWaIdndhj1qBhjFZbcJUoO0xNqGQwpcEgxZUy+mUMubjazrw5TjjG2zlmjHJGdhIRYa3zAcSg8=
Reply-to: or-dev@xxxxxxxxxxxxx
Sender: owner-or-dev@xxxxxxxxxxxxx
 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.