Onion Routing for Anonymous Communications
Why is There a Need For Anonymous Routing?
Traditionally, the right to privacy of communications has been one of the natural rights in most countries of the world. For example, law usually provides that mail and telephone communications can only be monitored with express permission given by a judge.
Unfortunately, no such regulations exist for the Internet. Even more worryingly, there is a global trend towards organised logging of information pertaining to individuals' activities online.
Keeping a record of a person's activities online is a stone's throw away from infringing on the natural right of that person to privacy. Therefore good ways are needed to protect the privacy of communications against observers. It should be possible for individuals to hide their communications from "loggers". In this article we will discuss a way to do this, called Onion Routing.
Onion RoutingThe following description assumes that the onion routing network runs on top of TCP, however it can be implemented on top of other protocols.
The basic idea of onion routing can be traced back to a seminal paper on anonymous email by D. Chaum . In this paper a system for anonymous e-mail communication is presented. It introduces a network consisting of a large number of "MIX" nodes. MIX nodes serve the simple role of accepting emails encrypted with their public keys, decrypting them, and then sending them on. Each node would also perform certain timing alteration of the emails, to make it harder for a network observer to trace the path that emails take. Because a node might wait an arbitrarily long time before forwarding the incoming email this system is primarily meant for non real-time communications.
Onion Routing provides a way for two parties - a connection initiator and a connection responder - to communicate with each other anonymously. Onion Routing protects its communications against traffic analysis attacks. It makes it very hard for network observers (such as crackers, companies, and governments) to reliably learn who is talking to whom and for what purpose, by examining data packets flowing over the network. It concentrates on hiding the source and destination of a packet, rather than the content of the packet. The content of the packet could of course be encrypted using any form of crytpography prior to sending.
The system consists of a number of machines, called onion routers . Routers communicate with each other over TCP. Some routers also can serve as entry funnels, they can accept connections from the clients of the network. Some routers can server as exit funnels, they can create TCP connections leaving the network to the actual Internet services that are being accessed through the Onion Routing network. Such services can be world wide web, e-mail, peer-to-peer applications, etc.
When a client application wishes to establish an anonymous connection to a server (such that neither the server, nor the network is able to associate the connection with the client), it first of all connects to an application proxy. An application proxy is, for example, a SOCKS proxy that accepts protocol-specific connections from applications, and converts them into a generic protocol (such as a stripped down SOCKS protocol). The packets are then forwarded to an onion proxy. The onion proxy creates a route over the onion network and then constructs a special data structure, an onion. An onion is a multiply encrypted layered structure, with information about the route through the network being spread across the layers. The onion is then passed on to an entry funnel. When an entry funnel ( or any other onion router) receives an onion, it decrypts it, which reveals a layer containing information about the next hop in the route constructed by the onion proxy. This layer is then stripped off and the onion is forwarded on to this next hop. Eventually, the onion reaches an exit funnel. The decrypted packet is identical to the packet that was produced by the application proxy at the beginning of the connection. This packet will then be sent to the destination TCP host.
Onion Routing relies on using Public Key Cryptography, which allows it to encrypt layers of onions such that only intended recipients of each layer can decrypt it with their private keys. Each hop along the route then only knows about the previous hop (that it received the onion from) and the next hop (that it was instructed to forward the onion to). Plus, as the entire onion is decrypted at each router, there is no correspondence on the data layer between an onion entering a router and an onion leaving the router. This means that an outside observer who sees the onion for a specific message enter a node does not know which of the onions leaving that node corresponds to that same message. If an eavesdropper compromises a host in the network of onion routers, they will only be able to see where the onion came from on the last hop, and where it should be sent to on the next hop. The absolute source and destination of the onion are hidden.
When the recipient sends a response to a particular message, the exit funnel converts it to the generic protocol, encrypts it with its own private key, and sends it backwards along the route: i.e. to the hop from which it received the corresponding incoming onion. Each hop then similarly encrypts the response onion with its private key and sends it backwards. Eventually the onion is going to arrive at the onion proxy, which will decrypt it with the public keys of the routers along the chosen route to get the clear-text data.
A More Formal Description
We will number all the routers in the network with numbers 1..N. Onion Router s has a public key Su and a private key Sr. The public key is well-known to onion proxies. Private keys are only known to the router.
There also exists an encryption function E[key](data) and a decryption function D[key](data) with the property that data encrypted with a public key Su can be decrypted with the corresponding private key Sr, and vice versa. ie, D[Su](E[ Sr](data)) = data and D[Sr](E[Su](data)) = data. This is the basic premise of public-key cryptography.
When the first packet of a connection to be anonymised arrives at an onion proxy, the proxy constructs a random sequence of routers on the network it knows about, Zn*, e.g. <4, 3, 5>. Where the first router in the sequence is an entry funnel, and the last an exit funnel. Then, to send a packet of data to the exit funnel, it constructs an onion like so: E[4u](3's IP address, E[3u]( 5' s IP address, E[5u](data))). This onion is then given to the entry funnel (4) . The entry funnel is able to decrypt the onion with its private key, revealing 3' s IP address and a chunk of encrypted data. It forwards this chunk to 3, and the process repeats. So, to retrieve the next hop in the route, a router first has to decrypt the onion with its own private key. Because no-one else knows this private key it is impossible for someone who intercepts the onion to extract the IP address for the next hop.
Encrypting the entire onion for each hop is a big advantage, because now the onion looks completely different at each router and it is very hard to correlate it between nodes. To even further complicate traffic analysis, all onions are usually padded with random data before being sent, so that they are always of the same size.
This way, it is very easy to create a virtual onion circuit, much like virtual circuits in ATM. Simply sending an onion to a node K along a chosen path creates a virtual circuit along the path. To support these virtual circuits, an additional bit of functionality on the routers is required. Each router has a number of TCP links to other routers. Several circuits can be multiplexed over one TCP link. So, for each incoming onion, the router should be able to figure out which circuit the onion belongs to and then find out what outgoing TCP link the onion should be forwarded to.
Once the network supports virtual circuits, two important benefits are provided. First, once a virtual circuit is created, the onions sent across the circuit need not include routing information. More importantly, data can travel back across the circuit in a secure manner. Here's how it works. In the example above, a circuit <4, 3, 5> would be established. Whenever an onion belonging to this circuit enters 4, it will be able to correctly forward it to 3. Moreover, when a response message enters 5, 5 will be able to associate this piece of data with the circuit and will know that the data should be forwarded to 3. To ensure data security, 5 first encrypts the piece of data with its own private key and then sends it to 3. 3 then encrypts it with its private key and sends it to 4. 4 does the same and sends it to the originating onion proxy. The onion proxy can then recover this data by decrypting as D[4u](D[3u](D[5u]( encrypted onion))) which will yield the original data that entered 5. Thus the circuit is bi-directional.
Some Advanced Considerations
The system described above is the essential idea behind Onion Routing. Proper implementation (one of which will be discussed presently), however, must include a number of subtler details that are outside the scope of this overview. There are a large number of possible ways to attack Onion Routing systems: Denial of Service (DoS) attacks, disrupting the functioning of the system; traffic analysis attacks, decreasing the anonymity provided by the system; and many possible active attacks, where an attacker modifies the behaviour of the system (either on the TCP layer, or by controlling individual routers) to gain leverage in traffic analysis.
Making Onion Routing secure is a research area that is currently active, with many different developments and results happening all the time. We will just outline the most important, frequently recognised techniques for increasing the system anonymity and security.
Denial Of Service (DoS) Attacks
Due to the open nature of the system, it is very easy to perform DoS attacks by, for example, forcing routers to perform a large number of cryptographic operations, or depleting their bandwidth resources. The best suggested way for protecting against that is by using some form of digital currency that clients must use to "pay" for routers' services. Such currency can be, for example, cryptographic puzzles (i.e. computations that are hard to perform but easy to verify) that are presented to clients. See  for an example.
Passive Traffic Analysis
The best protection against traffic analysis lies with obscuring traffic patterns. Making sure that all onions are of the same size, that timing information on circuits is obfuscated, and possibly adding noise traffic are all valid methods of protection against traffic analysis. Pipenet provides a very good model for counteracting traffic analysis attacks, however it is an idealistic measure, not attainable in real life.
Active Traffic analysis
This is the hardest to deal with. Active attacks can include corrupting or delaying traffic between onions to reveal circuit information, as well as setting up a large number of attacker-controlled routers. There are few effective measures against these attacks, however they are quite hard to perform in reality. Again, Pipenet provides an idealistic solution, that is not attainable in real life.
Tor, An Implementation of Onion Routing
Tor is currently the most advanced implementation of Onion Routing in use today. Tor is currently deployed on the Internet.* Tor design is based on the Onion Routing design described above, however it differs in some implementation details.
First important difference that Tor provides is perfect forward secrecy, which is defined by  as: disclosure of long-term secret keying material does not compromise the secrecy of the exchanged keys from earlier runs. The simple implementation with Public Key Infrastructure (PKI) we described above is vulnerable to traffic capturing. An attacker can record data going between routers, and can then compromise the routers at a later stage (to aquire their private keys) and thus decrypt the data. However, there are certain protocols that allow two parties to establish a common "session" key, that is used to encrypt data and that is only valid for the duration of communications. Recorded communications then can not be decrypted. Tor uses Diffie-Hellman key exchange between the onion proxy and each router along the chosen route to set up a set of encryption keys that are used to encrypt layers of onions for the duration of a circuits lifetime. PKI is still used, though, to ensure that the other side of an exchange is indeed who it claims to be.
Tor also implements something called "leaky-pipe circuit topology". In the original Onion Routing protocol, only the last router in a route can act as the exit funnel. Tor changes the concept slightly, allowing any router along the route to be an exit funnel. This means that an attacker observing the end of a circuit will have a harder time figuring out where the traffic goes.
A particular problem that we have not addressed above is distributing reliable router lists. Each onion proxy needs to have a fairly reliable list of routers on the network, along with their public keys and IP addresses. Tor provides special "directory servers", which are machines that active routers register with. Onion proxies can then query directory servers and get up-to-date lists of routers on the network. Directory servers also provide communal protection against attacks that involve setting up a large number of attacker-controlled routers. Each router operator needs to be approved by the directory server operator be listed on it,
The original Onion Routing design only protected the identity of an initiator of a connection. The responder was presumed to be a TCP service with a well-known IP address. Thus the responder can be easily mapped to a person. Tor provides a service called "hidden services" which allows responders to be protected by the system. Further details on implementation of this feature can be found in .
These are the main improvements of Tor over initial Onion Routing design. Currently Tor is a very good implementation of Onion Routing, ready to be used to protect anonymity and privacy of online communications.* At time of writing, there are 60 high-speed Tor nodes online. For more information see http://www.noreply.org/tor-running-routers/.
Here we presented a protocol called Onion Routing. The purpose of Onion Routing is to protect the anonymity of a user who wants to communicate over a network. In particular, it will hide the destinations of all communications initiated by the user. Any outside observers will not be able to tell whom the user is communicating with and for how long. To achieve this goal, Onion Routing uses Public Key Encryption to put multiple layers of encryption around the original data packet, thus creating an object called an onion. This onion will follow a specific route through the network, and at each route a layer of encryption will be peeled off. Once the onion reaches its destination it will have been reduced to the original data packet. When a router decrypts the onion using its private key it will only get the address of the next router along the path. So no router will ever know the full path that is travelled by the onion. Since no outside observer will be able to follow an onion while it is travelling through the network, the communication is completely anonymous.
 D. Chaum, "Untraceable Electronic Mail, Return Addresses, and Digitial Pseudonyms", Communications of the ACM, Vol 24, No 2 (1981)
 M. Reed, P. Syverson, D. Goldschlag, "Anonymous Connections and Onion Routing",
IEEE Symposium on Security and Privacy (1997)
 W. Diffie, P. van Oorschot, M. Wiener, "Authentication and Authenticated Key Exchanges",
Designs, Codes and Cryptography 2 (1992), 107-125.
 W. Diffie and M.E. Hellman, New directions in cryptography,
IEEE Transactions on Information Theory 22 (1976), 644-654.