Low-Cost Traffic Analysis of Tor

[Paul Syverson]

Hi Eugene,

Sorry to have read you too quickly. I thought after I sent the last
message that you probably were talking only about time not delivery.
Once upon a time (for at least part of the second generation design of
onion routing, i.e., gen 1) we tried to put some sort of mixing into
the design. I think we were wrong to bother; we mostly did to placate
various critics and referees and then kept it. The mixing will be
either inadequate to prevent any adversary of interest from
correlating flows or it will be too much of a performance overhead for
many applications. Several of us have talked about doing a midlatency
design, but that will be either a separate network or a Tor overlay, a
metalay network, if it is not to cost us most users for most
applications. In any case this would be a discussion topic for
or-talk rather than or-dev at this stage. Have at me again if I
have misconstrued you (or if you can show me wrong, which would
be great). But do it on or-talk or on the side.

aloha,
paul


On Fri, Oct 07, 2005 at 03:07:23PM -0500, Eugene Y. Vasserman wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: RIPEMD160
> 
> Hi,
> Probabilistic guarantee is a timeliness guarantee - delivery is still
> guaranteed, but the time within which this delivery is made is not
> guaranteed. (We could provide a weaker guarantee - say, this will be
> delivered before the TCP session times out. However, a complex guarantee
> policy might introduce an unacceptable performance hit.) The point is
> that round-robin scheduling (as Tor does now) is too easy to predict.
> What I suggest does not require changing anything expect the mixing
> strategy (which right now is round-robin - no mixing at all). I still
> haven't had a chance to look at the mixing code to see if this could be
> done with low-enough overhead as to not be noticeable by end-users. I
> don't want to make the argument on the performance/penalty tradeoff yet
> because I'm hoping there won't be any significant performance hit. I
> suspect it's possible, and can only be determined through testing. I'll
> report on my progress, if and when when there is some.
> Thanks,
> Eugene
> 
> Thus spake Paul Syverson:
> > Hi Andrei,
> > 
> > Who is this from?
> > 
> > Question from a two second glance, which is all I can spare at the
> > moment: probabilistic throughput guarantee? Does this imply
> > probabilistic guarantee of delivery? If so, you're talking UDP or
> > something not TCP in any case. In which case you're talking
> > substantial change from current Tor. Thus maybe an interesting design
> > theory suggestion, but something that will not be implementable in the
> > system for years if ever.
> > 
> > Gotta run,
> > Paul
> > 
> > 
> > On Fri, Oct 07, 2005 at 08:08:27PM +0100, Andrei Serjantov wrote:
> >>> 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.
> 
> - --
> Eugene Y. Vasserman
> http://www.cs.umn.edu/~eyv/
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.1 (MingW32)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
> 
> iD8DBQFDRtV74S3hfPlRZlkRA6KaAJ9v64LJ5OrqA22POcfZGu7gBNtrBQCbBLJ4
> ovdIV2Q1EDDKF5G2/Hv9Y3A=
> =0/lG
> -----END PGP SIGNATURE-----