strengthening remailer protocols

This is long enough.  I've been brutal and cut sections less
likely to promote discussion.

(I've also contacted OUP about Ganley's book, and may 
 buy it if I can kid myself I don't need the money.)


============================================================
August 1996
Peter M Allan
peter.allan@aeat.co.uk


                   Strengthening Remailer Protocols

STATUS OF THIS MEMO

This memo proposes improvements for the Mixmaster protocol and
requests discussion and further suggestions.
Distribution of this memo is unlimited.

INTRODUCTION

Lance Cottrell's documents [1] and [2] describe the current Mixmaster
protocol and attacks against it.  This memo began as a response to
those thoughts, but has developed in discussion with Cottrell.


SPAMMING ATTACK

[2] describes an active attack where many messages are sent to an
honest remailer to separate a message of interest from other
traffic.  The aim is to clear other messages out of the message pool,
wait for the target and finally eject that from the pool.  The target
message is identified because the attacker can recognise  his own
messages.

Attempts to defeat this attack could well be based on preventing the
attacker from recognising his own messages.  That is the approach
taken here.

     RE-ENCRYPTION AS A SPAM DEFENCE
     
     In this diagram remailer 'A' has received a message addressed to
     himself.  Inside that is one to 'B' - unreadable to A.  Further
     layers are hidden of course.

                AB?????  decrypts to B?????

     This means that our remailer can only disguise the message by
     re-encrypting it on the outside.  But the message has got to
     make some net progress toward delivery.  The trick is that a
     remailer can find the outer two headers addressed to him and
     process both of them.  Two headers processed and one rewound is net
     progress.  When the header rewound is addressed to the same
     recipient as was next on the list anyway the diagram looks like
     this.

     Actions at 'A':            AB????? decrypts to  B?????
                                 B????? encrypts to BB?????

     Actions at 'B':            BB?????  decrypts to B?????
                                         decrypts to  C????
                                         encrypts to CC????

     The beauty of this is that it is compatible with the existing
     protocol.  If a remailer only knows about removing layers of
     encryption it still fits into a network where some can do both
     actions.  Whether it sends or receives the message it still
     works.


     RE-ENCRYPTION IN THE MIXMASTER ROTATING QUEUE MODEL
     
     Instead of layers like an onion, Mixmaster has a queue of
     headers that get rotated.  A used header goes to the back of the
     queue where it can never again be read.  At some point the
     header at the front of the queue is found to be the last one,
     and the message is sent on its final hop.

     For a header queue the above actions look like this:

     Actions at 'A':        AAAB???  -> AAB???a
                                     -> AB???aa
                                     -> BB???aa

     In general when the first H headers are addressed to the
     remailer reading them, (H-1) rotations will be performed, and
     the top header will be overwritten with another one with a
     random key and IV to encrypt the rest of the message.  The
     number of headers present remains 20, however many or few of
     these are still to be read.  No valid header block is ever
     overwritten, only used header blocks that are good for nothing.
     This is always possible because after a remailer receives a
     message at least the one header it has just read must be of no
     further use.

     This will hide the message content from eavesdroppers, but not
     from the next remailer in line - 'B'.  Assume that remailer B
     is operated by an attacker, and that he directs spam messages
     there after host A (which is holding your message in the pool at
     the time of the attack).  B can read all messages sent by the
     attacker (who knows B's private key).  This is also why I think
     link encryption offers incomplete protection.

     RE-ENCRYPTION WITH CHEATERS

     Mixmaster assumes that no particular remailer in the network can
     be trusted and that the user does not know which remailers
     cheat.  The message passes through a chain of remailers, who aim
     to hide information from each other so that the compromise of
     some of them will not disclose the original sender and final
     destination.

     Central to the spamming attack is the idea that the attacker can
     recognise the messages he is trying to trace.  This is done by
     eliminating  his own messages.   The whole set - not just
     some of them.  It can be arranged that the attacker does not
     obtain the whole set until it is too late to trace the target
     message (i.e. after a few hops, when it is likely to have met other
     legitimate traffic).  The partial information the attacker obtains
     before all the spams are identified will be of some use, but
     following each of several leads with a new spam attack is unappealing
     as the number of suspect messages will just grow.

     The remailer needs the freedom to divert packets to another
     remailer.  This is shown below; where remailer C was chosen at
     random.

     Actions at 'A':        AAAB???  -> AAB???a
                                     -> AB???aa
                                     -> CB???aa

     Each remailer could have three options when sending a packet to
     its next host.

        1) rotate all possible headers, and send the result  (current protocol)
        2) re-encrypt message with new 3DES key and IV.  Do not divert.
        3) re-encrypt message with new 3DES key and IV.  Divert at random.
     
     Good probabilities for these options might be:

        1) 20%   P(1) = P(3)  The number of headers the next host can read
                 should not reveal whether a diversion has just been made.
                 (We care about this because it discourages cheaters
                  deliberately refusing to pass on your mail.)
        2) 60%   Other outgoing packets are not distinguishable from spams.
        3) 20%   Should not approach 100%.
                 (To arrive is better than to travel in hope.)
     
     A spam attack as described in [2] would use many more packets
     than those in the message pool (N) on the host under attack.  The
     number of spam packets diverted to honest remailers (a
     proportion R of the whole) would be about

		 MANY  . N  . P(3) . R

     and those diverted twice in succession to honest remailers would
     be about

		 MANY  . N  . P(3) . P(3) . R . R

     and I'd expect a figure above 5 here to thwart the spammer, because
     of the time taken to collect the 5 spams.

     This diversion (adding steps to the middle of a chain) seems different
     from a Middleman scheme [3] where extra hops are added at the end.

     This scheme does NOT allow a remailer to choose the rest of the
     chain to be followed.  A dishonest remailer cannot bypass any
     remailer chosen by the original sender (in the hope of following
     the message to its destination) using only cooperating dishonest
     remailers) because the message has been encrypted in the public
     key of each remailer the sender chose before it entered the
     network.



