Bandwidth throttling (was Re: Padding)

[Paul Syverson]

Hi guys,

So I hope I can devote a good deal of time for a while. Sorry for my
persistent distractions. I can try to respond to specific things that
have arisen in discussion but since I read last night through the whole
conversation of the last c. week I thought I might lead in with some
summarizing observations, thus simultaneously revealing my ignorance
and insulting all your hard work to this point.

The threat model seems to be crucial. Unfortunately, we don't have a
real idea of what is likely to be feasible. To some extent we won't
until we have experimental evidence or at least simulations.  I talked
with Roger on the phone this PM about this. In short, we are hosed
against a global adversary, even a passive one, and I think anything
we could reasonably do to stop him would likely make the network
impractical for intended applications.  So we are talking about some
kind of partial adversary. In the OR security paper in the first PETs
workshop, we looked at a roving adversary.  Without going into why we
chose it, I'll just say that, contrary to what was said there, I am
currently thinking that a roving adversary is probably not significant
for OR. Most connections are too shortlived to be vulnerable to such
an adversary, and since routes should shift with new connections
correlating multiple connections will only be doable after one has
already determined the endpoints, in which case the threat is already
realized. But, what is reasonable in that is the partial compromise of
the network. An adversary has a budget, and short of a systemic
vulnerability, he must compromise individual network elements or set
up his own. Roger noted that a good way to think about his budget
might be in terms of the reputation.  That's food for later thought.
For now we can simply think about an adversary owning some percentage
of the nodes. On to some specifics.


On confirming Alice and Bob are talking:

(1) If Alice and Bob live on pipes hanging off the network that are
visible to the adversary, then I think they are hosed for ordinary
applications. And I don't think padding/throttling will do any
good unless it is onerous on pipenet levels.

Basically it will be trivial for the adversary to correlate the timing
of connections opening and closing and the packet volume signature
over time to confirm their connection(s). Even if these are
padded/throttled to some reasonable rate an active adversary
can easily induce a signature on them.

Countermeasures we considered some time ago include partial length
padding similar to some of what has been discussed. Our idea was to
use inband signalling (from the OP) to indicate to a COR when to
drop/add a packet. Since the idea of inband signalling created
religious wars among us, there was a one bit field put in the onion
header to indicate whether or not the connection was one where inband
signalling was permitted. Another idea was to announce in the onion
some adding dropping regimen to each of the CORs in the route. Another
countermeasure was to have partial routes that are left up and then
make an OR connection to the head or tail of a route and mate it to
the existing partial route (or conversely extend the tail of a partial
route with more CORs). This will complicate the correlation of
connection opening and closing.

I don't think these will help much against the threat we are
considering. I suspect that the noise that this cover activity creates
can only be either inadequate or too expensive (or both).

Mostly we just need to live with this because of our application
requirements. If we are willing to live with delays that will make
remote login connections and even web traffic pretty ugly (and willing
to modify the application or application proxy so that the application
doesn't timeout), then we can do some form of actual mixing (both on
connection setup and data transfer). What we had contemplated long ago
was something like stop and go mixes. This, possibly combined with
route mixing and matching "frequency hopping" etc. would probably go
much farther than any padding scheme with less overhead.

So, I think for this access configuration we should not be talking
about padding at all.

(2) If Alice is in local-COR configuration (essentially running
her own OR or variants thereon), then things get more hopeful hence
trickier. (Let's leave Bob out of the discussion for the moment.)

Suggestion: Alice with a local OP and a remote COR, but a connection
to the COR that is not observed or controlled by the adversary is
essentially in local-COR configuration. (Of course if the COR
she first connects to is adversary, then the connection is observed
by the adversary, hence this suggestion does not apply.)

Essentially in this case an adversary would need to determine that
the Alice OR is the endpoint of a connection. How hard is that?
For the next OR on the route pretty easy from watching cell timings,
etc. For ones further on it becomes harder if there is link padding.
The same applies to Bob or someone watching Bob's connection to the
OR network (i.e., assuming Bob is not in local-COR).
For this reason I think link padding is useful.
If Alice and Bob are both in local-COR, then it seems likely that
the next hops in a connection between them would be able to know
they are second hops and thus know that Alice is talking to Bob.

Woops gotta run.  I will leave discussion of link padding regimens and
congestion and flow control for tomorrow. Anyway, that's a start I
hope.

aloha,
Paul