Onion routing 424617 move=:edit= 218612005 2008-06-11T12:16:45Z Macabu 5874111 /* Weaknesses */ '''Onion routing''' is a technique for [[pseudonymity|pseudonymous]] (or [[anonymity|anonymous]]) communication over a [[computer network]], developed by David Goldschlag, Michael Reed, and Paul Syverson {{Fact|date=March 2008}}. It is based on [[David Chaum]]'s [[mix network]]s, 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. ==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 network|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 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 [[eavesdropper]]s—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=== [[Image:Onion diagram.png|thumb|right|250px|Example "onion"]] [[Image:Onion_diagram.svg|thumb|right|250px|Same example, vector graphic]] 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 key]]s 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 cryptography|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 or she 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 [http://arstechnica.com/news.ars/post/20070830-security-researcher-stumbles-across-embassy-e-mail-log-ins.html sniffing attack.] ==Applications== ===Tor: the second-generation onion router=== {{main|Tor (anonymity network)}} On 13-Aug-2004 at the [http://www.usenix.org/events/sec04 13th USENIX Security Symposium], [[Roger Dingledine]], [[Nick Mathewson]], and [[Paul Syverson]] [http://www.usenix.org/events/sec04/tech/dingledine.html presented] [[Tor (anonymity network)|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 [[Transmission Control Protocol|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 [http://www.noreply.org/tor-running-routers nearly 1000 publicly accessible onion routers]. ==See also== * [[Anonymous P2P]] * [[Tor (anonymity network)]] * [[Degree of anonymity]] * [[Chaum mixes]] ==External links== * [http://www.onion-router.net/Publications.html Onion Routing Publications] * [https://www.torproject.org/ Tor source code, design documents, and publications] * [http://www.anti1984.com/en/tor.html English Tor installation and setup guide for beginners under Windows XP] <!-- This link 404s * Information on the predecessor attack: [http://prisms.cs.umass.edu/brian/privacy.html UMass Amherst Publications on privacy] --> ==Further reading== * ''Email Security'', [[Bruce Schneier]] (ISBN 0-471-05318-X) * ''Computer Privacy Handbook'', Andre Bacard (ISBN 1-56609-171-3) [[Category:Internet privacy]] [[Category:Routing]] [[Category:Anonymity networks]] [[bn:ওনিয়ন রাউটিং]] [[de:Onion Routing]] [[no:Onion routing]] [[sv:Onion routing]]