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

The problem of designing a reliable and trusted remailer network is
a generalization of the problem of constructing a reliable Internet and
so many of the solutions can be the same.  The structure of the
Internet has been gone over and over again for twenty years or so
and is probably optimal.

This suggests that
   *	all packets should be acknowledged
   *	messages should be broken down into packets which are routed
	independently
   *	users should communicate with trusted gateways
   *	users should be accessible through a hierarchy of logical names
	which includes the gateway name
   *	gateways should be known to users only through their logical
	names
   *	the gateways should frequently exchange routing information
   *	that routing information should have an expiry date
   *	gateway operators can choose who they announce routing
	information to and accept routing information from
   *	users may have accounts with gateways and be charged for
	gateway usage
    *	gateway operators can settle accounts between each other
	periodically
    *	system software should be obtained [only] from trusted sites;
	to make things simpler, it should be possible to distribute
	bootstrap diskettes that allowed the bulk of the software
	to be downloaded or updated over the net without being
	compromised

Specifically cryptographic elements are easily added to the system
    *	all inter-gateway traffic should be encoded
    *	packets can be delayed for random intervals
    *	routing of packets can be somewhat stochastic; that is, you
	don't generally packets by the quickest route, and the
	choice of forwarding gateway is not 100% predicatable,
	given the destination gateway
    *	packets can be fragmented and padded with noise at random
    *	noise packets can be added at random
    *	route selection, packet fragmentation, and noise generation
	can be continuously adjusted to defeat traffic analysis

The following suggestions raised in recent postings are included
in this scheme:
    *	cjl's MIRV capability (except that it is supplied by the
	system and not the user)
    *	Jidan's noise injection
    *	Rochkind's stability-from-being-paid and web-of-trust notions
    *	Markowitz's automated contacts between mailers
    *	a form of digital postage
    *	Rochkind's pinging

The following are very easily supported by the scheme:
    *	a form of digital cash (the gateway operator would run a tab
	for users, like a credit card company)
    *	digital signatures
    *	message transfer via custom Internet protocols as well as
	via the email system
    *	users could specify the degree of confidentiality required
	and the system would use stronger encryption, increase
	chaff (anti-traffic analysis measures), and restrict use to
	more trusted gateways as required

Where email is used to transfer messages, the format used should be
a subset of that specified in the SMTP RFCs.  Restricting the structure
of the headers would simplify the remailer software at little cost
to the user.

The use of alt.x groups to exchange gateway information does not seem
to add anything to this system; in fact it would seem to make it easier
to spoof the system.

There could be multiple remailer nets, some commercial (paid for)
and some free.	The commercial networks could choose to exchange
traffic with the free networks at no charge.

Commercial remailers would probably be very concerned with legal
issues, both criminal (pornography, etc) and non-criminal (copyright
violations).

--
Jim Dixon

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.

And I don't want to hear any excuses that you can say latency and mean
reordering, because that's self-delusion.  Not only is it false, but
misleading.  Reordering is necessary for security, and latency is a
by-product.  You don't get security by adding by-products.

Eric

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.
> 
> And I don't want to hear any excuses that you can say latency and mean
> reordering, because that's self-delusion.  Not only is it false, but
> misleading.  Reordering is necessary for security, and latency is a
> by-product.  You don't get security by adding by-products.

I don't understand this. My remailer (snakeoil@klaus.com.edy) gets
about 3 or 4 messages a day through it, and I'm very careful to add a
latency of 1 hour and sometimes 2 hours...surely this is more than
enough!

My friend Pandit says he gets 20 messages an hour, and he uses a
latency of 1 hour, so why can't I?

(Oh, you mean the key is to _randomly reorder_ the messages, not just
delay them by an hour when the average number of messages in an hour
is less than 1 anyway? Oh, now I see. Never mind!)

