From: tcmay@netcom.com (Timothy C. May)
Date: Thu, 27 Jan 94 00:12:11 PST
To: cypherpunks@toad.com
Subject: Re: Anonymous Anonymous ftp
In-Reply-To: <9401270525.AA05687@bilbo.suite.com>
Message-ID: <199401270809.AAA12139@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Jim Miller asks for an example:


> > - prepaid mailers, good for sending a packet to a
> > destination. With the final address nested insided a
> > series of encrypted packets, no mix along the way can
> > identify Bob without extensive collusion with other
> > mixes.
...
> I understand how you can do 2-way anonymous communication via message  
> pools and Penet-style systems, but I don't "get" prepaid mailers.  Could  
> you post an example showing how two people can converse anonymously via  
> prepaid mailers.

I'll use Lisp-like notation to encapsulate the sending of a packet to
a remailer "Bob." If Alice wishes to send a packet to Bob, she creates
this packet:

(Bob (more stuff))

I'm assuming encryption, which several remailers support and which all
users and all remailers should be using.

Bob gets this packet, decrypts with his private key and recovers the
"more stuff." He may discover "more stuff" contains some digital money
for his troubles, instructions on how much latency (number of
messages, for example) to use, and where to send the resulting packet.
All kinds of stuff can fit in here. But that's not the point.

If Alice wanted to send a message to Zeke, through a bunch of
remailers, she might create this initial message:

(Bob (Charles (Doris (Ed (........ (Zeke (final stuff))))....)))

Envelopes within envelopes within envelopes. (Naturally we need better
tools for doing this encapsulization, as manual efforts are too
error-prone, besides being hideously boring.)

All well and good if Alice knows the names of all the remailers she
wishes to use, their public keys, and of course the name and public
key of Zeke, to whom she wishes to send the final message. But what if
she doesn't know anything about Zeke except his public key?

(The pool approach is one approach. But for this example, to answer
Jim Miller's question, I'll look at alternatives. Not all the details
have been worked out, and certainly nobody has implemented this
"prepaid mailer," as they have with pools (e.g., BlackNet), but I
think the idea is sound.)

Zeke sells "prepaid mailers" via other anonymous methods, that is, he
wants people to be able to rapidly send him messages with mailers that
can be bought at their leisure, using slower systems like pools. (An
important point, as the time available for buying a prepaid mailer may
be much greater than that for sending the message. "Carrier pigeons"
come to mind.)

This prepaid mailer is a list of encryptions to be done (with the
possibility of instructions added in each inner message). Anyone
wishing to communicate with Zeke thus runs the script or program and
generates:

(Bill (Cindy (Darla (Earl (......(Zeke (...)))))...)

But doesn't this immediately point to "Zeke"? And where to send it?
(Remember, we're not using pools here. A pool--a publically visible
posting place--simplifies things and makes the solution more elegant,
but I'm trying to avoid the use of pools for this example.)

In each prepaid remailer, Zeke has a unique public-private key
pair...not his widely advertised public key. He shares his public key
with his prececessor in the remailer chain, Yancy, and instructs him
(pays him, of course) to make similar arrangements with _his_
predecessor, Xandor. That is, a cooperative pairwise sharing
propagates up a chain and the one-use-only public keys are then
propagated back down the chain to the end.

What results, if my thinking is correct, is a path through the web of
remailers such that any given node knows only its immediate
predecessor and its immediate successor. None of them knows the final
node (Zeke), because of this nearest neighbor effect.

So, Alice buys a prepaid remailer and applies the public keys one
after another, from Zeke to Yancy to Xandor to.... Charles and to Bob.
The public keys are known only to the nearest neighbors and so Alice
has no idea of which remailers she is actually using.

She sends the packet (Bob (Charles (..... (Xandor (Yancy (Zeke)))...)
to Bob, he opens it, sees the public key and looks up in his
back-propagated list what the next node is to be, etc.

[Confusion alert! Without pictures there is the major risk that
readers who have read this far will get hopelessly lost here...or even
earlier. What I want to emphasize is that this is not the normal
process, where a public key is closely identified with a node or site
in the remailer web. In this situation, the instructions for where to
remail _to_ are only shared pairwise, so that "Leonard" knows where to
send messages that belong to a particular prepaid mailer _to_. Not
even Zeke knows the big picture...he just _subcontracts_ the work to
his predecessor, who in turn subcontracts to...and so on recursively.]

The message rattles around this web, with each "subcontractor"
fulfilling the terms of his contract and handing on the message.
Eventually Zeke gets it and the message has been received.

Not that even Yancy does not know Zeke is the final recipient....this
is important. (Every recipient of such messages should also be a
potential remailer...I call this the "mixes as first class objects"
view.)

Will this work?

-- the recursive back- and forward propagating and mutual sharing of
keys and instructions could explode very quickly. My hunch is that it
grows quickly, but not "disastrously" (like Ackerman's function!). 

-- can anyone inside the remailer chain deduce the recipient? This
needs careful analysis.

-- as in DC-Nets (which this shares some similarities to....it may
even be equivalent to DC-Nets if looked at the right way...food for
thought), collusion between nodes can break the system. Disruption
(e.g., not sending a packet on) is also an issue. (And as in DC-Nets,
various measures can be taken to lessen the dangers....multiple
routings, reputations, ping tests, etc.)

Well, enough for now. There could be some fatal flaws, but this is the
direction I've been thinking about. Eric Messick and Hugh Daniel had
some ideas about "onions" about a year ago, but I never fully grokked
what their scheme was. If it was a scheme like this, and I have either
duplicated their thinking or was subconsciously affected by it, I
trust they'll let us all know.

Pity we can't get up and draw pictures on blackboards! This stuff
cries out for long sessions in front of the boards, and this ASCII
text just doesn't work too well.


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