DCchat

Dining Cryptographers Chat

Simple IRC-like chat program with strong cryptographic anonymity

Available from http://www.geocities.com/cryptosw.  See that site for
more information about DCchat and other experimental crypto software.
Feedback and questions can be left at that site, and it also provides
a place to set up planned chat sessions.

David Chaum's paper, "The Dining Cryptographers Problem:
Unconditional Sender and Recipient Untraceability", is widely
published on the net in an "unauthorized edition".  A sample link is
http://komarios.net/crypt/diningcr.htm.  The paper begins:

   Three cryptographers are sitting down to dinner at their favorite
   three-star restaurant. Their waiter informs them that arrangements
   have been made with the maitre d'hotel for the bill to be paid
   anonymously. One of the cryptographers might be paying for the dinner,
   or it might have been NSA (U.S. National Security Agency). The three
   cryptographers respect each other's right to make an anonymous payment,
   but they wonder if NSA is paying. They resolve their uncertainty
   fairly by carrying out the following protocol:

   Each cryptographer flips an unbiased coin behind his menu, between
   him and the cryptographer on his right, so that only the two of them
   can see the outcome. Each cryptographer then states aloud whether the
   two coins he can see--the one he flipped and the one his left-hand
   neighbor flipped--fell on the same side or on different sides. If one
   of the cryptographers is the payer, he states the opposite of what
   he sees. An odd number of differences uttered at the table indicates
   that a cryptographer is paying; an even number indicates that NSA
   is paying (assuming that the dinner was paid for only once). Yet if
   a cryptographer is paying, neither of the other two learns anything
   from the utterances about which cryptographer it is.

The principle can be extended to any number of participants.  Rather than
flipping coins, a stream cipher is used as a source of random bits.
And rather than sending single bits at a time, a block of data can be
collected into a packet to allow sending messages around in the form
of packets.

The DCchat program is a demonstration of a DC net, applied to a simple
chat program.  One-line messages are broadcast to all participants,
completely hiding the source of the message.  The anonymity is strong,
based on widely respected cryptographic algorithms.  See below for the
technical details.

To try it, you must have Python installed.  Versions from 1.5 through
2.1 have been tested.  Your Python must include support for the Tkinter
graphics library, and for threads.  If you need help installing Python
see http://www.python.org.

Start DCchat by running DCchat.py.  You may have to type "python
DCchat.py" on Unix, or in a DOS box on Windows.  So far I haven't
succeeded in making it work on the Mac.

The first time you run DCchat, it will pop up a window for you to move
your mouse in to seed the random number generator (RNG).  This will
write a file, randseed.bin, which will be used to seed the RNG on
subsequent runs.

Next DCchat will generate a pair of public/private keys: the host key
and a nym key.  The nym feature is not implemented yet.  The public host
key file is hostpub.hex.  This file can and should be freely published
as discussed below.  The hostpriv.hex file should be kept secret.
(DCchat does not yet use passwords to protect the private key files;
use an encrypted file system if your computer is insecure.)

DCchat then starts up the network thread which will run the Dining
Cryptographers algorithm, and a GUI for the chat program.  At this point
you might want to exit and find some other people who will run the chat
program with you.  You will need to decide on when you will chat, and
you will need to know the Internet address of at least one other member
of the group.  In addition, one person must be identified as the "root"
of the communication tree.  He is the only one who does not connect to
anyone else; everyone connects to him either directly or by connecting
to someone else who is connecting to him.  (The root person does not
get any special privileges in terms of being able to track messages or
identify who is communicating.)

At the agreed upon time, run the DCchat program again.  In the connect
box in the lower right corner, enter the address of the node you are
going to connect to.  If you are the root, click the button that says
"Be the one and only root."  If you're not the root, then as you begin
entering the address the button will change to "Connect".

The upper right box shows the host keys of all the participants in
the chat.  If you collect keys published ahead of time by others who
plan to attend and put them in a file called "dchosts.txt", then host
keys which match entries in that file will be shown in red.  This will
help you to know that you are talking to independent participants in
the chat, rather than a bunch of nodes controlled by one guy.

Once you have connected or established yourself as the root node,
you should wait until you are sure that everyone else who is going
to join the network has done so.  Once the chat itself begins then
no one else will be allowed to join.

To begin the chat, you simply send an initial message.  You may wish
to enter a nickname in the box provided.  This will be put at the
front of all of your messages.  Keep in mind that nicknames are not
authenticated and anyone can choose any nick, or change theirs at
any time.

Once everyone has sent an initial message the chat begins and you
will begin to see the other messages in the chat window.  You can
proceed to chat as usual.  At this point there is no way to know who
is originating any message.  This strong anonymity is the point of
the DCchat program.

Keep in mind that if someone leaves the chat, their anonymity will
be compromised as the disappearance of their host will coincide with
the disappearance of one of the participants in the chat.  If they
use a different nickname each time, this may not leak much information,
but if they use the same nick, or if they have a distinctive style,
people may be able to figure out what host they are coming from.
If you need to leave the chat, it is probably best to keep the program
running and just say goodbye.

Roadmap to Software

DCchat.py		- Startup program for DCchat
ChatGUI.py		- GUI for chat program
			  absent when their host is absent
TreeNetwork.py		- Handle DC network communications.  Deals with
			  connections and messaging.  Performs the
			  "broadcast-sum" operation that is the heart of
			  the DC net algorithm.
Notify.py		- Strategy module for DC net, handling events,
			  responsible for retry on collisions.
DCcrypt.py		- Do the crypto associated with DCnet, the DH
			  exchange and RC4 encryptions
LowSock.py		- Low level socket code providing a packet interface
MouseSeedWindow.py	- Seed an RNG from mouse movements in a window
Rand.py			- Random number generator built around RC4
message.py		- Parse and create the message formats used
randseed.py		- Seed the RNG from disk or popping up mouse window
			  if necessary.
ChatNoGUI.py		- Replacement for ChatGUI for unattended operation.
			  For users who want to participate in chat but
			  don't want others to notice that their nym is
Keygen.py		- Generate DSA keys for host and nym
keyload.py		- Load pre-generated keys from disk files
DH.py			- Low level crypto module for DH exchange
DSA.py			- Low level crypto module for DSA signatures
RC4.py			- Low level crypto module for RC4 encryption
npow.py			- Low level general purpose exponentiation function

Generally, DCchat is the startup module.  There are three main modules
responsible for the program: ChatGUI handles the GUI; TreeNetwork handles
the messaging; and Notify is a bridge between them that also handles
network retries when collisions occur in the network.  It is intended
that other network configurations might be supported by alternatives
to TreeNetwork.

DH, DSA and RC4 are low level crypto modules; Keygen and keyload generate
and load keys.  message contains the details of the message formats,
and LowSock provides a packet-based layer on top of the stream interface
provided by sockets.  This allows you to send a string and have the
receiver get the same string.

ChatNoGUI is a dummy replacement for ChatGUI which does not do any
chatting but connects to the network at the specified time.  Use it by
passing three arguments to DCchat: node number, time at which to connect
to network, time at which to switch to chat mode.  The times are expressed
in seconds after the program starts running.  This module does not use
a GUI and so can be run on systems that don't have Tkinter support.

DCchat by default uses port number 41251 for its connections.  If you
want people to connect to you but you can't listen on that port for
firewall reasons, you can change the MYPORT variable in TreeNetwork.py to
a value your firewall will allow.  Then when you tell people your address,
do it in the form address:port, using the port number that you used.
