From: Hal <hfinney@shell.portal.com>
Date: Wed, 12 Jun 1996 09:30:38 +0800
To: cypherpunks@toad.com
Subject: Re: Anonymous return addresses
Message-ID: <199606111814.LAA19675@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


From: "Robert A. Rosenberg" <hal9001@panix.com>
> If the message is split into more than one part (to meet the message size
> requirement) there is some potential leakage to each server of what message
> is being requested. If User a requested 3 messages, then they MAY be
> requesting all three parts of a 3 part message (or 2+1). If a record is
> kept of the number of requests over time, then there can be some regression
> checking based on the ID (ie: If the number of new messages for ANx in the
> DB matches the number that User Y requests in the current session). I may
> be in error with this thought but it looks like a possible problem.

Yes, this is a good point.  It might be addressed by having the later
parts of a multi part message not be identified with the anon ID of the
receiver, but rather with a random message label which is revealed to the
receiver in the first part of the message (encrypted, of course).  Then
the database owner could not tell which message parts went together just
by looking at the messages.  Arrival times might give this away, though,
if all parts of a multi-part message were sent at about the same time.

> >Messages would have a finite lifetime and would expire and be removed
> >from the database after a while.  The authors propose breaking the
> >database up into batches with a fixed number of messages, but I don't
> >fully follow the reasoning behind this.  I guess it reduces the load on
> >the server when it does its XOR's.
> 
> This can also affect the "attack" I speculated on above since it can "leak"
> more info. Multi-part messages (or multiple messages to the same recipient)
> which are retrieved in one session can be correlated between the groups
> (ie: User Y asked for 5 messages [Selected from Groups 1&5] and ANx is the
> one AN? that has the requested number of messages in each of the Groups
> [ie: 3 from G1 and 2 from G5]).

Yes, there is a tradeoff with the batch size between efficiency and
privacy.  The multi-part message issue does seem to make the problem
potentially worse.  Maybe it would be necessary for anonymous receivers
to mostly receive small messages, and/or make the message granularity
relatively large.

Some of these kinds of volume- or correlation-based traffic analysis
techniques can be countered by requesting dummy messages, ones which the
receiver won't be able to read.  If he asks for five messages every day
from that day's batch then it doesn't leak any information about which
ones are for him.  Asking for a random number averaging five may work
even better, if occasionally he really needs to read six.

Hal