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:

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 legacy/trac#8240 (moved), or we could define lifetime based on expected circuit use and application-provided linkability hints (such as legacy/trac#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.