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
participants (5)
-
cman＠IO.COM -
hughes＠ah.com -
Jim McCoy -
tcmay＠netcom.com -
Timothy Newsham