Remailer

-----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-----

On Wed, 25 Jan 1995 Louis Cypher wrote:

> 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.

	I have literally hundreds of messages archived from the CP list of
several months back where Eric Hughes repeatedly states that reordering,
not latency, is the key. Reordering of a sufficient magnitude will
introduce latency inherently. Otherwise you are still vulnerable to 
traffic analysis (which is an art, not a science, remember).

--
Michael Handler                                         <grendel@netaxs.com>
Civil Liberty Through Complex Mathematics                   Philadelphia, PA
"Toi qui fais au proscrit ce regard calme et haut" -- Baudelaire * Skotoseme
PGP Key ID FC031321  Print: 9B DB 9A B0 1B 0D 56 DA  61 6A 57 AD B2 4C 7B AF

| 	I have literally hundreds of messages archived from the CP list of
| several months back where Eric Hughes repeatedly states that reordering,
| not latency, is the key. Reordering of a sufficient magnitude will
| introduce latency inherently. Otherwise you are still vulnerable to 
| traffic analysis (which is an art, not a science, remember).

	Are you sure TA is still an art?  The NSA has (presumably)
spent thousands of man years on the problem.  Hal, Wei Dai and others
have done some very good work.  While I've only skimmed the surface of
it, its clear that clever statistical work comprises a lot of TA.  It
may be that the FBI has a couple of Suns handling the whole remailer
network right now.

	Also, if anyone wants to lok at the archives, the best thread
is subject reordering vs. latency.

Adam

-- 
"It is seldom that liberty of any kind is lost all at once."
						       -Hume

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

On Thu, 26 Jan, Adam Shostack <adam@bwh.harvard.edu> wrote:

> [quoting another Cypherpunk]
>  >>>> traffic analysis (which is an art, not a science, remember).
> 
> 	Are you sure TA is still an art?  The NSA has (presumably)
> spent thousands of man years on the problem.  Hal, Wei Dai and others
> have done some very good work.  While I've only skimmed the surface of
> it, its clear that clever statistical work comprises a lot of TA.

Adam is correct, as least if you believe Bamford.  _The Puzzle Palace_
lists some of the courses in the NSA's 3-year Traffic Analysis Intern
Program, along with some entertaining questions from the Agency's
aptitude test designed to ferret out potential traffic analysts.  IMO,
far more science than art is involved.


Alan Westrope                  <awestrop@nyx10.cs.du.edu>
__________/|-,                 <adwestro@ouray.denver.colorado.edu>
   (_)    \|-'                  2.6.2 public key: finger / servers
PGP 0xB8359639:  D6 89 74 03 77 C8 2D 43   7C CA 6D 57 29 25 69 23

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

iQCVAwUBLyegOlRRFMq4NZY5AQFACwP9F5usLixVxAm8SxMIK8D9SVWk6j3bWNwL
FgD9sgPGiPJnXhoJVG/OcJnxG1kyvYCiyA1D8WV8m4vMvVAoq83fvtXbCHYd7hit
TjkieVjajKthWDpRlcPaRYFv1QfVTuUHkYbTNZpCfhkcuDenPTe9Uo5ZeB/qWZUz
oe4eZWc3L10=
=87WF
-----END PGP SIGNATURE-----

Adam Shostack says:
> It may be that the FBI has a couple of Suns handling the whole
> remailer network right now.

If they are doing that, they are violating the ECPA. They are allowed
to monitor only those things they have a warrant to monitor (with, of
course, all those lovely National Security exceptions). This is not to
say that it isn't being done, but it can't be used in court.

Perry