From: cme@ellisun.sw.stratus.com (Carl Ellison)
Date: Mon, 23 Aug 93 14:51:39 PDT
To: cypherpunks@toad.com
Subject: Re: Attacks on remailers
In-Reply-To: <9308230602.AA25533@jobe.shell.portal.com>
Message-ID: <9308231749.ZM12733@ellisun.sw.stratus.com>
MIME-Version: 1.0
Content-Type: text/plain


On Aug 22, 11:02pm, hfinney@shell.portal.com wrote:
> Subject: Attacks on remailers
> Chaum, in his first paper on "Mixes" (anonymous remailers) described
> protocols which were designed to resist several attacks.  (See the
> February, 1981, Communications of the ACM, p. 84.)  These can
> be understood by considering a series of attacks of increasing sophis-
> tication, with corresponding responses.
> 
> Our opponent has as his goal to track a message through a chain of
> remailers.
> 
> Attack 1: Just intercept the message from the sender, and look at the
> commands of the form:
> ::
> Request-Remailing-To: first-remailer
> ::
> Request-Remailing-To: second-remailer
> ::
> Request-Remailing-To: final-destination
> 
> The final command shows where the message is finally going to go.
> 
> Response: Encrypt the messages.  Use "nesting", so that all that is
> visible as each message leaves a remailer is the destination of the
> next remailer.
> 
> Attack 2: Look at the mail logs on the system running the remailer to
> see which message goes out from the remailer account shortly after each
> message comes in.
> 
> Response: Run the remailer on a machine which does not keep mail logs,
> or on a machine to which you can deny the attackers access.
> 
> Attack 3: Monitor the messages in real time as they flow into and out of
> each remailer machine, again looking for the message which comes out
> just after each incoming message.
> 
> Response: Batch up many messages which arrive over a period of time,
> only sending them out at regular intervals or when a certain number have
> accumulated.  Send them out in random order.  Alternatively, delay each
> message by a random amount of time before the message goes out.  (This
> response will also deal with the previous attack.)
> 
> Attack 4: Look at distinguishing features of the messages which are
> preserved by the remailers, such as subject line or message size, to
> match up incoming and outgoing messages within each batch.
> 
> Response: Do not retain any header fields through remailers, not even
> subject.  Use an encryption mode in which messages are rounded up to
> some standard size so that all messages appear to be the same size.
> 
> Attack 5: Record an incoming message to the remailer, and insert a copy
> of it into the incoming message stream, so that the batch will have two
> identical messages.  Look for two identical outgoing messages.  Remove
> one.  This is the match to that incoming message.
> 
> Response: Check for duplicate incoming messages in the remailer, and
> remove all but one copy of each duplicate.
> 
> Attack 6: Insert a duplicate message multiple times in separate batches.
> Observe the outgoing batches and look for a pattern of destinations
> which are correlated with those batches in which the incoming message
> is inserted.
> 
> Response: Check for messages which have been duplicated from earlier
> batches and remove them.  Include time/date stamps on incoming messages
> with a time limit so that they are no good after a certain number of
> days; this way the check for duplicates only has to go back that many
> days.
> 
> Attack 7: Look at all messages coming out of the first remailer, and
> follow them into their 2nd remailers; take all messages from those and
> follow them on, and so on.  This will eventually lead to a number of
> destinations, one of which must have been the destination of the original
> message.  Over a period of time, look for correlations between destinations
> and sources.
> 
> Response: Use large remailer chains of popular remailers.  With enough
> mixing at each stage of the chain, the number of possible destinations
> will become astronomically large, making correlations statistically
> impossible.
> 
> Attack 8: Correlate messages being sent from person A with messages being
> received a certain time later by person B.  Even without the ability to
> track messages through the remailers this can show a communication pattern.
> 
> Response: Send dummy messages at regular intervals, which bounce through
> the remailer network and then die.  When you have a real message to send,
> replace one of the dummies with this.  The sender's traffic pattern is
> then constant and no information can be gained from it.
> 
> Attack 9: Bribe or coerce one or more remailer operators into revealing
> their keys, or into decrypting the desired messages.  Alternatively, run
> many remailers, pretending to be dedicated to privacy, while secretly
> gathering information on the messages.
> 
> Response: Use many remailers in a variety of geographical locations, so
> that it is unlikely that all of them can be corrupted in this way.
> 
> These are all the attacks I can remember being implicitly considered in
> Chaum's paper.  Other people who have ideas for attacks should mention
> them so we can think of responses.
> 
> Chaum also discusses anonymous return addresses.  We have a simple form
> of these enabled in our encrypting remailers.  The idea is to encrypt
> a series of remailing requests for the path the message will follow,
> with the last request directing the message to the user whose anonymous
> address this is.
> 
> Some more attacks are possible in this case:
> 
> Attack 1A: Look at the message content as it passes through each remailer,
> to correlate incoming and outgoing messages.
> 
> Response: Encrypt the message at each stage to prevent this matching.  This
> raises the problem of how to determine the encryption key in such a way
> that the final user can decrypt the message.  Chaum suggested including the
> encryption key in the anonymous address (a different key at each stage
> of the chain), so that the user can decrypt the message.  Eric Messick
> has proposed letting the remailer choose the key, with a protocol for the
> user to communicate again with the remailer to get the message decrypted.
> 
> Attack 1B: Send two different messages to the same return address with
> different contents, and look for duplicate address blocks in the outgoing
> batches.
> 
> Response: Apply some randomization to the address blocks at each stage so
> that messages to the same address don't look identical.  (Chaum did not
> give this solution, as he viewed the next attack as being essentially
> unanswerable.)
> 
> Attack 1C: Send many addresses to the anonymous address, and look for a
> destination which receives that many messages in a correlated fashion.
> 
> Response: Chaum's response is that the remailer must not accept more than
> one message with a given anonymous return address, just as it must not
> accept more than one copy of a message in the regular case.  This implies
> that anonymous return addresses must be use-once to be truly secure.
> 
> This conclusion is uncomfortable, as the requirement that an address be
> use-once will severely impair its usability.  But this attack appears
> hard to avoid.
> 
> There is always the possibility of giving up on anonymous addresses in
> the Chaumian sense, and instead using other ideas which have been
> suggested here, such as posting to newsgroups, or message broadcast
> pools.  All of these ideas have the problem that they expose everyone
> in some group to all of the messages intended for every group member,
> hence the number of messages will scale as the square of the number of
> group members.  This will quickly become unmanageable for large groups,
> therefore providing only a limited amount of anonymity.
> 
> It's also worth noting that our remailers are vulnerable to almost all
> of these attacks; at best we are safe against two or three of them.
> 
> Hal Finney
> hfinney@shell.portal.com
>-- End of excerpt from hfinney@shell.portal.com