Opened 22 months ago

Last modified 9 days ago

#9001 assigned defect

Slow Guard Discovery of Hidden Services and Clients

Reported by: mikeperry Owned by:
Priority: major Milestone: Tor: 0.2.7.x-final
Component: Tor Version:
Keywords: tor-hs path-bias needs-proposal Cc: rpw, nickm, arma, sysrqb, asn, andrea, dave2008713@…, special
Actual Points: Parent ID: #5456
Points:

Description (last modified by mikeperry)

In http://www.ieee-security.org/TC/SP2013/papers/4977a080.pdf, one of the attacks described is a method for locating the Guard nodes of a hidden service within about an hour.

It also seems possible to locate the Guard nodes of persistent, automated clients in a similar timeframe by similarly repeatedly destroying HSdir lookup circuits for your target hidden service.

These attacks are possible to execute on such rapid timescales because *each* endpoint in hidden service communications can destroy the current circuit, and force the other party to create a new one using a new middle node.

There are at least three ways to slow this attack:

  1. Multiple layers of guard nodes.
  2. Create a "Virtual Circuit" abstraction layer that picks your hops for a given purpose, and tries to re-use those hops even after certain failure conditions.
  3. Change the Tor Protocol to prevent DESTROY cells and other mechanisms of circuit destruction from destroying the counter-party's endpoint, and create mechanisms for multiple clients to share a single HS rend circuit (such as I2Ps 'garlic routing' concept).

Nick and I are tentatively leaning towards the "Virtual Circuit" approach. Such a layer would cleanly decouple path selection from circuit use, and allow us to do things like keep the same three hops for rend and intro circuits for N days, regardless of transient circuit failures or DESTROY cells.

This would considerably slow the attack, and also make all sorts of anonymity metrics and analysis easier to do. For example: We can choose N intelligently such that we would expect the runtime of the attack to be a function of our guard lifetime from #8240, or we could define lifetime based on expected circuit use and application-provided linkability hints (such as #5752).

We can also use the layer to improve the path bias accounting to only count failure if you are forced to choose a new path, rather than simply make a new circuit.

Child Tickets

TicketSummaryOwner
#9002Clients should discard v2 HS descriptors with more than 10 intro pointsmikeperry
#9241Abstract and decouple path selection from circuit construction

Change History (15)

comment:1 Changed 22 months ago by mikeperry

  • Cc andrea added
  • Description modified (diff)

comment:2 Changed 22 months ago by mikeperry

See also #9072, which is another example of where an endpoint (in this case a malicious website) can manipulate your circuits.

I think this rules out approach number 3 from the summary (because there are probably lots of these types of bugs), and hints strongly in favor of making sure that if you're trying to use a path for a given reason (SOCKS u+p isolation, etc), you keep trying to use that path even if there are failure conditions.

comment:3 Changed 22 months ago by andrea

+1 virtual circuits; that also gives a chance to make path selection more cleanly abstracted in general, which will be a win when we have to deal with things like IPv6-only relays that make the topology no longer a totally connected graph and change path selection anyway.

comment:4 follow-up: Changed 22 months ago by andrea

Hmm - virtual circuits still sound like an interesting idea to me, but how do we tell the difference between failures where it's sensible to retry the same path vs. ones where retrying will always fail, like if one of the nodes in the path goes offline and we can't know that, other than from the failures of the circuits, until the authorities figure it out and it drops out of the consensus? Seems like this involves a sensitive tradeoff between avoiding attacks like in #9072 vs. providing reliable service for the clients in the face of possibly unreliable nodes.

comment:5 in reply to: ↑ 4 Changed 22 months ago by rransom

Replying to andrea:

Hmm - virtual circuits still sound like an interesting idea to me, but how do we tell the difference between failures where it's sensible to retry the same path vs. ones where retrying will always fail, like if one of the nodes in the path goes offline and we can't know that, other than from the failures of the circuits, until the authorities figure it out and it drops out of the consensus?

It's not just a matter of relays failing; links can fail too, either permanently (e.g. due to bozos running relays/bridges on boxes with hostile firewalls), semi-transiently (e.g. due to a relay hitting an OS-imposed limit on the number of TCP sockets), or transiently (e.g. due to adaptive CBT refusing to use a circuit because one of the relays had to open a new TLS connection before it could pass on the CREATE cell (see also #3443); a second circuit built along the same path could easily have an acceptable build time).

