[PAPER REVIEW] Tor: The Second-Generation Onion Router

Title Tor: The Second-Generation Onion Router [Link]
Author Roger Dingledine, Nick Mathewson and Paul Syverson Email arma@freehaven.net
Publishing 13th USENIX Security Symposium Year 2004
Abstract We present Tor, a circuit-based low-latency anonymous communication service. This second-generation Onion Routing system addresses limitations in the original design by adding perfect forward secrecy, congestion control, directory servers, integrity checking, configurable exit policies, and a practical design for location-hidden services via rendezvous points. Tor works on the real-world Internet, requires no special privileges or kernel modifications, requires little synchronization or coordination between nodes, and provides a reasonable tradeoff between anonymity, usability, and efficiency. We briefly describe our experiences with an international network of more than 30 nodes. We close with a list of open problems in anonymous communication.
Summary I. Overview

  • Circuit based, fixed-size cells
  • Design: Perfect forward secrecy, Separation of “protocol cleaning” from anonymity, No mixing, padding, or traffic shaping, Many TCP streams can share one circuit, Leaky-pipe circuit topology, Congestion Control, Directory Servers, Variable exit policies, End-to-end integrity checking, Rendezvous points and hidden services

2. Related Work

Mix-Net, Babel, Mix-master, Mixminion, Anonymizer, Java Anon Proxy, PipeNet, ISDN mixes,    Tarzan, MorphMix, Crowds, Hordes, Herbivore, P5, Freedom, Cebolla, Anonymity Network, …

3. Design goals and assumptions

  • Goals: Deployability, Usability, Flexibility, Simple Design
  • Non-goals: Not peer-to-peer, Not secure against end-to-end attacks, No protocol normalization, Not steganographic

4. The Tor Design

  • Overlay network: each OR runs as a normal user-level process, and OP(Onion Proxy) to fetch directories and establish circuits.
  • Two keys: long-term identity key to sign TLS certificate and OR’s router descriptor, short-term onion key to decrypt requests
  • Cells:
  • Circuits and streams: Once a sender established a circuit, he can send relay cells
  • Brief Steps:
    (a) Opening and closing streams
    (b) Integrity checking on streams
    (c) Rate limiting and fairness:
    (d) Circuit-level throttling: packaging window, delivery window)
    (e) Stream-level throttling: relay sendme cells to implement end-to-end flow control

5. Rendezvous Points and hidden services

  • Goals: Access-control, Robustness, Smear-resistance, Application-transparency
  • Integration with user applications:
    FQDN (x.y.onion where x=authorization cookie, y=hash of the public key)
  • Procedures
    Bob generates a long-term public key pair to identify his service
    Bob chooses some introduction points, and advertises them on the lookup service
    Bob builds a circuit to each of his introduction points, and tells them to wait for requests
    Alice learns about Bob’s service out of band, retrieving the details from the lookup service
    Alice chooses an OR as the rendezvous point (RP) for her connection to Bob’s service
    Alice opens an anonymous stream to one of Bob’s introduction points
    Alice gives it a message including her RP, rendezvous cookie, and then a DH handshake
    The RP connects Alice’s circuit to Bob’s. (RP can’t recognize Alice, Bob, or the data)
    Alice sends a relay begin cell along the circuit, arriving at Bob’s OP and Bob’s webserver.
    An anonymous stream has been established, then Alice and Bob communicate as normal.

6. Other design decisions

  • Denial of Service
    (a) CPU-consuming denial-of-service attacks: requiring clients to solve a puzzle while TLS handshaking or accepting create cells
    (b) Disrupting a single circuit or link breaks all streams passing along that part of the circuit (end-to-end TCP ACK protocol)
  • Exit-policies and abuse
    (a) Attackers can harm the Tor network by implicating exit servers for their abuse. (This remains an arms race (unsolved))
    (b) Mitigation: each onion router’s exit policy describes to which external addresses and ports the router will connect.
  • Directory Servers
    (a) Partitioning attack to deceive a client about the router membership list, topology, or current network state
    (b) Act as an HTTP server, so clients can fetch current network state and router lists, and so other ORs can upload state info.

7. Attacks and Defenses

  • Passive Attacks
    • Observing user traffic patterns.
    • Observing user content.
    • Option distinguishability.
    • End-to-end timing correlation.
    • End-to-end size correlation.
    • Website fingerprinting.
  • Active Attacks
    • Compromise keys.
    • Iterated compromise.
    • Run a recipient.
    • Run an onion proxy.
    • DoS non-observed nodes.
    • Run a hostile OR.
    • Introduce timing into messages.
    • Tagging attacks.
    • Replace contents of unauthenticated protocols.
    • Replay attacks.
    • Smear attacks.
    • Distribute hostile code..
  • Directory Attacks
    • Destroy directory servers.
    • Subvert a directory server.
    • Subvert a majority of directory servers.
    • Encourage directory server dissent.
    • Trick the directory servers into listing a hostile OR.
    • Convince the directories that a malfunctioning OR is working.
  • Attacks against R/P
    • Make many introduction requests.
    • Attack an introduction point.
    • Compromise an introduction point.
    • Compromise a rendezvous point.
Note One of the best papers in terms of anonymity implementation. The tor is currently one of the largest deployed anonymous network over the world. Although there are a variety of conceptually anonymous networks and several ones in practice, tor is the most popular (as of now having millions of users) amongst them.This paper presents a circuit-based low-latency anonymous communication service. It addresses the limitations for the first tor implementation by adding a large number of features such as perfect forward secrecy, directory servers, integrity checking, configurable exit policies, and location-hidden services via rendezvous points.As authors mentioned, one of the biggest problem would be exit abuse, however, this might be remediated if end-to-end confidentiality have been used. One of side effects is to take advantage of high-level anonymity for the malicious purpose like spreading malware, exploit routes to avoid being kept track and/or IP laundry, which seems obvious now.