From: Hal <hfinney@shell.portal.com>
Date: Thu, 4 Aug 94 19:43:56 PDT
To: cypherpunks@toad.com
Subject: Remailer ideas
Message-ID: <199408050244.TAA16584@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


The MIRV idea for messages is not bad, but by itself it does not
provide enough cover.  If you have a 33K byte message come in and a
while later a 21K and a 12K byte message go out, there might not be
many other possible messages that could add up to 33K.

A more complete solution is to pad all messages to a standard size.
If every message which goes into the remailer is the same size, and
every message which comes out of the remailer is the same size, and
each has no carried-over header or message-body information, then
there should be no way of matching up incoming to outgoing message.
This was the simple solution in Chaum's original February 1981 CACM
paper, which I would strongly suggest that people read.  CACM is
probably the most widely available of the computer science journals
and should be at every university library.

Chaum's paper has some interesting aspects that are not often
mentioned.  He actually proposes two different solutions that differ
somewhat.  (People should also be aware of his alternative solution to
the traffic analysis problem, the "Dining Cryptographers" network.  I
think Tim may have scanned that in at some point, so it might be on
the net.  DC nets tend to be high bandwidth and are more suitable for
LANs or WANs than email, IMO.)

The first solution in Chaum's paper is the "Cascade".  In this there
is a sequence of "Mixes", what we would call remailers, which are used
in a FIXED order by everyone.  It's as though everyone first sent
their messages to soda, then to portal, then to catalyst, and so on
through some specific sequence.  Furthermore, these are all sent in a
set of batches which stay together as they move through the network.
A batch of messages starts at soda, then at a later time that same
batch pops out the other end, having been decrypted and shuffled at
each step.

From our perspective, this seems like a wasteful way of using the
network.  By keeping the messages together like this, the whole
cascade does no more shuffling than would a single mix.  Using the
cascade provides no more confusion of messages.

But the advantage it does provide comes from the fact that there is no
guarantee that the remailers are honest.  This is something which is
often overlooked by people who make suggestions that remailers should
cooperate, should automatically choose the message paths, etc.  Chaum
uses the cascade so that if even one mailer on the chain is honest and
uncorrupted, the whole chain is strong.  If you _knew_ you were using
a good remailer you wouldn't need a cascade.  But by using a cascade
you get that much more assurance that you have security.

The other reason for using a fixed cascade, I think, has to do with
the details of message padding.  The problem is that, generally, when
you decrypt a message it is not exactly the same size as it was when
you started.  Particularly with remailer messages, where there may be
some encrypted address information along with the message, the output
will tend to be smaller than the input.

By using a cascade, the messages will all shrink in step as they move
along.  All of the messages coming in to any mix in the cascade will
be the same size, and all the messages going out will be the same
size, but the outgoing messages may not be the same size as the
incoming ones.  It is this size differential which would make it hard
to safely combine messages which have gone through different numbers
of mixes.

Chaum does go on to suggest a solution to this as the second main part
of his paper.  That part is considerably harder to follow, but the
main idea seems to be that the mixes themselves will add padding to
the end of the messages so that they stay the same size.  Chaum
describes this in terms of messages composed of fixed-size blocks, but
it would seem that the idea could be generalized to a remailer which
added random padding to bring the output message up to the standard
size.  I can't see any security leaks in this generalization.

One interesting idea Chaum suggests is that after the remailer
decrypts the messages in its batch, it does not simply send each one
to the next address, but rather broadcasts them (perhaps to all of the
other remailers).  Those remailers try decrypting all of the incoming
messages and only those messages for which the decryption succeeds
will be sent on.

Again, I'd suggest people interested in reamailers read this
paper.  I believe there were some follow-ups in the Crypto 89 proceedings,
but my library is missing that volume so I haven't seen them.

Hal