[Cryptography] Email and IM are ideal candidates for mix networks

Perry E. Metzger perry at piermont.com
Sun Aug 25 18:28:11 EDT 2013

[Third in an ongoing series. Disclaimer yet again: I make few claims
of the contents here being specifically original to me. Mix networks
and the like have been discussed forever, and I'm sure others have
been having similar thoughts to this of late.]

The aim of the Tor network (which, it should be noted, is an onion
network and not a mix network in the original sense) is to provide
people with reasonably responsive end to end untraceable TCP
connections. This is a big strength when dealing with going to
arbitrary existing web sites and accessing existing services.

It is also a bit of a weakness, in that it imposes fairly strict
latency limits on what people will (de facto) put up with, and it
means that the effective limit on the system is exit node
availability. Exit node operators need a strong stomach.

However, we can note that the requirements for instant messaging and
electronic mail are somewhat distinct. Latency can't be infinite, but
several seconds is totally acceptable even for IM, and longer
(sometimes much longer) is often just fine for email.

End to end virtual streams are not necessary, either, and there is no
reason that "real" mix networks, complete with slicing of traffic to
uniform lengths, variable delays, cover traffic, far more hops than
Tor can afford, etc., are all quite feasible. Compared to video
traffic, IM and Email are quite trivial loads for the network -- this
also makes longer mixing paths and cover traffic quite feasible even
where they might not have been in the days when the Cypherpunks list
was young.

There is also no need per se for "exit" nodes. All participants in a
system can be "internal" nodes, since the system isn't being used for
surfing arbitrary web sites etc. Thus, the "rare exit node" problem
is not an issue.

So, imagine that we have the situation described by part 1 (some
universal system for mapping name at domain type identifiers into keys
with reasonable trust) and part 2 (most users having some sort of
long lived $40 device attached to their home network to act as a
"home server".)

All the server nodes we postulated in part 2 could easily participate
in a mix network for exchanging instant messages and RFC-2822 style
bodies. We will presume some end to end encapsulating encryption for
these messages, and the use of standard mix network techniques for
moving the (often sliced up) bodies of these objects around the
network. The endpoints for communications are typically people's home
servers themselves (see part 2), accessed through some sort of clients
(see below).

Spam might be a terrible, terrible problem in such a network since it
could not easily be traced to a sender and thus not easily blocked,
but there's an obvious solution to that. I've been using Jabber,
Facebook and other services where all or essentially all
communications require a bi-directional decision to enable messages
for years now, and there is virtually no spam in such systems because
of it. So, require such bi-directional "friending" within our
postulated new messaging network -- authentication is handled by the
public keys of course. (If you want to contact someone you haven't
talked to before, you'll need an introduction or to use SMTP email,
which you probably need to keep around to handle your keys as
described in part 1 anyway.)

We probably don't want any sort of central service running this
network that could be easily disrupted, so identifier to IP address
information should probably be stored in some big honking DHT, signed
in the ID's key. Access to the DHT probably should happen in some
privacy preserving way, possibly through the mix network itself or a
PIR protocol.

It would be unpleasant, and probably the kiss of death to deployment,
if everyone had to abandon Mail.app and iMessage and Pidgin and
Outlook and all the other user interfaces of the world in order to use
this system. Do we need to re-write all the world's user interfaces to
handle this?


There's no real reason that your home server can't present you with a
SSL'ed web and SSL'ed IMAP interface to your RFC-2822 messages. You
run the box, and it has your keys anyway, so you can likely trust it.
Similarly, you can do a Web interface for instant messages, or, if
you have an existing Jabber client, you can run the Jabber client
protocol over SSL to your home server.

Additional notes:

There are probably lots of interesting denial of service modalities
available in such a network. Figuring out very clever ways to stop
them is probably a priority. Note that distinguishing cover traffic
from denial of service may get quite interesting indeed.

Similar techniques may be useful for voice traffic, but that has
"interesting" latency requirements, and they're hard to fulfill with a
mix network that might take arbitrary time. There's been some
interesting work by a number of people (including one of my doctoral
brothers) on this topic. It probably would require a bunch of
experimentation to get it right. On the other hand, anything might be
better than what we have now for voice traffic, which is essentially
zero privacy from the operators of most of the services.

Perry E. Metzger		perry at piermont.com

More information about the cryptography mailing list