--Tim May, who is as tired as Eric is of hearing the hoary old
chestnuts about 'random delays,' this without regard to calculating
the amount of reordering. Part of the problem, I'll grant folks, is
that there are few if any papers showing calcultions on this--Chaum's
1981 paper only makes brief mention of reordering effects. I don't
think it's a _hard_ calculation, and I've made some estimates of the
"diffusion and confusion" deriving from a mix of 10 nodes, each with a
diffusivity of 10...with equal packet sizes, and no other identifying
clues, a simple analysis suggests 10^10 routes that could be followed.
However, if only 10 messages entered the mix labyrinth (my
nontechnical term!) and 10 left it, then regardless of the 10^10
routings, a monitor would still "know" that one of the 10 leaving was
the targetted message. On the other hand, he would have no certainty
as to which one. A condition true even if 2 messages entered a node
and 2 left it after being mixed. (It is this latter area, about
degrees of uncertaintly, that needs a more sophisticate combinatorial
anylysis. Again, not a big project...maybe a nice little Masters
thesis for someone to do, to extend Chaum's analysis a bit.)


P.S. I presume the list is back up again? 


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

Jim Dixon analogizes between the Internet and remailer networks.  The
analogy has some merit, but yet breaks down badly with the very first
point:

      *	all packets should be acknowledged

This is not the way the Internet works.  IP, Internet Protocol, is
unreliable.  TCP, the reliable stream protocol, does not acknowledge
individual packets but rather advancement along a sequence.  The
lesson is that reliable delivery should be built on top of unreliable
delivery.

Here the analogy breaks down on technical grounds.  With TCP, the
destination knows the source, yet in a remailer network this may not
be the case.  A good first cut, though, would be to forgo reliable
delivery for remailer-created pseudonymity and work out a reliability
mechanism for regular correspondents.  In this case the source _is_
known, it's just that it's not shown on the outside of the message.

Further, in email, there's currently no notion of a connection.  Email
message are much more like datagrams than bit streams.  In order to do
reliable delivery, there would have to be persistent state information
on each side of the communication.  If I send a message for the first
time to a party and there's no reply, I cannot conclude whether the
message was not delivered or whether the message was delivered and not
answered.

Connection-oriented email would be much more complicated than the
current systems.  It is, perhaps, time for email to become more
complex.  

      *	messages should be broken down into packets which are routed
	   independently

Length quantization is necessary for security in the face of total
network monitoring.  Multiple quanta may be warranted in the case of
high volume, which is certainly not the case right now.  So this point
holds.

      *	users should communicate with trusted gateways

This point is only half true, because the analogy only subsumes one
kind of trust.  For remailers there is both trust in delivery and
trust in silence, the destruction of the message and information about
it.  On the Internet the only trust required is delivery; there is not
a desiderata in the design (although it's certainly in some people's
minds) that packet monitoring _not_ be possible.

      *	the gateways should frequently exchange routing information

Again, this works for trust in delivery but not for trust in silence.

Eric

hughes@ah.com (Eric Hughes) writes:

>Further, in email, there's currently no notion of a connection.  Email
>message are much more like datagrams than bit streams.  In order to do
>reliable delivery, there would have to be persistent state information
>on each side of the communication.  If I send a message for the first
>time to a party and there's no reply, I cannot conclude whether the
>message was not delivered or whether the message was delivered and not
>answered.

>Connection-oriented email would be much more complicated than the
>current systems.  It is, perhaps, time for email to become more
>complex.  

I would really like to see some kind of system for reliable email.  I'm
surprised that it doesn't exist yet.  How many times have we said,
"You didn't get my email?  I'll resend it."  What are computers for, after
all?  Automating repetitive tasks, classically.  This is a perfect appli-
cation.  A copy of outgoing email could be kept, acknowledgements received
on receipt, and the email deleted or re-transmitted as needed.  Serial
numbers would distinguish retransmissions so that redundant resendings
(where the packets "crossed in the mail", so to speak) would be dropped.
All this was designed in an afternoon in Xmodem.  It's conceptually easy.
The hard part is getting a standard and getting people to build it into
their Mail User Agents.

Then, once we had this, we could do another layer for crypto protocols.
Lots of protocols go in stages.  A sends X to B, receives f(X), sends
g(Y,f(X)), etc.  To do this in email would be impossibly cumbersome now,
but the kind of mechanism used for reliable email could be extended to
support these kinds of "stateful" protocols.

As one obvious need for reliable email, consider the transmission of
Chaum-style digital cash.  You don't want to erase your copy until you
are sure the other guy has received it, otherwise your money is permanently
gone (just like when you send cash in postal mail and it is stolen).  But
keeping track of which cash you have sent to which people, who has gotten
theirs, which needs to be re-sent, etc., is painful.  A simple reliable
email method would solve a big part of this problem.

Hal

> >If I send a message for the first
> >time to a party and there's no reply, I cannot conclude whether the
> >message was not delivered or whether the message was delivered and not
> >answered.

Given a connectionless network absolute delivery is impossible (well, not
completely, but just about...)

> I would really like to see some kind of system for reliable email.  I'm
> surprised that it doesn't exist yet.

What makes you think that it doesn't?  You should check out Enabled Mail (I
think that is the name of it...); it is a set of MIME extensions that would
use a "safe" subset of Tcl to create triggers that can be set for message
receipt/delivery or for when the message is read.  I used to have a pointer
to the proposed system, but you should be able to find it by poking around
the comp.lang.tcl FAQ or asking over there.

