Low-Cost Traffic Analysis of Tor

[Eugene Y. Vasserman]

-----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-----