Slow Guard Discovery of Hidden Services and Clients
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:
- Multiple layers of guard nodes.
- 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.
- 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 (moved), or we could define lifetime based on expected circuit use and application-provided linkability hints (such as #5752 (moved)).
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.
Activity
changed milestone to %Tor: unspecified
Trac:
Description: 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 fingerprinting and destroying HSdir lookup circuits.
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:
- Multiple layers of guard nodes.
- 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.
- 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 learning 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 (moved), or we could define lifetime based on expected circuit use and application-provided linkability hints (such as #5752 (moved)).
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.
to
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:
- Multiple layers of guard nodes.
- 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.
- 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 (moved), or we could define lifetime based on expected circuit use and application-provided linkability hints (such as #5752 (moved)).
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.
Cc: rpw, nickm, arma, sysrqb, asn to rpw, nickm, arma, sysrqb, asn, andrea-
See also #9072 (moved), 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.
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 (moved) vs. providing reliable service for the clients in the face of possibly unreliable nodes.
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
CREATEcell (see also #3443 (moved)); a second circuit built along the same path could easily have an acceptable build time).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 (moved) 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.)
-
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 (moved) 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 (moved)) 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.
-
Skruffy pointed out that we want to fix #9093 (moved) 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.
Trac:
Parent: N/A to #5456 (moved) 
Trac:
Username: dave2008
Cc: rpw, nickm, arma, sysrqb, asn, andrea to rpw, nickm, arma, sysrqb, asn, andrea, dave2008713@gmail.comTrac:
Cc: rpw, nickm, arma, sysrqb, asn, andrea, dave2008713@gmail.com to rpw, nickm, arma, sysrqb, asn, andrea, dave2008713@gmail.com, special-
Also I updated asn's proposal. My version lives here: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/247-hs-guard-discovery.txt?h=guard_discovery_dev.
Last I heard, he likes the new version overall, but was considering some more tweaks.
Trac:
Keywords: SponsorU deleted, SponsorU 028-triage added 
Also see #15540 (moved)
Replying to cypherpunks:
Hi! Any progress on this one?
This is Prop247 https://gitweb.torproject.org/torspec.git/tree/proposals/247-hs-guard-discovery.txt
Can the adoption of HS v2 solve this issue?
No.
mentioned in issue #9002 (moved)
