Onion routing: relays, layers, guards and where it fails

Peeling an onion: what the term means

Wikipedia describes onion routing as a technique for anonymous communication over a computer network. Messages are encapsulated in layers of encryption, like the layers of an onion, and the encrypted data is transmitted through a series of network nodes called onion routers. Each router peels away a single layer, which reveals the data’s next destination, and when the final layer is decrypted the message arrives. The same page says each intermediary generally knows only the node before it and the node after it, which limits what any single relay can learn about the route.

The Naval Research Laboratory’s historical site, which says it reflects onion-router.net roughly as it stood around 2005, gives the aim in its own words. Onion routing, it says, prevents the transport medium from knowing who is communicating with whom, so the network knows only that communication is taking place. It adds that the content is hidden from eavesdroppers up to the point where the traffic leaves the onion routing network.

On the history, Wikipedia says onion routing was developed in the mid-1990s at the U.S. Naval Research Laboratory by Paul Syverson, Michael G. Reed and David Goldschlag, to protect U.S. intelligence communications online. The Navy filed a provisional patent application in 1997 and a non-provisional one in 1998, and the patent was granted in 2001. In 2002, Wikipedia says, Roger Dingledine and Nick Mathewson joined Paul Syverson to develop what became the largest and best-known implementation, Tor. After the laboratory released the code for Tor under a free license, Dingledine, Mathewson and five others founded The Tor Project as a non-profit organization in 2006.

The laboratory’s site calls Tor “Generation 2 Onion Routing”, and it spends a note on the word generation because, it says, terminology has varied over the years. It treats the initial design, published at the first Information Hiding Workshop and deployed in mid 1996, as generation 0, the designs between that and Tor as generation 1, and Tor, as conceived roughly from 2002 to 2005, as generation 2. It also describes a Tor network of several hundred nodes, a figure from around 2005 and not a current one.

Three relays, one layer each

Wikipedia describes how the path is made. The originator selects a set of nodes from a list provided by a “directory node” and arranges them into a path called a chain or circuit. The Tor Project’s glossary defines a circuit as a path through the Tor network built by clients and made of randomly selected nodes. It says most circuits consist of three nodes: a guard or bridge, a middle relay and an exit. NYU Networks at ITP says the same by a different route: a circuit is 3 nodes long by convention, with an entry node (also described as a guard), a middle node and an exit node. Wikipedia does not fix a number and says the chain is typically limited to preserve performance. The pages we read do not say why the usual count is three rather than four. When a bridge is used, the glossary says, the bridge takes the place of the guard; our page on Tor bridges covers that case.

The layers match the relays. The glossary says Tor uses three layers of encryption in a circuit and that each relay decrypts one layer before passing the request on to the next relay. NYU describes the client wrapping the traffic with the entry node’s key, the middle node’s key and the exit node’s key, each layer readable only by the node it belongs to. When the traffic first leaves, NYU says, only the source and the entry node can be known to anyone who intercepts it; the rest is incrementally decrypted and used to forward the traffic.

Wikipedia explains how the circuit grows one hop at a time. Using asymmetric key cryptography, the originator obtains a public key from the directory node, sends an encrypted message to the first (entry) node, and sets up a connection and a shared secret it calls a session key. Through that link the originator relays a message to a second node using encryption that only the second node, and not the first, can decrypt. The second node cannot tell whether the first is the originator or just another node in the circuit, and the third node is added the same way. On the way back the intermediary nodes keep the same link, with the data layered in reverse: the final node adds the first layer and the first node adds the last, and the originator decrypts all of them.

What each party sees follows from that. Wikipedia says a node cannot tell whether the node before it is the originator or another intermediary, and cannot tell how many other nodes are in the circuit; the exit node, it says, can identify that it is the final relay before the destination. NYU adds that your internet provider might see traffic headed to a Tor entry node and so know you are using Tor, but cannot know what you are trying to access once the encrypted message is inside the network. The site you reach sees the IP address of the last node, as NYU puts it, and the glossary says the same about the exit.

How often the path changes

