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