jim

Given a connectionless network absolute delivery is impossible (well, not
   completely, but just about...)

Here is a theme I'm going to mention a few times today: the complexity
class of probabilistic algorithms is the one that matters most for
practical applications.

Which is to say, that when you have a partially unreliable
connectionless network, you can't, can not, can never _assure_
delivery.  You can, however, set up the protocols so that the
assurance in delivery is arbitrarily close to probability one, even
though it can't ever actually reach it.

Here's the fallacy which is common, that something which is
probabilistically bounded but is not deterministically bounded is
somehow flawed.

Or, rather, you can trust expected values.

Hal's random-send spool has an expected value of latency which is
approximately the size of the spool but has no deterministic upper
bound for that latency.  Fine.  Great.  No problem.  There should be
zero hesitation here, because the expected value -- the probabilistic
average -- is what you want.

When you start off with probabilistic assumptions about the underlying
reliability of the network, the best you can get is probabilistic
answers.  Even if the network components are deterministic, you still
get probabilistic results.  Adding probabilistic components also gives
you probabilistic results.  So what's the bid deal?

The hesitation to accept a probabilistic measurement is still
all-too-frequent.  I will refrain from commenting on why I think that
is, and merely admonish folks not to pull their punches and bewail a
probabilistic result about device behavior.

Eric

Date: Fri, 5 Aug 1994 22:11:59 -0700
    From: Hal <hfinney@shell.portal.com>
    To: cypherpunks@toad.com
    Subject: Re: Remailer ideas
    References: <9408051709.AA14763@ah.com>
    
    . . .

    A copy of outgoing email could be kept, acknowledgements received
    on receipt, and the email deleted or re-transmitted as needed.  Serial
    numbers would distinguish retransmissions so that redundant resendings
    (where the packets "crossed in the mail", so to speak) would be dropped.
    All this was designed in an afternoon in Xmodem.  It's conceptually easy.
    The hard part is getting a standard and getting people to build it into
    their Mail User Agents.

I think that many of the simple cases are conceptually easy, but even
slightly complicated ones are non-trivial.  For example, I tend to
include Return-Receipt-To: lines in my messages, so I get a bunch of
responses.  Interpreting those responses and deciding what action
would be appropriate raises some interesting questions, not the least
of which is ``What does it mean for a message to be successfully
delivered to the cypherpunks list?''.  Just as an example how easily
the issue can become confused, I'll throw in, ``How is the meaning of
successful delivery affected by changes in list membership during
transmission?''  Considering that some of the addresses to which
cypherpunks is distributed are also distribution lists, any list
related problems are multiplied.

Practical issues make this whole thing more difficult.  The ``getting
people to build it into their Mail User Agents'' part in particular.
The idea of a Return-Receipt-To: field has been around for a while,
but the semantics have never been pinned down.  Some mailer daemons
generate replies meaning that the bits were delivered.  Some readers
(MUAs?) generate replies based on end-user actions.

This thread of discussion got me thinking about a really sick thought
though:  Using email messages to represent UDP packets.

			Rick

Rick Busdiecker <rfb@lehman.com> writes:

>I think that many of the simple cases are conceptually easy, but even
>slightly complicated ones are non-trivial.  For example, I tend to
>include Return-Receipt-To: lines in my messages, so I get a bunch of
>responses.  Interpreting those responses and deciding what action
>would be appropriate raises some interesting questions, not the least
>of which is ``What does it mean for a message to be successfully
>delivered to the cypherpunks list?''.  Just as an example how easily
>the issue can become confused, I'll throw in, ``How is the meaning of
>successful delivery affected by changes in list membership during
>transmission?''  Considering that some of the addresses to which
>cypherpunks is distributed are also distribution lists, any list
>related problems are multiplied.
I can see that there may be difficult cases, but I still think that
there would be real utility in the ability to specify that a particular
piece ofmail should be re-transmitted if it does not get delivered
to the destination machine within a certain period of time.  As I said,
this would help with the implementation of cryptographic protocols that
worked via email, not to mention the many other applications.



>Practical issues make this whole thing more difficult.  The ``getting
>people to build it into their Mail User Agents'' part in particular.
>The idea of a Return-Receipt-To: field has been around for a while,
>but the semantics have never been pinned down.  Some mailer daemons
>generate replies meaning that the bits were delivered.  Some readers
>(MUAs?) generate replies based on end-user actions.