NYU describes what Tor Browser does with circuits. It chooses a random three-node circuit from a published list of Tor nodes, and clicking the “i” icon to the left of the address bar shows the entry node, the relay node and the exit node with their IP addresses and countries. The glossary describes the same view differently, as the Tor circuit icon in the URL bar of the desktop browser. NYU says staying on the same circuit can risk your anonymity, so the browser chooses a new random circuit about every 10 minutes, and you can also refresh the circuit for a single open tab; it adds that the “New Identity” button closes open tabs, clears cookies and browsing history and uses new circuits for all connections. The glossary describes New Identity in the same terms and says Tor Browser warns that all activity and downloads will be stopped. Our page on whether Tor Browser is safe goes into the browser itself.

Why the first relay stays put

The Tor Project’s page on entry guards says they are the first relays your Tor client connects to. Instead of picking a new entry each time, Tor selects a small set of guards and reuses them, which the page says reduces the chances of an attacker correlating your traffic and deanonymizing you. The glossary adds that non-exit relays can act as either a middle relay or a guard for different users.

The page gives its reasoning. Tor, it says, like all current practical low-latency anonymity designs, fails when the attacker can see both ends of the communications channel. Its example is an attacker who controls or watches the relay you use to enter the network and also controls or watches the website you visit. In that case the page says the research community knows of no practical low-latency design that can reliably stop the attacker from correlating volume and timing on the two sides. NYU describes the same weakness as traffic-analysis attacks, where an observer who can see the start and the end of your traffic uses timing correlation to work out what you are doing.

The page then does the sum. If the attacker controls or can observe c relays out of n in total, and you select new entry and exit relays each time, it says the attacker can correlate all your traffic with a probability of around (c/n) squared. It says profiling is “for most users, as bad as being traced all the time”, because the attacker noticing once is as bad as noticing more often, so choosing many random entries and exits gives the user no chance of escaping profiling by this kind of attacker.

The fix, in the page’s words, is entry guards: each client selects a few relays at random and uses only those for the first hop. If those relays are not controlled or observed, the page says the attacker cannot win and the user is secure. If they are, the attacker sees a larger fraction of the user’s traffic but the user is no more profiled than before, and the user has some chance, on the order of (n minus c) over n, of avoiding profiling where there was none. NYU calls this somewhat unintuitive: randomly choosing a small set of relays gives a greater chance of avoiding authorities than a completely random entry each time.

The page lists a second use and a limit. Restricting entry nodes may also help against attackers who run a few Tor nodes in order to list the IP addresses of Tor users. The page says that feature will not really become useful until a “directory guard” design is adopted too, and the text we read does not say whether that has happened.

The last relay, and why HTTPS still matters

The glossary defines the exit as the last relay in the circuit, the one that sends traffic out onto the public Internet. The service you are connecting to, whether a website, a chat service or an email provider, sees the IP address of the exit. Because the exit decrypts the final layer, Wikipedia says a compromised exit node can acquire the raw data being transmitted, potentially including passwords, private messages and bank account numbers. NYU says the same for traffic that is not encrypted, giving HTTP in place of HTTPS as the example, and says a snooper could read personally identifying data in the final leg.

Wikipedia gives a case: a Swedish researcher, Dan Egerstad, used such an attack to collect the passwords of over 100 email accounts related to foreign embassies. That account is Wikipedia’s, and we did not find it on the pages we read besides Wikipedia’s. Wikipedia compares exit node vulnerabilities to those on unsecured wireless networks and says both can be mitigated by authenticated end-to-end encryption such as HTTPS. With end-to-end encryption between sender and recipient, and a sender who is not lured into trusting a false certificate offered by the exit node, the last intermediary cannot view the original message, it says.

NYU points to a further risk even with encryption: if you log in to a site and that site correlates your identity with other traffic it has seen from the same exit node, your anonymity is at risk. Its rule of thumb is not to send personal information such as a username or email address while using Tor. On the exit and onion services the pages do not line up. NYU says that when you visit an onion service over Tor, someone who compromises the exit node talking to the service can only know the IP associated with the service, not the service itself and not the contents. The glossary says onion service circuits never use an exit node. We cannot reconcile the two from what we read, so we report both.

