Sampled Traffic Analysis by Internet-Exchange-Level Adversaries

[Paul Syverson]

On Wed, May 30, 2007 at 02:46:20AM -0700, Mike Perry wrote:
> Thus spake Paul Syverson (syverson at itd.nrl.navy.mil):
> 
> > Anyway, the main reason I'm writing is that my objection was not just
> > that the GPA was too strong but that it was too weak. Thinking you
> > could have an adversary powerful enough to monitor all the links
> > necessary to watch your whole large network but not able to do any
> > active traffic shaping at all anywhere seems obviously nuts. This is
> > one reason why padding on an open low-latency (lossless) network is
> > problematic: an adversary with any active capability at all can induce
> > a timing channel easily.
> 
> Actually, I'm going to disagree slightly because I don't feel like
> sleeping yet :). It would take far less resources to passively tap the
> traffic and filter out say Tor IPs and do analysis on just that data
> offline. Trying to actively do that filter in-path PLUS arbitrarily
> delay (ie queue in memory) that traffic in real time, all without
> signficantly affecting pass-through traffic seems like it would be a
> lot more expensive.
> 

If the traffic patterns can be stored and analyzed offline rather than
in real time, it just makes my point stronger.  Assume
someone with the ability to do truly global monitoring, watching
every connection from every client everywhere in the world through
every tor node everywhere in the world to every server everywhere in
the world (Note that I was effectively assuming the filtering you mentioned.
I don't care if the adversary watches non-Tor traffic. I assume they
have already made that separation. As you note, it is trivial to
recognize traffic going to/from/between Tor IP addresses.)
What I am saying is that it is nuts to assume that someone could have
monitors on all of these places but can do nothing active at all,
not even doing something as trivial as killing a targeted circuit
and watching to see if a suspected circuit dies elsewhere. It doesn't
even have to be targetted. The adversary can simply arbitrarily induce timing
channels in various places or kill circuits or whatever
and watch for those patterns elsewhere (in the stored
data if this is done offline).


> Also, not to mention there is a limited number of bits that can be
> reliably encoded in this manner, and the purturbations of padding that
> shares the same TLS connection will lower this effectiveness. The
> adversary needs enough bits to get through to be able to track all the
> parties it is interested in. If padding is in place, it will have to
> spend considerable effort in redundancy to make sure that the
> timestamp remains present in the exit stream.. Which again means more
> queueing and more expense. 
> 

Lasse and I saw how incredibly easy it was to find patterns with very
limited resources. George and Steven showed how you could induce patterns
gross enough to even monitor them by interference (albeit on a much
smaller and generally lower bandwidth network). 


> Of course, it also means more expense on the part of the anonymity
> network in wasted bandwidth.. If padding slows down the network to the
> point where users start to leave, other, more dangerous effects take
> over.
> 

I'm not comparing a global passive adversary with a global active one
and claiming that global active is more realistic or practical.  I'm
saying that it is a mistake to posit a truly global adversary (not
just a really big adversary watching, e.g., eighty percent of all the
communication we would ever be talking about) that cannot do even the
tiniest local thing actively. Nonetheless, that is the adversary from
much of the literature.


aloha,
Paul