Low-Cost Traffic Analysis of Tor

[Andrei Serjantov]

> Greetings. Let me introduce myself. I'm a grad student and the U of MN
> in computer science. I've been working on anonymous network systems. I
> also had a chance to play with Tor, and read the "Low-Cost Traffic
> Analysis of Tor" paper (mentioned below).
> I have a general question: this may or may not decrease performance, but
> wouldn't locking and/or randomizing bandwidth per flow through a Tor
> server solve this problem? This attack seem comparable to a variant on
> SSL (and general crypto) timing attacks. Similar solutions could be
> applied. Also, since this attack relies on a malicious node being able
> to estimate its flow's likely performance through an honest node at any
> given time, Tor could apply a somewhat more complex mixing approach,
> making this attack more difficult. I was thinking of something like
> lottery scheduling, which is really easy to implement and, if done
> right, will not impose any noticeable CPU overhead, and still provide
> the same (albeit probabilistic, not deterministic) throughput guarantees
> for every flow. Please let me know your thoughts. I will hopefully have
> some time to spend implementing this in the near future, if there is a
> consensus that some of these suggestions would help.

Before you start hacking, I would advocate writing down your mixing
strategy and trying to show (or at least argue) that what you are
doing has a reasonable anonymity/performance tradeoff. It's probably
worth sticking my nose out and saying that Tor does not really want to
do any mixing for performance reasons -- lower performance means lower
number of users and hence lower anonymity sets against weaker
adversaries..... (hmm is this strictly true?? I suppose the anonymity
set is the set of all people if you don't observe the entire network)

A.