Onion services: six relays and a meeting point

The Tor Project’s page says onion services are services that can only be accessed over Tor. The glossary says “hidden services” is the former name, still sometimes used in Tor documentation, and the laboratory’s site says hidden services and rendezvous points have been part of onion routing since the beginning. The Tor Project page lists four benefits: location hiding, end-to-end authentication, end-to-end encryption and NAT punching, the last meaning that a service does not need open ports because it only establishes outgoing connections.

The address is part of how this works. The Tor Project page says an onion service’s address is the service’s identity public key, and its example address is 56 characters long before the .onion ending. NYU describes the address as a 16-character string based on a hash of the public key. The pages differ, and the NYU page does not say why. This page prints no onion addresses and gives no steps for reaching an onion service. The Tor Project page breaks the protocol into acts, which we have condensed into six steps:

1. Introduction points. The service picks relays and builds long-term circuits to them, so that its location stays hidden. The page says the service is reachable only through three introduction points, which it connects to through a three-hop circuit.
2. Descriptor. The service assembles a descriptor listing its introduction points, signs it with its identity private key and uploads it to a distributed hash table, using an anonymized circuit.
3. Lookup. A client with the onion address asks the hash table for the descriptor and verifies its signature with the public key encoded in the address. The page says this is what provides end-to-end authentication.
4. Rendezvous point. The client picks a relay, builds a circuit to it and asks it to be the rendezvous point, giving it a one-time secret.
5. Introduction. The introduction point passes the client’s details, the secret and the rendezvous address, on to the service.
6. Meeting. The service connects to the rendezvous point through an anonymized circuit and sends the same secret. The page says the rendezvous point matches the two and then simply relays end-to-end encrypted messages between client and service.

The page counts the result: the complete connection consists of 6 relays, 3 picked by the client, the third being the rendezvous point, and the other 3 picked by the onion service. NYU describes the same pattern, a circuit of 6 nodes with 3 from the client and 3 to the service. The glossary agrees that most onion services use six hops in a circuit, with the exception of single onion services.

What it does not promise

Wikipedia explains timing analysis. Ordinary internet connections are not anonymous partly because internet providers can trace and log connections between computers. Onion routing obscures the path, but records of connections between computers still exist, and traffic analysis searches the records for a potential originator and tries to match timing and data transfers to connections made to a potential recipient. If an attacker has compromised both ends of a route, it says, a sender may be seen to have transferred an amount of data to an unknown computer some seconds before a different unknown computer transferred similar data to a particular destination. Wikipedia lists two things that may help the attacker: nodes failing or leaving the network, and a compromised node keeping track of a session while chains are periodically rebuilt.

Two of the pages give numbers, and both are old or partial. The laboratory’s site, from around 2005, describes a Tor network of several hundred nodes and says the protection makes it difficult to determine the number of users. The abstract of an arXiv paper by Akshaya Mani, T Wilson-Brown, Rob Jansen, Aaron Johnson and Micah Sherr, submitted on 22 September 2018, reports a measurement study using privacy-preserving tools. Its abstract says Tor had about 8 million daily users, a factor of four more than previously believed, that about 90% of lookups for onion addresses were invalid and that more than 90% of attempted connections to onion services failed. Those are 2018 figures, and we read only the abstract, not the paper.

Wikipedia also names a variant. Garlic routing, it says, is associated with the I2P network and encrypts multiple messages together, which it says increases the speed of data transfer and makes it more difficult for attackers to perform traffic analysis. Its list of related projects says Tox and Tribler implement onion routing.

The pages we read do not say whether onion routing is legal or illegal in any country, so we do not answer that. They do not say how many users are actually deanonymized in practice, and they do not give a percentage for how traceable Tor is. Wikipedia carries a notice, dated March 2017, that its factual accuracy may be compromised by out-of-date information, so the patent dates, the 2006 founding of The Tor Project, the Egerstad case, garlic routing and the Tox and Tribler mention are Wikipedia’s account alone and we found them on no other page we read; for how the mechanism works, the Tor Project and NYU pages agree with it. For the wider picture, our page on the dark web starts from the words people mix up.