Onion routing

Onion routing is a technique for anonymous communication over a computer network. Messages are repeatedly encrypted and then sent through several network nodes called onion routers. Each onion router removes a layer of encryption to uncover routing instructions, and sends the message to the next router where this is repeated. This prevents these intermediary nodes from knowing the origin, destination, and contents of the message.

Onion routing was developed by Michael G. Reed, Paul F. Syverson, and David M. Goldschlag, and patented by the United States Navy in US Patent No. 6266704 (1998). As of 2009, Tor is the predominant technology that employs onion routing.

Capabilities

The idea of onion routing (OR) is to protect the privacy of the sender and recipient of a message, while also providing protection for message content as it traverses a network.

Onion routing accomplishes this according to the principle of Chaum's mix cascades: messages travel from source to destination via a sequence of proxies ("onion routers"), which re-route messages in an unpredictable path. To prevent an adversary from eavesdropping on message content, messages are encrypted between routers. The advantage of onion routing (and mix cascades in general) is that it is not necessary to trust each cooperating router; if one or more routers are compromised, anonymous communication can still be achieved. This is because each router in an OR network accepts messages, re-encrypts them, and transmits to another onion router. An attacker with the ability to monitor every onion router in a network might be able to trace the path of a message through the network, but an attacker with more limited capabilities will have difficulty even if he controls one or more onion routers on the message's path.

Onion routing does not provide perfect sender or receiver anonymity against all possible eavesdroppers—that is, it is possible for a local eavesdropper to observe that an individual has sent or received a message. It does provide for a strong degree of unlinkability, the notion that an eavesdropper cannot easily determine both the sender and receiver of a given message. Even within these confines, onion routing does not provide any absolute guarantee of privacy; rather, it provides a continuum in which the degree of privacy is generally a function of the number of participating routers versus the number of compromised or malicious routers.

Onions

Routing onions

Example "onion"

The primary innovation in onion routing is the concept of the routing onion. Routing onions are data structures used to create paths through which many messages can be transmitted. To create an onion, the router at the head of a transmission selects a number of onion routers at random and generates a message for each one, providing it with symmetric keys for decrypting messages, and instructing it which router will be next in the path. Each of these messages, and the messages intended for subsequent routers, is encrypted with the corresponding router's public key. This provides a layered structure, in which it is necessary to decrypt all outer layers of the onion in order to reach an inner layer.

The onion metaphor describes the concept of such a data structure. As each router receives the message, it "peels" a layer from the onion by decrypting with its private key, thus revealing the routing instructions meant for that router, along with the encrypted instructions for all of the routers located farther down the path. Due to this arrangement, the full content of an onion can only be revealed if it is transmitted to every router in the path in the order specified by the layering.

Once the path has been specified, it remains active to transmit data for some period of time. While the path is active, the sender can transmit equal-length messages encrypted with the symmetric keys specified in the onion, and they will be delivered along the path. As the message leaves each router, it peels off a layer using the router's symmetric key, and thus is not recognizable as the same message. The last router peels off the last layer and sends the message to the intended recipient.

Reply onions

Onion routing also includes a technique allowing recipients to send responses back to the sender, without compromising the identity of either party. This is embodied in the concept of reply onions; these are similar to normal routing onions, except that they encode a path back to the sender. To initiate a two-way conversation, a sender generates both an onion and a reply onion. The reply onion is transmitted to the recipient, who then uses it to initiate the return path. Because the reply onion is multiply-encrypted, it provides little information that might compromise the sender — an attacker must either break the public-key encryption, or alternatively compromise all of the routers in the return path.

Weaknesses

Onion routing has several weaknesses. For one, it does not provide much defense against timing analysis. If an attacker observes a relatively under-loaded onion router, he can link incoming/outgoing messages by observing how close together in time they are received and re-sent. However this can be overcome by buffering several messages and then transmitting them using a pseudorandom timing algorithm.

Onion routing networks are also vulnerable to intersection attacks and predecessor attacks. Intersection attacks rely on the fact that onion routers periodically fail or leave the network; thus, any communication path that remains functioning cannot have been routed through those routers that left, neither can it involve routers that joined the network recently. In a predecessor attack, an attacker who controls an onion router keeps track of a session as it occurs over multiple path reformations (paths are periodically torn down and rebuilt). If an attacker observes the same session over enough reformations, he will tend to see the first router in the chain more frequently than any other router.

Onion routing exit nodes give the operator complete access to the content being transmitted (via sniffing) and therefore the onion network should not be used to transmit sensitive information. A Swedish researcher, Dan Egerstad, was able to collect over one hundred foreign embassy email account passwords using a sniffing attack.

Applications

Tor: the second-generation onion router

Main article: Tor (anonymity network)

On 13-Aug-2004 at the 13th USENIX Security Symposium, Roger Dingledine, Nick Mathewson, and Paul Syverson presented Tor, The Second-Generation Onion Router.

Tor is unencumbered by the original onion routing patents, because it uses telescoping circuits. Tor provides perfect forward secrecy and moves protocol cleaning outside of the onion routing layer, making it a general purpose TCP transport. It also provides low latency, directory servers, end-to-end integrity checking, and variable exit policies for routers. Reply onions have been replaced by a rendezvous system, allowing hidden services and websites. The .onion pseudo-top-level domain is used for addresses in the Tor network.

The Tor source code is published under the BSD license. As of May 2007, there are nearly 1000 publicly accessible onion routers.

See also

• Anonymous P2P
• Tor (anonymity network)
• Degree of anonymity
• Chaum mixes
• Onion

Further reading

• Email Security, Bruce Schneier (ISBN 0-471-05318-X)
• Computer Privacy Handbook, Andre Bacard (ISBN 1-56609-171-3)

External links

• Onion Routing Publications
• Tor source code, design documents, and publications
• English Tor installation and setup guide for beginners under Windows XP