DC-Net proposal, comments requested

proposal:
   Dining Cryptographer's (DC) net built on top of TCP/IP.

purpose:
   To explore the problems in implementing a useable DC net.  

description:
   The Net would allow connections to a PAD machine,  the PAD machine
   would be used to establish a "connection" across the DC-Net to
   another PAD machine which would then allow an outgoing TCP connection.
   The connection through the DC-NET would be transparent and untraceable.
   Machines that are part of the DC-NET could talk to each other 
   untraceably through the network.

discussion:
   This net would allow a user to set up an 'untraceable' connection
from one point on the internet to another.  The NET would be made
up of one or more actual DC-Nets.  

A DC-NET
   This net is broadcast in nature (data written by one machine can be
seen by all other machines on the network) but with the characteristic 
that it is impossible to tell which machine on a particular DC-Net 
wrote out the data (except if all other machines are controlled by the 
same person?).  The DC-NET itself is bit oriented.  Such a DC-network would
be the underlying layer for the packet network.  The actual DC-Network
would be made up of processes on various (or even the same,  for testing 
purposes) machines all connected together with TCP.  
 

The Packet Net
   The Packet Network would be built with the DC-Net as a base.  In order
to send useful information across the network a single node would form
data into packets.  These packets would be outputted to the network a
bit at a time.  Since the DC-Net is bit oriented it is possible for
another node to send some bits after one node has started to write out
its packets.  As a node writes out a packet it should listen to the
network for "collisions" and if a collision is detected it would 
"give up" on the current transmission and wait for some time to start
again.  Packets from one machine to another must have some sort of
addressing.  The packet could be encrypted entirely in the public
key of the destination if there is only a single DC net.  If there
are multiple DC-Nets with packet forwarding between them then there
must be some sort of plaintext address information in the packets.
The return address should *never* be in plaintext.  Probably the
data and return address of a packet would be encrypted in the public
key of the destination or in a private key shared with the destination.

Sessions
  Virtual connections can be built on top of the packet network in
the same way as they are on top of other packet networks.  Some protocol
like TCP (or even the TCP protocol) could be used.


Why should this be built on the internet?
    Writting and debugging a network of this sort on top of the internet
should be easier than writing it and implementing it from scratch.  Some
people have proposed neighborhood networks that would be used to
implement untraceable and unstoppable connections.  This is an excellent
way to develop and debug such a network.

What needs to be resolved
   Alot!  This is just something I threw together.  There are alot of
   questions.  In fact most of it is still a question.  The protocol
   of the underlying DC-Net needs to be written.  A packet layer must
   be written or adapted from current protocols.  The issues of addressing
   need to be addressed.  There are also sure to be alot of politically
   oriented questions as well.


                                  Tim N.

> A DC-NET
>    This net is broadcast in nature (data written by one machine can be
> seen by all other machines on the network) but with the characteristic 
> that it is impossible to tell which machine on a particular DC-Net 
> wrote out the data (except if all other machines are controlled by the 
> same person?).  The DC-NET itself is bit oriented.  Such a DC-network would

Actually, a single collusion between two processes could isolate a 
single non-colluding process, if that process was "between" them 
on the graph. One of the hard problems with DC Nets is how to minimize
the need for trust among the members, and how to arrange for net
formation and re-formation in a way that minimizes the ability to
deliberately or systematically partition all of the processes over
a period of time as part of a "fishing expedition" to determine the
source of some perceived-noxious output from the net.

We talked about DC Nets at the Austin cypherpunks meeting, and played
the "Dining Cryptographers Game" (complete with snazzy pieces provided
by yours truly). It was fun, but folks were a little nonplussed about 
the degree of trust required among participants.

> be the underlying layer for the packet network.  The actual DC-Network
> would be made up of processes on various (or even the same,  for testing 
> purposes) machines all connected together with TCP.  
>  
> 
> The Packet Net
>    The Packet Network would be built with the DC-Net as a base.  In order
> to send useful information across the network a single node would form
> data into packets.  These packets would be outputted to the network a
> bit at a time.  Since the DC-Net is bit oriented it is possible for

I've been looking at this problem as well, Tim, and it doesn't seem to 
me that you have to output a bit at a time. In fact, the DC net machines
should probably be operating on blocks that fit nicely into single IP
packets. Just consider the blocks to be the result of N coin tosses.

