Onion Routing is a technique for anonymous communication over a computer network, developed by David Goldschlag, Michael Reed, and Paul Syverson. It is based on David Chaum's Mix networks, though it includes a number of advances and modifications. Among these modifications is the concept of "routing onions", which encode routing information in a set of encrypted layers.
The goal of Onion Routing 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 of Onion 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 router is compromised, anonymous communication can still be achieved. This is due to the fact that 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 or she 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 vs. the number of compromised or malicious Routers.
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 off of 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 is encrypted using a different key, and thus is not recognizable as the same message.
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.
Onion Routing has several weaknesses, however. For one, it does not provide much to defend against timing analysis. If an attacker observes a relatively under-loaded Onion Router, he or she can link incoming/outgoing messages by observing how close together in time they are received and re-sent. 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, nor cannot 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.
