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. Like someone unpeeling an onion, 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 (formerly of Extreme Networks), Paul F. Syverson, and David M. Goldschlag, and patented by the United States Navy in US Patent No. 6266704 (1998). As of 2009^[update], 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 any router is 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 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 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"

A routing onion (or just onion) is a data structure formed by 'wrapping' a plaintext message with successive layers of encryption, such that each layer can be 'unwrapped' (decrypted) like the layer of an onion by one intermediary in a succession of intermediaries, with the original plaintext message only being viewable by at most:

1. the sender
2. the last intermediary
3. the recipient

If there is end-to-end encryption between the sender and the recipient, then not even the last intermediary can view the original message; this is similar to a game of 'pass the parcel'.

An intermediary is traditionally called a node or router.

To create and transmit an onion, the following steps are taken:

1. The sender picks nodes from a list provided by a special node called the directory node (traffic between the sender and the directory node may also be encrypted or otherwise anonymised or decentralised); the chosen nodes are ordered to provide a path through which the message may be transmitted; this ordering of the nodes is called a chain or a circuit.
2. Using asymmetric key cryptography, the sender uses the public key of each chosen node to wrap the plaintext message in the necessary layers of encryption: The public keys are retrieved from an advertised list or by on-the-spot negotiation for temporary use,^[1] and the layers are applied in reverse order of the message's path from sender to receiver; with each layer, the client includes information for the corresponding node regarding the next node to which the onion should be transmitted.
3. As the onion passes to each node in the chain, a layer of encryption is peeled away by the receiving node (using the private key that corresponds to the public key with which the layer was encrypted), and then the newly diminished onion is transmitted to the next node in the chain.
4. The last node in the chain peels off the last layer and transmits the original message to the intended recipient.

Using this approach means each node in the chain is ideally aware of only 2 other nodes:

1. the preceding node from which the onion was transmitted.
2. the proceeding node to which the onion should next be transmitted.

The peeling away of each layer of the onion makes it difficult or impossible to track the onion without compromising a significant number of nodes.

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 a reply onion, which is similar to a normal onion, except that a reply onion encodes a path from the receiver back to the sender of the normal onion.

To initiate a two-way conversation, a sender generates both an onion and a reply onion. The reply onion is transmitted to the last node of the chain, which then uses the reply onion to initiate the return chain for the recipient's response. 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 compromise all of the nodes in the return chain).

Weaknesses

• Timing analysis: Incoming and outgoing messages passing through a relatively under-loaded node can be linked by observing how close together in time they are received and re-sent. However, this weakness can be overcome by buffering several messages and then transmitting them using a pseudorandom timing algorithm.^{[citation needed]}
• Intersection attacks: Nodes periodically fail or leave the network; any chain that remains functioning cannot have been routed through either the nodes that left or the nodes that recently joined the network, increasing the chances of a successful traffic analysis.
• Predecessor attacks: A compromised node can keep track of a session as it occurs over multiple chain reformations (chains are periodically torn down and rebuilt). If the same session is observed over the course of enough reformations, the compromised node tends to connect with the particular sender more frequently than any [other] node, increasing the chances of a successful traffic analysis.^[2]
• Exit node sniffing: An exit node (the last node in a chain) has complete access to the content being transmitted from the sender to the recipient; Dan Egerstad, a Swedish researcher, used such an attack to collect the passwords of over 100 email accounts related to foreign embassies.^[3] However, this weakness can be overcome by employing end-to-end encryption (that is, encryption between the sender and the recipient), such as SSL.

Applications

Tor

Main article: Tor (anonymity network)

On August 13, 2004 at the 13th USENIX Security Symposium,^[4] Roger Dingledine, Nick Mathewson, and Paul Syverson presented Tor, The Second-Generation Onion Router.^[5]

Tor is unencumbered by the original onion routing patents, because it uses telescoping circuits.^{[citation needed]} 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 April 2011^[update], there are about 2600 publicly accessible onion routers.^[6]

Decoy Cyphers

The weak link in decryption is the human in the loop. Human computation is slow and expensive. Whenever a cypher needs to be sent to a human for semantic processing, this substantially increases the cost of decryption.

A decoy cypher can take the form of noise - sending copious messages of encrypted garbage plaintext. This decreases the signal-to-noise ratio for humans trying to interpret decrypted "plaintext" messages.

A decoy cypher can also take the form of misleading information - for example, in an onion cypher, most of the layers may contain information that when decrypted will produce a message that directly misleads the person reading it - often resulting in them taking actions against their interest - such as signalling that they are evesdropping by responding to a specific false signal, false flag attacks, or causing them to suspect the wrong parties. The actual message can still be contained at some level of the onion - but preferably not the lowest level - which may include an innocuous message so that if all layers are decrypted the core seems innocent. (see noise decoy cypher).

See also

• Garlic routing
• Anonymous P2P
• Tor (anonymity network)
• Degree of anonymity
• Chaum mixes
• Bitblinder
• Java Anon Proxy

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
• Anonymous Connections and Onion Routing

References

1. ^ Roger Dingledine; Nick Mathewson, Paul Syverson. "Tor: The Second-Generation Onion Router". http://www.onion-router.net/Publications/tor-design.pdf. Retrieved 26 February 2011. 
2. ^ The Predecessor Attack: An Analysis of a Threat to Anonymous Communications Systems, by MATTHEW K. WRIGHT, MICAH ADLER, BRIAN NEIL LEVINE (University of Massachusetts Amherst) and CLAY SHIELDS (Georgetown University)
3. ^ Bangeman, Eric (2007-08-30). "Security researcher stumbles across embassy e-mail log-ins". Arstechnica.com. http://arstechnica.com/news.ars/post/20070830-security-researcher-stumbles-across-embassy-e-mail-log-ins.html. Retrieved 2010-03-17. 
4. ^ "Security '04". USENIX. 2004-01-04. http://www.usenix.org/events/sec04. Retrieved 2010-03-17. 
5. ^ "Security '04 Abstract". Usenix.org. 2004-07-27. http://www.usenix.org/events/sec04/tech/dingledine.html. Retrieved 2010-03-17. 
6. ^ "TorStatus — Tor Network Status". Torstatus.blutmagie.de. http://torstatus.blutmagie.de/. Retrieved 2010-03-17.