Re: Latency vs. Reordering (Was: Remailer ideas (Was: Re: Latency vs. Reordering))

In message <9408051716.AA14773@ah.com> Eric Hughes writes:

> Back to the start, I guess.
> 
> >   Specifically cryptographic elements are easily added to the system
> >       *	packets can be delayed for random intervals
> 
> Let me repeat:
> 
> REORDERING IS OF PRIMARY IMPORTANCE FOR REMAILER SECURITY.
> 
> ADDING LATENCY IS NOT.

No need to shout, we heard you the first time.	;-)

In a system that is carrying continuous traffic, random packet delay
is functionally identical to packet reordering.

If messages are fragmented, random delays on sending packets out is
functionally identical to reordering.

More importantly, RemailerNet as described defeats traffic analysis by
more significant techniques than reordering.  Reordering is a weak
technique.  The introduction of noise, 'MIRV'ing of messages,
fragmentation of messages, random choice of packet routes, and
encyphering of all traffic are stronger techniques.

--
Jim Dixon

-- 
+-----------------------------------+--------------------------------------+
|  Jim Dixon<jdd@aiki.demon.co.uk>  |	    Compuserve: 100114,1027	   |
|AIKI Parallel Systems Ltd + parallel processing hardware & software design|
|	     voice +44 272 291 316  | fax +44 272 272 015		   |
+-----------------------------------+--------------------------------------+

In a system that is carrying continuous traffic, random packet delay
   is functionally identical to packet reordering.

OK.  Prove it.  Here are some difficulties I expect you'll find along
the way.

First, "continuous traffic" is the wrong assumption; some sort of
multiple Poisson distribution for arrival times is.  This is by no
means a hypothetical.  The backoff algorithms for TCP had to be
developed because packet streams are not continuous, but bursty.
There is such a thing as too many packets arriving at a router
simultaneously.  Routers don't swap packets to disk when they run out
of RAM; they drop them.  So given any relation between arrival
interval, processing time, and machine capacity, there some
_percentage_ of the time that the router is going to overflow exactly
because the traffic is not continuous.

Second, the beginnings and endings of operation are special.  The idea
of "stochastic deconvolution" hits me immediately, throwing out
completely any reasoning based only on steady state assumptions.

Third, these two effects interfere with each other, as there are
bursts of silence in Poisson arrival times which will tend to reset
the deconvolution.

Fourth, the problem is incompletely specified, since the distribution
of random added latencies is not made specific.  If I assume a flat
distribution over a given number of message intervals, that's not the
same as assuming a geometrically decreasing distribution, or some
other distribution.

I'd guess there are more.

   If messages are fragmented, random delays on sending packets out is
   functionally identical to reordering.

This is false; a system that concentrates on reordering has provably
better average latency that one based only on adding latencies.
Consider the following.  If I send out a message sometime between two
messages, I've acheived no more reordering (the significant thing,
remember) than if I sent out that same message immediately after the
arrival of the first of the two bracketing messages.

So I can take _any_ latency-adding system and reduce its average
latency with minimal effect on reordering by the following
modification.  When a message comes it, each message in the queue is
tagged to go out at some time relative to present.  For each of these
messages, I can calculate the probability that no other incoming
message will arrive before a particular outgoing time.  Pick some
probability bound close to 1, and send out all messages with
probability greater than the cutoff _now_, before waiting for their
time to be up.

The decrease in reordering can be normalized to zero by lengthening
the time scale of the added latencies.  You'll then find that the
modified system shows lower latency.

And that's only the first inequivalency.

Latency-adding systems are less efficient at memory usage than
reordering systems.  Reordering systems can get pretty close to 100%
use, since the queue can be kept full, as in Hal's threshold sending
scheme.  The random delays can't have full usage, because there's an
maximum to memory; it can't be borrowed like money when you
temporarily need more of it.  The analysis has similarities to
gambler's ruin.

Anyone else care to point out more inequivalencies?

   More importantly, RemailerNet as described defeats traffic analysis by
   more significant techniques than reordering.  Reordering is a weak
   technique.  

WHAT??

Anyone else listening to this: I believe the above quoted two
sentences to be distilled snake oil.

   The introduction of noise, 'MIRV'ing of messages,
   fragmentation of messages, random choice of packet routes, and
   encyphering of all traffic are stronger techniques.

Encyphering is necessary.  Reordering of quanta is necessary.

"MIRV" messages may actually decrease security; multiple routes may
decrease security; fragmentation may decrease security.  Noise
messages may not be resource effective.  All the above claims require
some justification, and I have seen nothing robust yet.

Eric

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.

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.

Hal

This suggests, that IF YOU COULD TRUST IT, a single remailer would be just
   as good as a whole net.  

If you could trust it and if it were large enough.  There's scaling
reasons to use multiple remailers as well.

Consider a network of mailers running on a private network with link
encryptors.  Whenever you join two nodes with a full-time link
encryptor you remove the information about message arrival and
departure, which is to say that you remove all the remaining
information not already removed by encryption and reordering.

In other words, two remailers (physical) hooked up with link
encryptors are almost the _same_ remailer for purposes of traffic
analysis, and almost only because of the link latency and relative
bandwidth.  Likewise, multiple remailers hooked up with link
encryptors all collapse to the same node for traffic analysis.  Open
links between two remailers which are connected otherwise by a path of
encrypted links turn into an edge from the collapsed remailer set back
onto itself.

Simulating any of the salient features of a link encryptor over the
Internet is an interesting exercise, particularly in regard to price
negotiation with your service provider.

Eric

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