That's one reason I like the "enabledmail" approach.  All we have to do
is persuade everyone to run a system which allows anyone on the network
to get your computer to run an arbitrary program for them.  Then everything
will be fine.  One nice thing is that enabledmail scripts can
trigger either on delivery to the dest machine, or on being read by the
recipient.  This gives even more flexibility in how you want to define
a "received" message.

Hal

Date: Mon, 8 Aug 1994 20:15:36 -0700
    From: Hal <hfinney@shell.portal.com>
    
    . . . I still think that there would be real utility in the
    ability to specify that a particular piece ofmail should be
    re-transmitted if it does not get delivered to the destination
    machine within a certain period of time.

Agreed.
    
    That's one reason I like the "enabledmail" approach.  All we have to do
    is persuade everyone . . . .

I also agree that this approach is desireable.  My contention is not
that these things are undesireable, but rather that they are not as
trivial as was originally suggested.

			Rick

On M/N reordering schemes: A relatively simple way to avoid
the unlucky message sitting in the queue problem would be to store a
timestamped, ordered list of messages waiting to go.  When a new
message comes in, one is randomly selected to be sent out.  The list
is then examined to find messages older than H hours.  The entries for
those messages are then duplicated & reinserted into the list, thus
increasing the chances that a message thats been sitting around for a
while will be randomly selected. (As there are multiple pointers to
it, and only single pointers to new messages.)


Adam


-- 
Adam Shostack 				       adam@bwh.harvard.edu

Politics.  From the greek "poly," meaning many, and ticks, a small,
annoying bloodsucker.

On M/N reordering schemes: A relatively simple way to avoid
   the unlucky message sitting in the queue problem would be to store a
   timestamped, ordered list of messages waiting to go.

The key word in the above sentence is the word "unlucky".  When I
formalize the word unlucky, I get "expected value is arbitrarily close
to zero".  Therefore, I completely ignore this situation, because it
just doesn't happen often enough to worry about.

If you have a higher level protocol which corrects errors, then
staying in a mix too long is just another cause of failure.  It should
be tallied up with the rest of the causes of failure and then, once
its contribution to unreliability has been established, ignored.

The probabilistic reasoning which says that "the message will get out
with the following distribution of latencies" is perfectly fine, and
as long as the systemic consequences of late messages have a fixed
upper bound, the total effect of delayed messages does also.  Estimate
the damage, and if it's workable just don't worry about it.

And when I claim that some folks just empathize too much with that
poor little datagram who went on an incredible journey through lots of
out-of-the-way place to finally come home, well, I'm exactly half
joking.

Eric

Jim Dixon writes:

>Commercial remailers would probably be very concerned with legal
>issues, both criminal (pornography, etc) and non-criminal (copyright
>violations).

It would seem that remailers shouldn't be anymore accountable for
passing on illicit pornography than the postal services are today.

??

>--
>Jim Dixon

Spencer Mullen writes:

> It would seem that remailers shouldn't be anymore accountable for
> passing on illicit pornography than the postal services are today.
> 
> ??

I'll take the "??" as an invitation for comment.

Package delivery services like UPS and Federal Express *do* have
immunity from prosecution based on what they carry, but this is in
exchange for allowing inspection of packages under specified
circumstances. Thus, if the DEA suspects a package contains cocaine,
it can be inspected, and the shipper will most likely cooperate in
resealing the package and continuing the shipment.

This is part of "common carrier" status. (I don't have any cites for
this, as I'm not a lawyer. But this topic has come up many times on
the Net, and the consensus of knowledgeable people is that
"participation in legitimate law enforcement investigations" is part
and parcel, so to speak, of being a common carrier.)

Caveat: I'm not claiming any of this is as it should be, etc. Just
stating facts as I understand them.

The implications for crypto are unknown, but between the Digital
Telephony Bill mandating easy tapping access and the various key
escrow schemes, I expect that a remailer network which cannot possibly
cooperate may face legal problems.

(One scenario: Digital Telephony III, in 1997, mandates that all mail
sites must keep records of incoming and outgoing packets, and where
they mailed them to, and must keep explicit mapping between incoming
and outgoing packets. These records must be available for inspection,
with a $10,000 a day fine fro noncompliance. With such a mandate, the
authorities could go to each and every remailer they find and demand
these records. A wrinkle: what about *offshore* remailers? Ah, things
then get very interesting.)

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