> another node to send some bits after one node has started to write out
> its packets.  As a node writes out a packet it should listen to the
> network for "collisions" and if a collision is detected it would 
> "give up" on the current transmission and wait for some time to start
> again.  Packets from one machine to another must have some sort of
> addressing.  The packet could be encrypted entirely in the public
> key of the destination if there is only a single DC net.  If there
> are multiple DC-Nets with packet forwarding between them then there
> must be some sort of plaintext address information in the packets.
> The return address should *never* be in plaintext.  Probably the
> data and return address of a packet would be encrypted in the public
> key of the destination or in a private key shared with the destination.
> 
> Sessions
>   Virtual connections can be built on top of the packet network in
> the same way as they are on top of other packet networks.  Some protocol
> like TCP (or even the TCP protocol) could be used.
> 
> 
> Why should this be built on the internet?
>     Writting and debugging a network of this sort on top of the internet
> should be easier than writing it and implementing it from scratch.  Some
> people have proposed neighborhood networks that would be used to
> implement untraceable and unstoppable connections.  This is an excellent
> way to develop and debug such a network.
> 
> What needs to be resolved
>    Alot!  This is just something I threw together.  There are alot of
>    questions.  In fact most of it is still a question.  The protocol
>    of the underlying DC-Net needs to be written.  A packet layer must
>    be written or adapted from current protocols.  The issues of addressing
>    need to be addressed.  There are also sure to be alot of politically
>    oriented questions as well.
> 

One head scratcher I've been considering is whether it would be better
to simulate a token-passing scheme, or to have comparisons broadcast
to all participants. Since in a broadcast scheme, the number of packets
per round generated is n^2, it seems prima facie that token passing would
be faster (it would certainly consume a much smaller % of the net's total
bandwidth), but actually for reasonable n, the accumulated latencies from
a few slow links could very well make the token passing slower. 

Also, I have thought of some ways of dealing with "slacker" processes
or folks who suddenly drop out that work better with a broadcast approach,
but there's probably a way to deal with them in the token-based scheme.

Another issue is whether or not your processes need to elect a "lead" process 
to handle synchronization issues and serve as an arbiter in net formation
and re-formation.


-- 
----------------                                             /\ 
Douglas Barnes            cman@illuminati.io.com            /  \ 
Chief Wizard         (512) 448-8950 (d), 447-7866 (v)      / () \
Illuminati Online          metaverse.io.com 7777          /______\

Doug Barnes writes about Tim Newsham's work on DC-Nets:

> I've been looking at this problem as well, Tim, and it doesn't seem to 
> me that you have to output a bit at a time. In fact, the DC net machines
> should probably be operating on blocks that fit nicely into single IP
> packets. Just consider the blocks to be the result of N coin tosses.

