15 July 1997: Add notice of update.
25 April 1997: Add Lucky Green's comments.
19 April 1997: Added Matthew Ghio's comments.
18 April 1997: Added Hal Finney's comments.
17 April 1997
To: cypherpunks@toad.com Date: Tue, 15 Jul 1997 13:27:53 -0400 (EDT) From: Mike Reiter <reiter@research.att.com> Subject: update on Crowds Back in April we circulated an announcement for a system called "Crowds" for browsing the web anonymously. Here is an update on its status. 1) There is a new, more complete version of the Crowds paper, and a new web page from which you can retrieve it. The page's URL is http://www.research.att.com/projects/crowds/ Of course, comments are welcomed and appreciated. 2) AT&T has finally decided to release the code, and we are working out a free license for noncomercial use with our lawyers right now. Once that is done, we would like to start alpha testing. Alpha testing will require some commitment from the testers, and we are looking for serious people who are interested in contributing to our attempt at providing anonymity to the Internet community. To be an alpha tester, you should have access to a machine - running SunOS, Solaris, or Irix - with Perl 5.003 or later - with a high-throughput connection to the Internet (no modems please!) - that is not behind a firewall Moreover, testers must be US citizens, due to the cryptography in the code. If you are interested in being an alpha tester, please send email to either of us. In your email, please describe the platform on which you'll be running. Mike Reiter <reiter@research.att.com> Avi Rubin <rubin@research.att.com>
To: cypherpunks@toad.com
From: Avi Rubin <rubin@research.att.com>
Date: Thu, 17 Apr 1997 17:42:36 -0400 (EDT)
We are developing a new system called "Crowds" for achieving anonymity on the web. A preliminary description of the system can be found on our web pages. Any comments/criticisms are welcomed and appreciated.
Mike Reiter (http://www.research.att.com/~reiter/)
Avi Rubin (http://www.research.att.com/~rubin/)
Mike Reiter's site has a compressed Postscript version of 81K:
http://www.research.att.com/~reiter/papers/dimacs-tr9715.ps.gz
Avi Rubin's NYU site has two versions :
1. An uncompressed Postscript version of 771K:
http://www.cs.nyu.edu/cgi-bin/cgiwrap/~rubin/crowds.ps
2. A compressed version of 81K:
http://www.cs.nyu.edu/cgi-bin/cgiwrap/~rubin/crowds.ps.gz
To: cypherpunks@cyberpass.net
Date: Fri, 18 Apr 1997 16:55:06 -0700
From: Hal Finney <hal@rain.org>
Subject: Re: A new system for anonymity on the web
> We are developing a new system called "Crowds" for achieving anonymity on the web. A preliminary description of the system can be found on our web pages. Any comments/criticisms are welcomed and appreciated.> Mike Reiter (http://www.research.att.com/~reiter/)
> Avi Rubin (http://www.research.att.com/~rubin/)
I took a look at this and it sounds like a very interesting project, quite far along.
The idea is that a group of web users each run a proxy program on their machine, which the authors call a "jondo" (pronounced "John Doe"). These are kind of like web remailers. The jondos all register with a server so they know which other jondos are out there running.
When it starts up, the jondo picks a path through the "crowd" of jondos, and sends messages to them to set up the path. The data through the path is encrypted so a local eavesdropper can't tell what path you are setting up.
Then, when you make web requests, the browser is set to use your local jondo as a proxy. The jondo takes the request and sends it down the path to the last jondo in the chain. That jondo, which doesn't know who the originating jondo is, sends the data to the web server, with the results coming back through the path. Your local jondo serves both as the originator of your requests, and it may also serve as the intermediate jondo of one or more paths belonging to other people.
The whole system is designed to be as efficient as possible. The path is left in place throughout your browsing session, so hopefully your messages will skoot through it without a lot of overhead. Once the path is set up the intermediate jondos only need to pass the data through without processing it, so that is not too costly. The authors suggest that the performance should scale well since adding more users also adds more jondos to carry the traffic.
We have discussed some generally similar ideas in the past, but this project apparently already has a prototype working, some 700 lines of Perl plus some crypto code. They have a server which keeps track of the jondos in the crowd, and they say they hope to release the first version soon for people to experiment with.
It sounds like it may be a good alternative to the anonymizer, especially if it can be more efficient. I'm looking forward to seeing their implementation.
Hal
To: cypherpunks@cyberpass.net
Date: Sat, 19 Apr 1997 17:25:11 -0400
From: ghio@temp0059.myriad.ml.org (Matthew Ghio)
Subject: Re: A new system for anonymity on the web
Hal Finney <hal@rain.org> wrote:
> I took a look at this and it sounds like a very interesting project,
> quite far along.
>
> The idea is that a group of web users each run a proxy program on
their
> machine, which the authors call a "jondo" (pronounced "John Doe").
> These are kind of like web remailers. The jondos all register with a
> server so they know which other jondos are out there running.
Yes, it's an interesting idea. Basically it works like this: The proxy server receives a request, and then forwards it to another jondo. That jondo then decides at random whether to get the web page from the server directly, or to forward the request to yet another jondo.
The authors point out a potential problem with this scheme: When a jondo recieves a request, there is a slightly higher probability that the requestor is the originator rather than an intermediary. Thus it is possible to statistically guess who is requesting what.
Their solution is to use a static system of connections, somewhat like a pipe-net, rather than a system in which the paths may change often. By creating a single path through which all requests from any given user are made, the statistical bias problems are eliminated. This also reduces the computational overhead by reducing the number of public-key encryption operations involved.
They also present a statistical evaluation of the traffic analysis problems inherent in a static-path recipient anonymity scheme. Most of these issues have previously been discussed in the context of remailer reply-blocks. Since the path can cross itself, or be forwarded to a collaborator's jondo, a forwarder along the path can watch messages and see where they go. This shortens the effective path for purposes of analysis, but doesn't conclusively identify the recipient, unless a substantial fraction of the users are collaborating against the rest.
The paper does not address the problems regarding the temporal nature of the information. Measuring the time between requests and responses, and knowing the types of delays inherent in the forwarding network allows an attacker to place an upper bound on the number of hops in the path. If, for example, the time delay between a user's browser receiving the text of an HTML page and when it sends requests for the images contained therein is sufficiently short, it could conclusively identify the originator of the request. Even if the intermediaries were unable to decrypt the request, a feature not present in their current design, the user could still be linked with the web page that was requested, through traffic analysis or collaboration with the end-server.
Since users are unlikely to tolerate long delays in retrieving the requested information, this suggests that any effective privacy-protecting system for web browsing would necessitate the use of a pre-caching system wherein the links on a web page would be pre-loaded and cached to minimize the ability of an attacker to measure the actual time between requests.
To: cypherpunks@cyberpass.net
Date: Fri, 25 Apr 1997 01:24:29 -0700
From: Lucky Green <shamrock@netcom.com>
Subject: Re: A new system for anonymity on the web
At 12:59 PM 4/20/97 -0700, Steve Schear wrote:
>Hal,
>
>What do you think of the "onion
routing" approach from the group at Naval
>Postgraduate? How would compare it to this newest proposal?
Neither one of them is any good in its present form. The folks at the FC'97 rump session got to watch Jim and myself poke truck sized holes into the NRL design within seconds of them ending their presentation. :-)
Here was a US military research lab presenting a system they thought would give them a way to surf the Net anonymously by using the public for cover traffic. [Let me just spell out here that I believe that the people from NRL and Cypherpunks are on the same side on this issue. Their concern is COMSEC, not SIGINT.]
Anyway, we knew how to crack their system without even having to think about it, since folks on Cypherpunks, especially Wei Dai, had discovered various venues of attack on such systems long ago. Cypherpunks are teaching the military about traffic analysis. :-)
The one good thing about NRL is that they seem to be willing to learn. [The other being that they get paid to write our code for us.] Though I get the distinct feeling that they don't like the required solution. There is simply no way to harden the system against attack without using a constant or at least slowly varying (I would guess we are talking about periods of several hours here, certainly not minutes, but I haven't done the math, nor do I have the time to do so) bandwidth data stream between the end user and the first Onion Router. This will invariably require special software on the end user's machine. I think the best design would be a client side proxy. [That much Crowds got right.]
As to Crowds, they got to be kidding. How many end users are willing to become, even without their direct knowledge, the last hop to <enter evil URL here>? I believe that relatively few users would want their IP address to be the one showing up in the server log of <enter seized machine's name here> because their jondo happened to be the exit point chosen.
-- Lucky Green <mailto:shamrock@netcom.com> PGP encrypted mail preferred
"I do believe that where there is a choice only between cowardice and violence, I would advise violence." Mahatma Gandhi