Onion Routing
|
|
Onion Routing is a technique for pseudonymous (or 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.
| Contents |
Capabilities
The goal 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 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.
Onions
Routing Onions
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.
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 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.
Applications
Tor: The Second-Generation Onion Router
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 such as The Hidden Wiki (http://6sxoyfb3h2nvok2d.onion/) (you need Tor to access this page).
The Tor source code is published under the BSD license. As of May, 2005, there are more than 100 publicly accessible onion routers (http://www.noreply.org/tor-running-routers).
See the Tor article for more information.
I2P
I2P is an open source project for encrypted and anonymous and/or pseudonymous virtual private network communication. Implemented using Onion Routing, it shares a lot of the ideas behind Tor. See the article on I2P for more details.
See also
External links
- Onion Routing Publications (http://www.onion-router.net/Publications.html)
- Tor source code, design documents, and publications (http://freehaven.net/tor)
- a german Wiki concerning with Security and Anonymity - mainly Tor (in development) (http://www.securiwiki.de)
- a remailer FAQ (http://www.andrebacard.com/remail.html)
- Remailer Vulnerabilities (http://www.skuz.net/potatoware/PSKB-035.html)
- Mixmaster & Remailer Attacks (http://www.obscura.com/~loki/remailer/remailer-essay.html)
Further reading
- Email Security, Bruce Schneier (ISBN 047105318X)
- Computer Privacy Handbook, Andre Bacard (ISBN 1566091713)