Exactly. The "coin tosses" can be arranged far in advance and shared
on CD-ROM (for example) or whatever's convenient. Chaum, Bos,
Pfaltzman (I think...I don't have my paper handy) consider even using
ciphers to generate the tosses, though then the DC-Net ceases to be
information theoretically secure and is no more secure than the cipher
itself.

To see this in a simple way, forget about the "classical" DC-Net
situation of n participants in a ring or other graph. Instead,
consider only 2 participants, Alice and Bob.

Alice and Bob share a sequence of random numbers, essentially a
one-time pad. The sequence they share is, as an example:

1 0 1 1 0 1 1 0 0 0 1 0 1 0 .....

As a pair they can send 1s or 0s by the one of them sending the
message XORing his message with the sequence and then both of them
output the sequence.

Let us imagine Bob wished to send the "message": 1 1 0 0 1 1 0 1 0 1
1...

Alice: 1 0 1 1 0 1 1 0 0 0 1 0 1 0 .....

Bob:   1 1 0 0 1 1 0 1 0 1 1 ....   (his message, before he sends it)

XOR:   0 1 1 1 1 0 1 1 0 1 0..... (this is what Bob sends out)

The outside world sees two different bit streams and recovers the
message by XORing the streams put out by Alice and Bob:

XOR:   1 1 0 0 1 1 0 1 0 1 1....

Thus, Bob's "message" has been sent out, but since the outside world
does not the original one time pad Alice and Bob were using, it cannot
know which of Bob or Alice was sending the pad and which was "lying,"
that is, XORing the message with the pad and outputting that.

Of course, Alice knows it was Bob who sent the message (becuase she
knows she didn't). Extending the protocol to the ring
Alice-Bob-Charles in the classical DC-Net way completes the picture.

But you can see how precomputed, preexchanged pads--or a very secure
cipher (a good pseudorandom number generator, really)--would be used
in practice to eliminate coin tosses, real or simulated. No DC-Nets
would do things one bit a time, that I can see.

> Also, I have thought of some ways of dealing with "slacker" processes
> or folks who suddenly drop out that work better with a broadcast approach,
> but there's probably a way to deal with them in the token-based scheme.

"Disruption" by sending of spurious messages, to deny service by
flooding the DC-net, seems to be the biggest problem, and Chaum and
Bos devote most of their papers to schemes for handling this.

I have some of these papers--let me know if you don' yet have them,
especially the hard to find Jurgen Bos Ph.D. thesis.

Great to see work on DC-Nets again! Yanek Martinson, who I've not seen
on the list in many months, was working on an implementation, and at
today's Cypherpunks meeting, Strick expressed interest in implementing
DC-nets in his TCL-based crypto toolkit.


--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^756839 | Public Key: PGP and MailSafe available.
Note: I put time and money into writing this posting. I hope you enjoy it.

>Doug Barnes writes about Tim Newsham's work on DC-Nets:

>> I've been looking at this problem as well, Tim, and it doesn't seem to 
>> me that you have to output a bit at a time. 

Indeed, the DC-net protocol operates in any abelian (commutative)
group, such as, say, integers mod 2^56 (the size of a ping packet
body).  The modulus need not be a power of two, but there's little
advantage if it's not.  The vectors in a linear code might also be
appropriate for certain side effects.

>[... some people] consider even using
>ciphers to generate the tosses, though then the DC-Net ceases to be
>information theoretically secure and is no more secure than the cipher
>itself.

In practice, this is a small problem.  Since many of the messages that
a deployed DC-net sends out will be text encrypted for some particular
destination, one needs no greater computational security than that of
the cipher used to encode the message.

There are several random number generators provably as secure as the
hard number-theoretic problems used for public key cryptography.  The
problems include quadratic residuosity, factoring, and discrete log.

Eric

cman@IO.COM (Douglas Barnes) writes:
> [dc nets stuff]
> 
> One head scratcher I've been considering is whether it would be better
> to simulate a token-passing scheme, or to have comparisons broadcast
> to all participants. [...]

Doug has already heard a lot of this over dinner discussions we have had on
dc nets and networking, but here are a few more things I have been thinking
about in regards to this.

The idea we hashed around in the token passing realm was that members of
the net would begin by knowing only thier partners (I will assume people
are being honest in the network for the moment...)  Each person will pass
packets to the left, the person they share thier data with in the dc setup
(i.e. the person whose menu they look behind and whose coin they compare
thier toss with.)  The "packets" will have two sizes, the small one for
token negotiation and a large one for data transmission.  Token-sized
packets are passed until someone suceeds in transmitting the "i speak"
token, then a data packet, and then token negotiation begins again.

Everyone prepares two random numbers, one for the data sharing that is part
of the dc net and another to use in the communications ring.  When people
have checked thier neighbors and are ready to transmit, they send thier
second random number (and a random signed token so they know when they see
thier token come back to them) to the person on thier left.  When a packet
is recieved, each number is incremented or not for the "same/different"
message and passed to the next member.  When your token finally gets back
to you it is possible to check for the message sent by the net, you know
your original random number and the number of passes necessary for you to
get your token back tell you how many people are participating.

Doug and I thought that perhaps if the broadcast signal was something like
"1111(rand 8 bits)1111" and people backed down when they sensed collision,
so that unless the 16 bits ended with 1111 people would know there was no
token in that round (0 is the default message, when people colliding stop
trying to send the negotiotion falls to zero for that round) and they would
try again.  Eventually someone would be able to transmit the sequence and
because the number in the middle is random only they would know that they
have the send token.  Then people communicate for the preset length of the
data packet and begin negotiating for the token again.

As far as breaking up and reforming the network I am still looking for
ideas, but have been reading some old crypto proceedings and I am going to
play around with some ideas and see if Chaum's blind signature stuff
coupled with a ZNP for proving identity might work (it happens to be the
article I was reading on the way over to work and it has gotten me
thinking...)

> Also, I have thought of some ways of dealing with "slacker" processes
> or folks who suddenly drop out that work better with a broadcast approach,
> but there's probably a way to deal with them in the token-based scheme.

Yes and no.  The internet is not a connection-oriented medium and it is
impossible to know whether or not a particular packet made it through.
"Broadcasting" is also tricky for the same reason.  The designers of the
net have worked out several schemes for getting around these problems, it
makes no sense not to lift a few good ideas for this...  


jim