Attacks on remailers

[hfinney@shell.portal.com]

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