From: anonymous-remailer@shell.portal.com
Date: Wed, 25 Jan 95 13:59:01 PST
To: cypherpunks@toad.com
Subject: Remailer
Message-ID: <199501252158.NAA12786@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

From: Louis Cypher (alt.anonymous.messages)

In this message I will analyze message reordering in remailers, and
traffic analysis in remailer webs.

Remailers which immediately resend incoming messages provide no 
security against an attacker who is able to watch all traffic to and 
from the remailer.  Two proposals have been suggested to solve this 
problem, latency and reordering.  In recent discussions, the consensus 
was that message reordering was superior to (and the actual intent of) 
latency.  Reordering is not sufficient, a form of latency is required 
to make it effective.

In this analysis, I assume that the reordering is accomplished by 
keeping a group of n messages at the remailer, and sending a random 
one whenever a new message comes. This is superior to simply waiting 
for n messages to arrive, then sending them all at once (I will show 
this later).

The attack on the reordering remailer is simple. The attacker sends a 
stream of marked messages through the remailer.  After the waiting 
messages have been flushed out, any incoming real message will be 
flushed out of the remailer before more arrive, allowing it to be 
uniquely identified coming and going.  The defense against this is to 
only check the group and send excess messages after a time delay. This 
delay should be the typical time for n real messages to arrive. A 
mixing of approximately n messages is ensured by this process. If 
there is no attack, then the mixing is not quite as good as keeping a 
group of 2n messages.

Here is the math on the reordering schemes:

1) Wait for n messages, then mix and send them all.
	The message is known to be one of those 10 (duh).

2) Keep a group of n messages. Send one of the n+1 when a new one 
	arrives.
	The message could be any message ever sent after arrival.
	That is not useful. How many messages does it take before we are
	90% sure that the message has been sent?

prob that the message has not been sent after x messages is (n/n+1)^x

Prob that it has been sent = 1 - (n/n+1)^x
Messages till 90% prob:  x=ln(.1)/ln(n/n+1)
For n=10, x=24, which is much better then 10 for scheme 1.

3) Accumulate b messages, then send a of them (Scheme 2 is a=1, b=n)
  x = ln(.1)/(ln(a) - ln(b))
  This gives the largest x  for a=1.
  In my example of how to defend against the flood attack, a=n, b=2n
  x = 33
  This is misleading, because it will introduce twice the delay as 
  scheme 2.
  Given the same delay, a=n/2, b=n, one finds that x=16.6
  That is better than batching, but not as good as scheme 2. The 
  smaller x is
  worth it, because a reordering of at least some minimum number of
  messages is ensured.

Some writer proposed changing n randomly to protect against this 
attack. Obviously that would not work. The attack will consist of many 
many more than n messages.

The second issue for consideration is:
Given a web of perfect remailers, how easy is it to identify 
corespondents? Tim has been asking this one for a while.

I assume that there is sufficient traffic through all remailers that 
any message entering the web could be any message leaving the web. 
This can be achieved, even with light traffic, by sending fake 
messages through the web to bit buckets. While they do not improve the 
security of the web as a whole, they help ensure that no tracking of 
messages within the web is possible, forcing it to be treated as a 
black box.
I assume that no correspondents are remailers themselves, and that all 
communications are random (random times with random people). This 
assumtion that all communications are uniformly distributed is 
terrible but....
This analysis only applies to indistinguishable messages. Each 
standard packet size can be thought of as having its own black box (a 
good argument for message splitting and having only one packet size).

To simplify the problem, I am going to treat the web as though it were 
clock driven. Some number of messages enter and leave the web each 
"tick" with no messages staying in the web between ticks.  This is a 
reasonable approximation, with the "tick" being the mean time of 
passage through the web.

Define "f" as the fraction of remailer using population sending a 
message in a given tick. This is also the probability that any 
individual will send a message in a given tick. The probability of a 
given pair of corespondents in a given tick is
	f^2
The probability of a pair of corespondents occurring m times in n 
ticks is
        m
p= 1 - Sum [(f^2)^i (1 - f^2)^(n-i) n! / (i! (n-i)!)]
       i=0

Lets put some numbers in there. If people send 1 message per day on 
average, and one tick is 30 min., then f=1/48. If you watch the web 
for a month you will see 1440 ticks. If the chance probability of your 
sending m messages to your co-conspirator  is too small then you have 
been nabbed.
The condition for that is: p << (1/population)

The results for m=0 to 12 (using the above numbers) are:

m = 0   	p = 4.64811E-1
m = 1   	p = 1.30173E-1
m = 2   	p = 2.56257E-2
m = 3   	p = 3.86587E-3
m = 4   	p = 4.71498E-4
m = 5   	p = 4.81967E-5
m = 6   	p = 4.23687E-6
m = 7   	p = 3.26538E-7
m = 8   	p = 2.23961E-8
m = 9   	p = 1.38336E-9
m = 10  	p = 7.77044E-11
m = 11  	p = 4.00273E-12
m = 12  	p = 1.91774E-13

So, for a remailer using population of 10,000 you had better send less 
than 5 messages per month to your accomplice.  This only gets worse 
the longer you keep it up. You can not send 4 per month, month after 
month.

		Louis Cypher

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBLybfL6yHUAO76TvRAQFhEwP+OMBMyESk97mVPNJMsoECl0YiJY+xnOqs
PHu3OT6j7igdu64NsAHxduwBLmArpgOFXEtrMBwXTkxzUZq6holJdQ+GPtQi787x
WtXhV2KkipW6z67TMxzjdSN7cVluQiMpnNhTSOpGUDcM8no3JD8/Ti1ficwljVkH
5kNx6RWFEpI=
=pRy3
-----END PGP SIGNATURE-----