[tor-dev] [Discussion] 5 ^H 3 hops rendezvous circuit design

[Paul Syverson]

On Wed, Feb 12, 2014 at 05:43:10PM -0500, Zack Weinberg wrote:
> On 02/11/2014 11:53 PM, Paul Syverson wrote:
> > The biggest concern is that no matter how you handle the commitment
> > and the size of the flexible set, you make it fairly easy for a HS
> > simply following this protocol precisely and with just the resource of
> > a handful of other nodes (n) in the network to identify the client
> > guard with certainty each time. (If he owns less than n, it becomes a
> > likelihood rather than a certainty each time. Alternatively if he owns
> > a few ASes or IXPs he could accomplish similar results with a judicious
> > choice of the network location of all n.) Given the push
> > elsewhere to use single guards for long periods, this makes guard
> > nodes all the more likely to face subpoena or other forms of attack
> > since the argument that this is a successful strategy to locate
> > clients of interest is greatly strengthened. Since the HS can choose
> > two hops that it does not object to, the client should be similarly
> > protected, i.e., four relays in the circuit overall.
> > 
> > The other big concern is that this looks like there are many places
> > to DoS or resource deplete the hidden service. Earlier designs kept
> > per introduction connection state for the HS to a minimum. There may
> > be ways to reduce that, but it is an important consideration.
> 
> So I have to say that I'm increasingly skeptical about the value of
> guards in general, and in this specific case - where both endpoints are
> emitting nothing but Tor protocol - I'm not convinced guards add
> anything at all, because *even if* both sides happen to pick malicious
> entry points that are controlled by the same adversary, the traffic will
> be indistinguishable from middle-relay traffic!  ... Except, I suppose,
> by traffic correlation to recover the flow and realize that the
> malicious relays are in positions 1 and 3, which in turn means each is
> talking directly to an endpoint.  And then they can do cross-flow
> correlation and figure out which end is the hidden service.  However,
> this kind of long-term correlation attack is *easier* for an adversary
> that controls enough stable nodes that it has a reasonable chance of
> getting picked as a guard by at least one party.  See above skepticism.

Asymptotically guards buy you nothing.  But it's not a long-term
attack that motivated guards. Lasse Overlier and I showed in our 2006
paper "Locating Hidden Servers" that prior to guards, someone owning a
single relay on the live Tor network of the day (c. 250 relays) could
find a hidden server in a matter of minutes. We were focused on what
could be done with a single relay so could only attack HS circuits. But
we noted that the same effect would apply to all Tor circuits if the
attacker had two or more relays. The next year Bauer et al. in
"Low-Resource Routing Attacks Against Tor" showed that specifically
(although in simulation rather than on the live Tor network as we
showed).

In our recent CCS paper we showed that guard compromise for reasonable
sized adversary was more on the order of several months than several
minutes. So quite the win.  The time to circuit compromise for typical
usage behaviors once the adversary has a guard is fairly quick. 

My point above was primarily about how a hostile hidden service could
easily learn the guard of the client by simply following the suggested
protocol, and then apply more directed resources on the guard for
circuits of interest to later identify and watch the client and all or
most of his behavior. Without guards, the client is just quickly exposed
directly. Much worse.

> 
> That said, these are both really good points, and together, may kill the
> whole concept. :-(  I wonder if we can formalize the problem enough to
> prove one way or another whether you really must have at least four hops?
> 

I expect that experimental results will be more compelling than
anything you can prove in this case. I also think that especially for
sensitive users (subject to targeted attacks rather than trawling) the
guards need to be chosen in a trust-aware way, as Lasse and I
suggested and as we have been exploring in more recent papers. Now
once you throw bridges into this mix...

aloha,
Paul