From: tcmay@netcom.com (Timothy C. May)
Date: Sun, 7 Aug 94 22:00:21 PDT
To: hfinney@shell.portal.com (Hal)
Subject: Re: Latency vs. Reordering (Was: Remailer ideas (Was: Re: Latency vs. Reordering))
In-Reply-To: <199408070216.TAA09025@jobe.shell.portal.com>
Message-ID: <199408080501.WAA27022@netcom7.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


I've left the subject line unchanged, to show an unusual _triple
nesting_ of subjects!

Also, I just got back after a weekend away, and so am only now seeing
these interesting messages about remailers, entropy, etc. A subject of
great interest.

Hal Finney writes:

> I had an interesting thought.  Remailer networks are hard to analyze,
> with messages whizzing this way and that.  But Tim pointed out that if
> you have N messages coming in to the network as a whole and N going
> out, all that zigging and zagging really can't do much better than
> N-fold confusion.

Yes, in _principle_, the theory is that Alice could be the only the
remailer in the universe, and still the "decorrelation" of incoming
and outgoing messages would be good. For example, 100 messages go in,
100 leave, and no one can make a better 1 chance in 100 chance of
matching any single input to any output. From a _legal_ point of view,
a wild guess, hence inadmissable, blah blah. (From a RICO point of
view, to change subjects, Alice might get her ass sued. Or a subpoena
of her logs, etc. All the stuff we speculate about.)

But we can go further: a single remailer node, or mix, that takes in 1
input and produces 2 outputs breaks the correlation capability as
well.

However, we all "know" that a single remailer doing this operation is
in some very basic way less "secure" (less diffusing and confusing,
less entropic) than a network of 100 remailers each taking in hundreds
of messages and outputting them to other remailers. Why--or if--this
hunch is valid needs much more thinking.

And the issues need to be carefully separated: multiple jurisdictions,
confidence/reputation with each remailer, etc. (These don't go to the
basic mathematical point raised above, but are nonetheless  part of
why we think N remailers are better than 1.)

By the way, there's a "trick" that may help to get more remailers
established. Suppose by some nefarious means a message is traced back
to one's own system, and the authorities are about to lower the boom.
Point out to them that you are yourself a remailer!

This is more than just a legalistic trick. Indeed, as a legalistic
trick it may not even work very well. Nonetheless, it helps to break
the notion that every message can be traced back to some point of
origin. By making all sites, or many sites, into remailers, this helps
make the point that a message can never be claimed to have been traced
back "all the way." There are lots of interesting issues here, and I
see some vague similarities to the ideas about "first class
objects"...in some sense, we want all nodes to be first class objects,
capable of being remailers.  (There's an even more potentially
interesting parallel to digital banks: admit the possibility of
everybody being a digital bank. No artificial distinction between
"banks" and "customers." Helps scaling. And helps legally. I'm not
saying we'll see this anytime soon, especially since we have no
examples of digital banks, period. But a good vision, I think.)

> This suggests, that IF YOU COULD TRUST IT, a single remailer would be just
> as good as a whole net.  Imagine that God offers to run a remailer.  It
> batches messages up and every few hours it shuffles all the outstanding
> messages and sends them out.  It seems to me that this remailer provides
> all the security that a whole network of remailers would.
> 
> If this idea seems valid, it suggests that the real worth of a network of
> remailers is to try to assure that there are at least some honest ones
> in your path.  It's not to add security in terms of message mixing; a
> single remailer seems to really provide all that you need.

Yes, which is why increasing N increases the chance that at least one
non-colluding remailer is being used.

A trick I have long favored--and one I actually used when we played
the manual "Remailer Game" at our first meeting--is to *USE ONE'S
SELF* as a remailer. This still admits the possibility of others being
colluders, but at least you trust yourself and get the benefits
described above.

[The alert reader will not that a spoofing attack is possible, as with
DC-Nets, in which all traffic into your node is controlled in various
ways. The graph partition work Chaum does, and others who followed him
do (Pfaltzmann, Boz, etc.), is very important here.]

Practically speaking, we need to see hundreds of remailers, in
multiple legal jurisdictions, with various policies. Messages routed
through many of these remailers, including one's own remailer, should
have very high entropies.

I still say that a formal analysis of this would make a nice project
for someone.

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."