How to expire/create circuits?

[Roger Dingledine <arma@mit.edu>]

Since tor uses tcp and has only a few tcp connections, issues come up
when clients are behind a firewall and the firewall silently times out
a masqueraded connection, or when the client is a laptop and the laptop
moves to a new network.

When we had one request per onion, it was simple -- circuits would become
empty and go away when their request ends, and onion proxies expired
tcp connections to onion routers when they have no active circuits and
are >10 mins idle. Circuits that were still in use but 10 minutes idle
(eg from an idle ssh connection) got a padding cell for keepalive. That
way totally idle onion proxies wouldn't take up any resources at all
from the onion routers.

But now circuits live forever and get reused. So it's hard to tell when
they should expire.

The first problem is usability: when I move my laptop to a new network,
my first web or ssh request causes the old connection to notice that
it's failed (and the circuit gets turn down along with the connection),
and then the next request works (because it generates a new circuit). If
I still lived behind an overzealous firewall, I would find that whenever
10 minutes pass without a web request, my next request fails. (We could
solve this issue by having the OP retry failed connections once or twice;
perhaps we should do that anyway.)

The second problem is anonymity: we don't want all requests forever to
go over the same circuit. If I do some stuff today and then more stuff
tomorrow, it would be nice if the sessions weren't linked. Perhaps even,
if I do some stuff at hotmail and then immediately after do some stuff
at google, I'd like them not to be linked.

Option one (very high load, very high anonymity):

Each new client request gets its own onion, with path chosen randomly.
This requires a lot of new onions, and probably significantly limits
the number of users we can handle with a given number of onion routers.
On the other hand, maybe the number of users we'll have won't make it
an issue. ;)

Option two (high load, mid anonymity): 

Clients make a new circuit for every new hostname. If there's already
a circuit for this hostname, but the circuit is more than n minutes old
(say n=5), then create a new one and use that. If there ever exist more
than one circuit for a given hostname, expire all the older ones which
are empty (have no topics currently active).

This seems to be building quite a few onions still -- one for every domain
the client goes to. It also is a significant drop in anonymity compared
to option one: obvious attacks include linking sessions between sites (eg
because they pull pages from one another), and linking sessions across
time (eg because you're pulling down lots of webpages from bob.com over
one session, and then you carry on doing it from a second session).

Option three (mid-high load, mid anonymity):

The client creates a new circuit every n minutes. New topics attach to
the newest circuit. If there ever exist old circuits that are empty,
expire them.

This has clients periodically creating circuits round the clock, even
when the user is on vacation for the weekend.

Option four (mid load, mid anonymity):

Like option three, but only create a new circuit if the newest circuit is
dirty (that is, a topic has been started in the past up to n minutes).
A circuit is clean until it gets used, as which point it's marked dirty
and no longer attached to after at most n minutes. To prevent firewalls
from eating clean but unused circuits, we'd have to send a padding cell
down them every 10 minutes or so.

This option is appealing because we can entirely separate the building
of onions from topics. So we could try more esoteric circuit-building
approaches, like synchronous circuit-building or removing/adding hops
one at a time from circuits, without changing much else.

For options three and four, it's possible to end up with no circuits,
if the new circuit dies before n minutes have passed. If a circuit dies
early we should act as though n just expired. (We'll need a safeguard
so we don't get into a frenzied loop of new onions when the network
goes away; and a plan for how to retry topics a few times at the OP,
coordinated with retrying the circuit. Suggestions?)

To keep from having to reform tcp connections often, we should reuse
the first hop in the circuit when creating the next circuit.

Option five (low load, high anonymity):

The onion proxy opens an onion. It sends a padding cell every 10
minutes. If the circuit breaks, it opens another. The user has a special
mechanism for signaling the onion proxy to build a new circuit. Or maybe
a rulefile that dictates when a new circuit should be made. Not sure
how to do such a signaling mechanism, and a rulefile is probably just
a big can of worms. But it doesn't sound like it would use many onions,
and *if* the user knew what the heck was going on, he could protect his
privacy quite well.

Option six (low load, low anonymity):

The onion proxy opens an onion. It sends a padding cell every 10
minutes. It reuses that onion until it breaks, then it opens another.



On first thought I vote option four. I'd like to hear your thoughts.

--Roger