Anonymous communication networks like the Tor network hide metadata from passive network observers. While the term ‘anonymous’ is used to mean many things, in this context we are speaking in terms of the inability of a network observer or attacker to link actions on a network with its participants [ANONTERMS]. Even users who choose to identify their actions to a remote server benefit from the location hiding properties and perhaps the hiding of other metadata.
In the designs of these networks, there are three commonly discussed anonymity properties which I will attempt to define here:
- Sender anonymity: The sender, Alice, sends a message to Bob, her identity remains hidden. Bob doesn’t know that the message is from Alice.
- Receiver anonymity: Bob receives a message from an unknown entity, and may send a reply even though he doesn’t know to whom. Alice receives the reply and can be confident that Bob will not learn her identity.
- Sender and receiver anonymity with respect to third party observers: Bob and Alice send each other messages while being certain of who will receive the messages AND while not hiding their identity to the receiver. However, third party observers will NOT be able to determine that they are even communicating with each other.
It is also interesting and useful to note that these metadata hiding properties can also be described from the perspective of clients, “mail servers” and recipients, as in [PETMAIL15].
Other kinds of metadata that are useful to hide in an anonymity network include message transmission time and size. Using traffic padding can help hide these kinds of metadata as well.
Anonymous communication networks in general have been implemented as decentralized systems. This means that a single entity, such as a company or other type of organization cannot be the sole operator of the network. Instead they rely on many separate participants, so that users do no need to depend on all of the operators for the security properties to hold. In other words, security by design instead of security by policy.
Tor and the Academic Research Community
Currently, the most notable and successful anonymous communications network to date is the Tor Network. It is volunteer operated, has many users world wide, and an excellent and usable application, the Tor Browser. The Tor Project receives relatively large amounts of funding and greatly benefits from academic research.
We strongly advocate the use of Tor and are huge fans of their excellent work. You can learn more about it here:
The Tor blog has some excellent articles including a very thoughtful post about the Tor research community:
https://blog.torproject.org/tor-heart-pets-and-privacy-research-community
We also would like to recommend “anonbib” which is a great library of the important academic papers about anonymity systems including Tor and mixnets:
https://www.freehaven.net/anonbib/
The Privacy Enhancing Technology Symposium is a great place to meet researchers who are actively designing new anonymity and privacy preserving systems:
Other Anonymous Network Projects
- https://geti2p.net/en/ – I2P is an anonymous overlay network similar but different to Tor.
- http://dedis.cs.yale.edu/dissent/ – Bryan Ford’s Dissent, a Dining Cryptographer Network project.
- https://gnunet.org/ – GnuNet Project does fund some mixnet research as well as other designs relevant to anonymous communications.
- https://panoramix-project.eu/ – The Panoramix Project is a European research project involving several universities and companies, whose mission is to support the research and development of mix networks.
Non-Goals of Anonymity Networks:
Hiding the fact that someone is utilizing an anonymity network is not an intrinsic goal of anonymity networks. That is to say: a passive network observer will be able to determine that Alice and Bob are interacting with, say, a mix network. However it’s worth noting that the Tor Project has developed pluggable transports which can be used to disguise Tor traffic. These pluggable transports are used for censorship circumvention. In addition to the work in this direction by the Tor Project, the academic community has published a large number of papers on this subject which you can find on “censorbib” :
Composition of a Mix Network
Much in the same way that the Tor network uses the Directory Authority system [TORDIRAUTH] to distribute public keys of all the Tor relays, mix network designs likewise use a Public Key Infrastructure (PKI) which can be used to distribute public key material and other information for each component mix in the network [MIXMINIONDIRAUTH].
Tor creates low latency circuits with nested encryption in order to transport client streams whereas decryption mix networks are a message oriented network that uses a nested cryptographic packet format. Currently, the Sphinx packet format is understood to be the best solution for this specialized task. [SPHINX] [SPHINXSPEC] One of the properties that the Sphinx format provides is bitwise unlinkability between input and output messages. This is quite different than sender and receiver anonymity. Instead, it refers to the impossibility of using the message contents to link incoming and outgoing messages that enter and exit a component mix.
At each hop of a mix network message’s path traversal, the message is delayed for a period of time determined by the mix strategy. This contributes to statistical interference between the component mix’s input and output messages.
Mix Strategy
David Chaum’s seminal mix network paper “Untraceable electronic mail, return addresses, and digital pseudonyms” [CHAUM81] inspired many later papers about mix networks. In this first mixnet paper Chaum introduces the threshold batch mix strategy which sends shuffled groups of messages when a treshhold number of messages are queued.
The purpose of mix strategies in general is to create statistical interference to thwart timing correlation attacks. Unlike Tor, mix networks do not need part of the network to be unobservable by adversaries nor do mix networks use route unpredictability to achieve their security properties. The mix strategy used by each component mix in the network provides the mix network with it’s location hiding security properties.
Mix strategies can be generalized and considered as a functional trade off between latency and anonymity set size. [GENMIXES] However it is clear that a large anonymity set size does not imply greater difficulty for the attacker and therefore this cannot function alone as a meaningful metric of security. [NOTANENTROPIST] n-1 attacks, where an adversary controls all but 1 of the messages in a set of mixed messages, are the most commonly discussed active attacks for mix networks [TRICKLE], however it is also possible to combine several kinds of statistical information about the current state of the mix network. The practicality and specifics of these attacks depends upon the employed mix strategy and other designs used. [SLEEPINGDOGSLIE]
Mix Topology
Unlike Tor, mixnets do not depend on route unpredictability for their anonymity properties. Therefore, classical mixnet designs feature the cascade topology which means the route does not change, all mixnet clients utilize the same route through the mix network. Cascade topology makes it easy to prove the anonymity properties of a given mixnet design for a particular mix, however, it does not scale well with respect to increasing mixnet traffic. Free route topologies scale better since traffic is evenly balanced between more nodes, however it quickly becomes intractable to prove the anonymity properties. It also turns out it provides slightly worse anonymity. The stratified or layered topology is the best compromise between free route and cascade topologies because it has good anonymity and performance scaling properties [MIXTOPO10]. In this topology each hop in the route is selected from a set of each mixes designated to be used for that hop.
Obstacles To The Adoption of Anonymous Communication Networks
The saying goes, “Anonymity loves company” which means that an anonymous communication system cannot provide high anonymity assurances if there are very few people using it. Tor has become very successful for a number of reasons and in particular, has a large number of users world wide. Any new anonymity networks will have to deal with the social problem of getting new users when their network does not yet have enough users to have a large enough anonymity set to support the anonymity assurances of the system.
A recent academic paper highlights some of the obstacles to the adoption of “secure communication tools” as being mainly:
- poor quality of service
- lack of interoperability [ADOPT17].
Tor definitely has excellent quality of service and interoperability compared to any other anonymity network that has ever been deployed. This in turn helps to promote adoption by a wide range of users which then increases the anonymity set size and gives the system stronger anonymity assurances [ANONLOVESCOMAPANY].
For mix networks, historically the poor quality of service has meant: high latency AND unreliability. Fundamentally a mix network is a lossy packet switching network on which we can build reliable protocols, however historically there hasn’t been any work on creating reliable protocols for mix networks. These highly latent and unreliable mix network designs don’t seem very appealing from a user perspective. The lack of reliability has probably hindered adoption.
Compulsion Attacks on Anonymity Networks
Another problem that affects mix networks (but not Tor) is known as the compulsion attack. In a compulsion attack, the attacker observes the network and captures a mixnet message (cryptographic packet such as a Sphinx packet). The first mix operator in the path is then compelled by the attacker to decrypt this mix message, yielding the routing information for the next hop. The attacker repeats this process until the entire path through the mix network is traced.
There are a variety of proposed defenses [COMPULS05], however the main defense for this attack is to rotate the keys used by component mixes. Mixnet designs which do not rely on volunteer mix operators can also use link layer encryption as a defense against compulsion attacks.
Recent Research and Development of Mix Networks
The Panoramix Project has funded the most recent and advanced academic mixnet paper, “The Loopix Anonymity System” [LOOPIX] which among other things explores the trade offs between decoy traffic and latency. Some of this decoy traffic is dual-use and not only functions to increase anonymity set size while lowering mix latency but also functions as a heartbeat mechanism for detecting n-1 attacks. [HEARTBEAT03]
A followup research and development project, known informally as “Katzenpost”, is based on the Loopix paper and was inspired by Tor and by Mixminion [MIXMINION]. We’ve designed a reliable network transport protocol, and a Stop and Wait ARQ protocol that uses the mix network [PANEND2END]. Thus, in theory we are solving for the historical “lack of reliability and high latency” mix network problems.
Katzenpost uses a Post-Quantum cryptographic link layer (based on the Noise framework [NOISE], [NOISEHFS]) to protect Sphinx packets from being captured by network observers/adversaries. [PANMIXWIRE] Katzenpost also uses a relatively short mix routing key rotation epoch. [PANMIXNET]
We’ve written detailed software design specifications, however we do not yet specify designs for decoy traffic at this time:
https://github.com/Katzenpost/docs
Katzenpost software is actively being developed, in various git repositories, here:
https://github.com/Katzenpost/
We’ve also had some mailing list discussions here:
https://lists.mixnetworks.org/listinfo/mixnetworks
and here:
https://moderncrypto.org/mailman/listinfo/messaging
Conclusion
Various anonymous communication network designs have differing performance and threat model trade offs. Tor is really good at being low latency, easy to use but not so good at protecting against sufficiently global adversaries. I’m imagining a world where we have a variety of anonymity networks which are complimentary to one another rather than in competition. In particular if there were various other anonymity networks, this doesn’t imply they would serve the same need and use cases as Tor. I think mixnets will not be so appropriate as Tor is in serving the needs of a general purpose anonymity network that works with a variety of applications. It might be more useful to have several custom mixnets made for their specific applications.
The two mixnet use cases I’m most interested in seeing deployed are:
- asynchronous crypto messaging system
- zcash transaction transport
Informative References
[ANONTERMS] Pfitzmann, A., Hansen, M.,
“Anonymity, Unobservability, and Pseudonymity:
A Consolidated Proposal for Terminology”, July 2000,
https://www.freehaven.net/anonbib/cache/terminology.pdf.
[PETMAIL15] Warner, B.,
“Petmail mailbox-server delivery protocol”,
Proceedings of Brian Warner’s blog, July 2015,
http://www.lothar.com/blog/53-petmail-delivery/.
[MIXMINIONDIRAUTH] Danezis, G., Dingledine, R., Mathewson, N.,
“Type III (Mixminion) Mix Directory Specification”,
December 2005, https://www.mixminion.net/dir-spec.txt.
[TORDIRAUTH] “Tor directory protocol, version 3”,
https://gitweb.torproject.org/torspec.git/tree/dir-spec.txt.
[MIXMINION] Danezis, G., Dingledine, R., Mathewsom, N.,
“Mixminion: Design of a Type III Anonymous Remailer Protocol”
https://www.mixminion.net/minion-design.pdf.
[SPHINX] Danezis, G., Goldberg, I.,
“Sphinx: A Compact and Provably Secure Mix Format”, DOI 10.1109/SP.2009.15,
May 2009, http://research.microsoft.com/en-us/um/people/gdane/papers/sphinx-eprint.pdf.
[SPHINXSPEC] Angel, Y., Danezis, G., Diaz, C., Piotrowska, A., Stainton, D.,
“Sphinx Mix Network Cryptographic Packet Format Specification”
July 2017, https://github.com/Katzenpost/docs/blob/master/specs/sphinx.rst.
[CHAUM81] Chaum, D.,
“Untraceable electronic mail, return addresses, and digital pseudonyms”,
February 1981, https://www.freehaven.net/anonbib/cache/chaum-mix.pdf.
[TRICKLE] Serjantov, A., Dingledine, R., Syverson, P.,
“From a Trickle to a Flood: Active Attacks on Several Mix Types”,
Proceedings of Information Hiding Workshop, October 2002,
https://www.freehaven.net/anonbib/cache/trickle02.pdf.
[NOTANENTROPIST] Syverson, P.,
“Why I’m not an Entropist”,
In the Proceedings of Security Protocols XVII: 17th International Workshop, April 2009,
https://www.freehaven.net/anonbib/cache/entropist.pdf.
[GENMIXES] Diaz, C., Serjantov, A.,
“Generalising Mixes”,
In the Proceedings of Privacy Enhancing Technologies workshop (PET 2003), March 2003,
https://www.freehaven.net/anonbib/cache/diaz:pet2003.ps.gz.
[SLEEPINGDOGSLIE] Syverson, P.,
“Sleeping dogs lie on a bed of onions but wake when mixed”,
Proceedings of HotPETS 2011,
https://petsymposium.org/2011/papers/hotpets11-final10Syverson.pdf.
[MIXTOPO10] Diaz, C., Murdoch, S., Troncoso, C.,
“Impact of Network Topology on Anonymity and Overhead in Low-Latency Anonymity Networks”,
PETS, July 2010,
https://www.esat.kuleuven.be/cosic/publications/article-1230.pdf.
[ANONLOVESCOMAPANY] Dingledine, R., Mathewson, N.,
“Anonymity Loves Company: Usability and the Network Effect”,
In the Proceedings of the Fifth Workshop on the Economics of Information Security (WEIS 2006), Cambridge, UK, June 2006,
https://www.freehaven.net/anonbib/cache/usability:weis2006.pdf.
[ADOPT17] Bonneau, J., Sasse, M., Abu-Salma, R., Smith, M., Naiakshina, A., Danilova, A.
“Obstacles to the Adoption of Secure Communication Tools”,
Proceedings of the 38th IEEE Symposium on Security and Privacy,
Oakland, San Jose, CA, USA, 2017
http://www.jbonneau.com/doc/ASBDNS17-IEEESP-secure_messaging_obstacles.pdf.
[PANMIXWIRE] Angel, Y.
“Panoramix Mix Network Wire Protocol Specification”, June 2017,
https://github.com/Katzenpost/docs/blob/master/specs/wire-protocol.rst.
[COMPULS05] Danezis, G., Clulow, J.,
“Compulsion Resistant Anonymous Communications”,
Proceedings of Information Hiding Workshop, June 2005,
https://www.freehaven.net/anonbib/cache/ih05-danezisclulow.pdf.
[NOISE] Perrin, T.,
“The Noise Protocol Framework”, May 2017,
https://noiseprotocol.org/noise.pdf.
[NOISEHFS] Weatherley, R.,
“Noise Extension: Hybrid Forward Secrecy”,
1draft-5, June 2017,
https://raw.githubusercontent.com/noiseprotocol/noise_spec/41d478d3dd97d77a6695f4d6cf6283e2830e9ca6/extensions/ext_hybrid_forward_secrecy.md
[PANMIXNET] Angel, Y., Danezis, G., Diaz, C., Piotrowska, A., Stainton, D.,
“Panoramix Mix Network Specification”, June 2017,
https://github.com/Katzenpost/docs/blob/master/specs/mixnet.rst.
[LOOPIX] Piotrowska, A., Hayes, J., Elahi, T., Meiser, S., Danezis, G.,
“The Loopix Anonymity System”,
USENIX, August, 2017
https://arxiv.org/pdf/1703.00536.pdf
[HEARTBEAT03] Danezis, G., Sassaman, L.,
“Heartbeat Traffic to Counter (n-1) Attacks”,
Proceedings of the Workshop on Privacy in the Electronic Society, October 2003,
https://www.freehaven.net/anonbib/cache/danezis:wpes2003.pdf.
[PANEND2END] Angel, Y., Danezis, G., Diaz, C., Piotrowska, A., Stainton, D.,
“Panoramix Mix Network End-to-end Protocol Specification”, July 2017,
https://github.com/Katzenpost/docs/blob/master/specs/end_to_end.rst.