-----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----- ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.leitl.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE [demime 1.01d removed an attachment of type application/pgp-signature which had a name of signature.asc]