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 peeling 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.[citation needed]
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.[citation needed]
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.[citation needed]
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.[citation needed]
Onions
Routing onions
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
- the last intermediary (the exit node)
- 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.
Circuit establishment and sending data
To create and transmit an onion, the following steps are taken:[1]
- The originator picks nodes from a list provided by a special node called the directory node (traffic between the originator 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. No node within the circuit, except for the exit node, can infer where in the chain it is located, and no node can tell whether the node before it is the originator or how many nodes are in the circuit.
- Using asymmetric key cryptography, the originator uses the public key (obtained from the directory) of the first node in the circuit, known as the entry node, to send it an encrypted message, called a create cell, containing:
- A circuit ID. The circuit ID is random and different for each connection in the chain.
- A request for the receiving node (i.e. the entry node in this case) to establish a circuit with the originator.
- The originator's half of a Diffie-Hellman handshake (to establish a shared secret).
- The entry node, which just received one half of the handshake, replies to the originator, in unencrypted plaintext:
- The entry node's half of the Diffie-Hellman handshake.
- A hash of the shared secret, so that the originator can verify that he/she and the entry node share the same secret.
- Now the entry node and originator use their shared secret for encrypting all their correspondence in symmetric encryption (this is significantly more efficient than using asymmetric encryption). The shared secret is referred to as a session key.
- A relay cell, as opposed to a command cell like the create cell used in the first step, is not interpreted by the receiving node, but relayed to another node. Using the already established encrypted link, the originator sends the entry node a relay extend cell, which is like any relay cell, only that it contains a create cell intended for the next node (known as the relay node) in the chain, encrypted using the relay node's public key and relayed to it by the entry node, containing the following:
- A circuit ID. Once again, it is arbitrary, and is not necessarily the same for this connection as it is for the previous.
- A request from the entry node to the relay node to establish a circuit.
- The originator's half of a Diffie-Hellman handshake. Once again, the new node cannot tell whether this handshake originated from the first node or the originator, it is irrelevant for operating the chain.
- The relay node, similar to the first step, replies with its half of the handshake in plain text along with a hash of the shared secret.
- As the entry node - relay node circuit has been established, the entry node replies to the originator with a relay extended cell, telling it that the chain has been extended, and containing the hash of the shared secret along with the relay node's half of the handshake. The originator and the relay node now share a secret key.
- To extend the chain further, the originator sends the entry node a relay cell which contains a relay cell that only the relay node can decrypt, instructing the relay node to extend the chain further. The process can be repeated as above to as many nodes as possible. In Tor, for example, chains are limited to 3 nodes: the entry node, the relay node, and the exit node.
When the chain is complete, the originator can send data over the Internet anonymously. For example, if the originator wishes to open a website, the originator's onion proxy (typically running a SOCKS proxy) forwards the request from the originator's browser to the originator's local onion router (which controls the circuits). The onion router creates the following cell:
- (Send HTTP request to IP-of-webpage)]}
Where curly brackets indicate content encrypted with the entry node's shared key, square brackets content encrypted with the relay node's key, and regular brackets content encrypted with the exit node's key.
Upon receiving the cell, the entry node only sees the following:
The entry node knows that relay requests for circuit ID 1 (C1) should be relayed to circuit ID 2 (C2), since it received a request from the originator to extend the circuit earlier. For this reason, there is no need for the originator to know the circuit IDs, it is enough for it to tell the entry node which circuit it refers to. The entry node takes the payload and sends a relay cell to the relay node.
Upon receiving the relayed cell from the entry node, the relay node sees the following:
The relay node follows the same protocol as the entry node and relays the payload to the exit node. The exit node sees this:
- Send HTTP request to IP-of-webpage
The exit node proceeds to sending an HTTP request to the website.
Receiving data
Continuing from the above example: the website's server responds to the exit node with the contents of the web page as follows:[1]
The exit node uses its session key (the secret shared between it and the sender) to encrypt the content it received, and sends the following cell to the relay node:
The relay node knows which shared secret key to use, since it refers to circuit ID #3, and uses that key to encrypt the message again (so that no adversary watching the traffic can know the structure of the chain). It also knows that any relay request from circuit #3 should be relayed to circuit #2. It relays the following cell to the entry node:
The entry node takes the encrypted payload, and sends the following cell to the originator:
The sender receives a cell that is encrypted, from inside the cell (onion) to the outside: the exit node shared key, the relay node shared key, and the entry node shared key. The sender's onion router must decrypt the cell three times with three different keys in order to see the page. The number of layers of encryption between each hop is constant, however, no node can tell whether encrypted data contains more encrypted data. The purpose of layered encryption is not to make the encryption stronger per se, but rather to facilitate the execution of perfect forward secrecy. That is, if the exit node encrypted the page with the sender key, and the nodes after it would only pass on that encrypted data without encrypting it in more layers with their respective keys, an adversary would only have to compromise the exit node's shared key to be able to intercept the sender's incoming traffic. However, since the nodes add more layers of encryption as the cell is passed on, compromising the exit node's shared key will only reveal the contents of the webpage but not the IP of the sender.
Weaknesses
- Timing analysis: An adversary could determine whether a node is communicating with a web by correlating when messages are sent by a server and when messages are received by a node. Tor, and any other low latency network, is vulnerable to such an attack.[2] A node can defeat this attack by sending dummy messages whenever it is not sending or receiving real messages. This counter-measure is not currently part of the Tor threat model [3] as it is considered infeasible to protect against this type of attack.[4]
- 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.[3]
- 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.[5]
- 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.[6] However, if the message is encrypted by SSL, the exit node cannot read the information, just as any encrypted link over the regular internet.
Applications
Tor
On August 13, 2004 at the 13th USENIX Security Symposium,[7] Roger Dingledine, Nick Mathewson, and Paul Syverson presented Tor, The Second-Generation Onion Router.[8]
Tor is unencumbered by the original onion routing patents, because it uses telescoping circuits[9]. 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 2012[update], there are about 3,000 publicly accessible onion routers.[10]
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.[citation needed]
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 eavesdropping 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).[citation needed]
See also
Further reading
- Email Security, Bruce Schneier (ISBN 0-471-05318-X)
- Computer Privacy Handbook, Andre Bacard (ISBN 1-56609-171-3)
References
External links