comment:6 follow-up: Changed 22 months ago by rransom

The only solution is to add a second layer of guards (‘identity guards’?), dependent on the client's ‘identity’ (as determined by the same things that control stream isolation).

This fix has some prerequisites:

  • Tor relays must use a UDP-based link protocol exclusively, for multiple security reasons. (Some entry nodes might allow their clients to connect using other link protocols.)
  • Clients must be able to choose a set of identity guards deterministically from a non-uniform (e.g. load-balanced) distribution according to a seed (#2653 gives one approach).
  • Each client application must be associated with one or more persistent identities. Otherwise, using identity guards only adds a moderate delay in finding a client's entry guards.
  • In order to avoid linking a client's identities, Tor clients must not allow any information about the Tor network or destination servers obtained through one identity to affect any behaviour of its other identities. (This requires that adaptive CBT and the path-bias detector be removed, and that many client-side caches be isolated to a single identity.)

comment:7 in reply to: ↑ 6 Changed 22 months ago by mikeperry

Replying to rransom:

The only solution is to add a second layer of guards (‘identity guards’?), dependent on the client's ‘identity’ (as determined by the same things that control stream isolation).

I recognize that link failure might be one way to attack a virtual circuit layer, but I don't believe it makes a secondary layer of guards the only solution, and I don't believe that a well designed virtual circuit layer would suffer as bad as you say under the timeout issues either.

This fix has some prerequisites:

  • Tor relays must use a UDP-based link protocol exclusively, for multiple security reasons. (Some entry nodes might allow their clients to connect using other link protocols.)
  • Clients must be able to choose a set of identity guards deterministically from a non-uniform (e.g. load-balanced) distribution according to a seed (#2653 gives one approach).
  • Each client application must be associated with one or more persistent identities. Otherwise, using identity guards only adds a moderate delay in finding a client's entry guards.

I think what you allude to here in this third prerequisite point is exactly why virtual circuits are better. My plan is to use virtual circuits plus strong stream/identity isolation (#5752) to cause you to try to use the same 3 hops for the same isolation, and to retry once you are successful. Before you're successful, it doesn't matter so much against this attack (because the other endpoint is not yet aware of your connection attempt).

The most important thing is making it simple to reason about, and virtual circuits are way easier to reason about than multiple layers of guard nodes, because we've been pretending Torcircuits are more robust/permanent than they are in all of the existing Tor analysis to date. A second layer of guards changes the entire analysis of Tor.

  • In order to avoid linking a client's identities, Tor clients must not allow any information about the Tor network or destination servers obtained through one identity to affect any behaviour of its other identities. (This requires that adaptive CBT and the path-bias detector be removed, and that many client-side caches be isolated to a single identity.)

I think once we get to this point, we've already realized that there are a lot of hidden complexities and routing behavior changes we'll need to support 2 layers of guards as opposed to virtual circuits.

comment:8 Changed 21 months ago by mikeperry

  • Parent ID set to #5456

Skruffy pointed out that we want to fix #9093 along the same timeframe as we deploy virtual circuits, otherwise it may be possible to remotely overload relays to probe for the fact that they are in use by a particular client (by observing the repeated disconnect/reconnect patterns of the target during the circuit-pruning OOM step).

At least I think that's what he was talking about.

comment:9 Changed 14 months ago by dave2008

  • Cc dave2008713@… added

comment:10 Changed 13 months ago by asn

Discussing this with Linus today, we figured out that hidden services with authentication will not launch circuits to rendezvous points if the client hasn't authenticated herself first. This might be a sufficient temporary workaround for some hidden services.

comment:11 Changed 13 months ago by nickm

  • Milestone changed from Tor: 0.2.5.x-final to Tor: 0.2.6.x-final

comment:12 Changed 9 months ago by nickm

  • Milestone changed from Tor: 0.2.6.x-final to Tor: 0.2.???

Virtual Circuits is a neat idea that will require a proposal. I'm kicking this into 0.2.??? until a proposal can be written and some serious analysis can be done.

comment:13 Changed 9 months ago by special

  • Cc special added

comment:14 Changed 2 weeks ago by nickm

  • Milestone changed from Tor: 0.2.??? to Tor: 0.2.7.x-final

These may be worth looking at for 0.2.7.

comment:15 Changed 9 days ago by nickm

  • Status changed from new to assigned
Note: See TracTickets for help on using tickets.