REFERENCES

1      Frequently Asked Questions about Mixmaster Remailers
       FAQ Version 1.8 July 4 1996
       by Lance Cottrell <loki@obscura.com.>


2      http://www.obscura.com/~loki/remailer/remailer-essay.html
       by Lance Cottrell <loki@obscura.com.>

3      email  "Re: middleman - what is it ?"
       "John A. Perry" <perry@alpha.jpunix.com>

At 2:25 PM -0700 9/2/96, John Anonymous MacDonald wrote:
>I don't really see the use of this complicated scheme.  The main
>problem seems to be that if M floods remailer R with messages to B,
>and A sends a message to C through R, then it will be clear to M that
>A's message was destined for C.
>
>Rather than divert messages, then, I propose that for each input
>message there is a 10% chance that a piece of cover traffic is
>generated.  Thus, if M sends 50 messages through R and sees 6 outgoing
>messages going to remailers C, D, and D, he will now know which
>messages correspond to the message that A send through.

I quite like this load based cover traffic scheme. Another defense against
flood is to slow the rate at which the messages leave the system. A simple
modification to Mixmaster (which will be in the next version) is to have an
exponential pool. The operator sets two parameters, a minimum pool size,
and a fraction of messages to send each time the pool is processed. 10
messages and 10% seem like good settings to me. Given at least one cover
message each time the pool is processed, flooding is much less productive.

A side benefit of this system is a reduction in the load on the sendmail
system during a flood or spam.

	-Lance

----------------------------------------------------------
Lance Cottrell   loki@obscura.com
PGP 2.6 key available by finger or server.
Mixmaster, the next generation remailer, is now available!
http://www.obscura.com/~loki/Welcome.html or FTP to obscura.com

"Love is a snowmobile racing across the tundra.  Suddenly
it flips over, pinning you underneath.  At night the ice
weasels come."
                        --Nietzsche
----------------------------------------------------------

Peter Allan <peter.allan@aeat.co.uk> writes on cpunks:
> [re-encrypting as a mechanism to prevent an attacker in a spamming
> attack reconizing his own messages]

The attack Peter is hoping to frustrate is as follows: target message
being sent from Alice to Bob through remailer R.  The attacker in an
active `spam' attack floods remailer R so that he will recognize the
target message and it's destination.

Another approach to making the transmitted message unrecognizable to
it's owner would be to finish the implementation of D-H key exchange
in mixmaster.  (The version I am looking at (2.0.3) does not have the
D-H key exchange and direct socket communication implemented, rather
it delivers mail by sendmail, I believe).

As a bonus this provides forward secrecy, so that not even a supeonaed
remailer operator would be able to reconstruct the destination.

You can still do a spamming attack by recognizing the destination,
rather than the message: Eve forwards enough messages to remailer R to
flush the target message.  Each of Eves messages is headed to a known
(to Eve) address.  Say the remailer R has a buffer of 10 messages, if
Eve sends 9 messages, 3 to each of remailers R2, R3, and R4.  Eve can
then determine the destination of the target message: the remailer
which gets 4 messages is the destination remailer.

(Here my knowledge of mixmasters workings are wearing thin, but I
believe it does these things, or provides facilities so that the
operators/users can make sure these things happen).

The way that this kind of attack is frustrated is that dummy messages
are created as cover traffic by the remailer, and that at some points
messages can be swallowed by a remailer as junk messages.

Sufficient junk cover traffic would ensure that even with a spamming
attack the destination would not be known immediately because the
attacker can distinguish the target message from the junk.

Ultimately a good way to foil this attack in general is to have each
remailer send a fixed amount of mail to each other remailer in cycles.
No traffic analysis if all remailers get equal traffic.

The only entry point for analysis then is the entry and exit points.
The active spam attack then would be to block, or delay all entry
points into the remailer net, apart from the target message.  The only
messages in the network would then be the spam traffic, and the target
message.  When the target message leaves the net, the Eve knows the
destination.

To hinder this attack, the remailers could generate and mail to
previous users junk mail.  Over a long time, statistical attacks could
perhaps be built on a pair of users who communicated frequently.  The
ultimate solution to this is for the users also to receive fixed
amounts of junk each day.

Starting to sound like similar overheads to a DC net, huh?

Peters other suggestions of adding random diversions sound like
reasonable ways to add another form of cover traffic, and should help
make life harder for the attacker,

Adam
--
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)

I don't really see the use of this complicated scheme.  The main
problem seems to be that if M floods remailer R with messages to B,
and A sends a message to C through R, then it will be clear to M that
A's message was destined for C.

Rather than divert messages, then, I propose that for each input
message there is a 10% chance that a piece of cover traffic is
generated.  Thus, if M sends 50 messages through R and sees 6 outgoing
messages going to remailers C, D, and D, he will now know which
messages correspond to the message that A send through.