[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.

Malware and its Use of Implemented Anonymous Networks

현대 악성코드는 시간이 지날수록 점점 지능화되고 정교해지고 있다. 때로는 공격용으로 만든 단순한 부산물이라기보다 정교하게 작성한 창조물같아 보이기도 한다. 악성코드 기능, 전파 그리고 악용하는 형태를 아래와 같이 정리해 봤다.
Modern malware gets more intelligent and elaborated as time goes by. Sometimes it looks like a creature of sophisticated work, rather than just a by-product for the purpose of attack. I have organized the features, distributions and misuses of malware.
요즘 공격은 악성코드를 수반하는 경우가 많으며 다음과 같은 특성을 지닌다.
 공격 자체에서 네트워크 상에서 추적하기 어렵도록 또는 시스템에서 흔적을 남기지 않는 방식으로 은닉을 시도함
 안티 리버싱 (안티-VM, 안티-디스어셈블리, 안티-디버깅)과 암호화/인코딩 기법을 이용해 분석을 어렵게 함
 특정 대상만을 공격하며 먹이가 아닌 경우 아무런 동작을 하지 않음
 대상을 파괴적이거나 무자비한 형태로 공격함
 주요정보 또는 데이터 절취와 블랙마켓 판매
 업데이트 서버나 대중적인 애플리케이션을 통한 배포 사용
Modern attack shows that it mostly involves malware, which
 Attempts to conceal attack itself by:
    . making it hard to trace themselves down from network perspective
    . making it difficult to find artifacts with wiping out themselves from system perspective
 Employs many techniques to be hard for analysis including:
    . Anti-VM, Anti-disassembly and Anti-debugging
    . Encryption and decoding
 Infects a target but do nothing harm until they achieve their goals
 Assaults a target in a destructive and reckless manner
 Steals useful information and/or data and trade on the black market
 Uses an update server and/or popular applications to maximize distribution
또한 악성코드는 다음과 같이 진화하거나 확장하리라 쉽게 상상할 수 있다.
 기존의 합법적인 도구 여러 개를 악의적인 방식으로 활용함
 클라우드 컴퓨팅 인프라에 특화된 변종 출현 가능성
 특정한 대상 (특정 장비나 조직)에 완전히 국한된 공격
 스테가노그래피를 이용한 교묘한 공격
 이미 공격당한 장비를 전용 익명 네트워크로 활용함
 기 공격으로 이미 노출된 개인정보(건강/신용카드/종교나 신념/주민번호/주소/계정 등)를 입수한 후 협박
Also, it is easy to imagine how future malware will evolve and/or expand, which
 Employs the combination of existing – even legitimate – tools/techniques in a malicious fashion
 Emerges new variables targeting cloud computing infrastructure
 Focuses highly on target-oriented attack (a specific device or organzation) which does not affect others at all
 Uses steganography technique in the wild more cleverly
 Forms private p2p anonymous network (e.g tor) with exploited zombie machines
 Makes threats against a privacy, exposing individual information stolen in the past and/or other area including:
    . credit card, health history, religion or belief, social security number, address, account and so on
이제 악성코드가 자신을 은폐하기 위해 사용할 가능성이 있는 익명 네트워크를 알아보자.
The anonymous networks below are implemented ones, which might be used as hiding malware trace.
악성코드가 자신을 은폐할 목적으로 배포하는 효율적인 방법 중 하나는 익명 네트워크를 활용하는 것이다. 가장 크게 구현된 네트워크는 Tor인데, 이전 차움의 믹스넷 설계라는 익명 우편을 전송하는 아이디어로 시작됐다. 토르를 구현한 Roger Dingledine은 2004년 이 특별한 형태의 네트워크를 구성했고 아래 링크에서 당시 발표한 페이퍼를 볼 수 있다.
One of the effective way to distribute malware secretly is to use the existing implemented anonymous network. The biggest implemented one is tor or the Onion Routing, whose idea comes from Chaum’s Mix-net design at first. The creator of tor, Roger Dingledine, has started to design this special network since 2004. You can read the paper here: https://svn.torproject.org/svn/projects/design-paper/tor-design.pdf
아래는 tor에서 간단히 경로를 생성하는 메커니즘이다.
a. 토르 네트워크에 접속하려는 자는 우선 디렉토리 노드에서 노드 리스트를 받아 선택한다.
b. 경로에 참여하는 노드 (선택된 노드)는 디피-헬만 키 교환 알고리즘을 통해 세션 키를 생성한다. (TLSv1 상에서)
c. 각 노드는 공개키 스키마를 이용해 라우팅 정보를 포함해 모든 데이터를 암호화한다.
중간 노드는 트래픽이 온 바로 이전 노드와 트래픽을 전송할 바로 다음 노드만 알고 있다. 따라서 마지막 노드를
제외한 노드는 트래픽을 추적할 수 없다.
d. 접속자는 사용할 경로를 여러 개 생성한 다음 이전 세션이 종료되면 다른 경로를 택해 전송한다.
The below shows a brief circuit (chain) establishment mechanism in tor.
a. The directory node provides node list to originator to choose nodes.
b. Each participating node does Diffie-Hellman key exchange to create session key. (over TLSv1)
c. Each node encrypts all data including routing information with public key scheme.
The node only understands the previous node which this traffic comes from and the next node which it goes to.
Therefore, there is no way to trace the traffic back except exit node.
d. The originator creates several circuits to make use of, and change a new chain when old session is over.
Freenet은 인터넷에서 동작하는 별도 네트워크이다. 하지만 tor와 다르게 모든 컨텐츠는 Freenet을 통해서만 접속할 수 있다. 매우 큰 분산 데이터베이스 형태로 동작한다. 한 사용자가 파일이나 특정 페이지를 공유할 경우 이를 요청하는 사람이 많을수록 더 분산된 캐시에 저장되고 다 빠르게 다운로드할 수 있는 구조다. 분산 저장소는 C:\Users\[UserID]\AppData\Local\Freenet\datastore 경로에 존재하며 암호화되어 있어 통제를 할 수 없는 구조다Freenet은 사용자가 요청시 키를 가지고 접속하고 해당 파일에 대한 관리를 할 수 있다. 관련 키는 4가지가 존재하며, 반드시 fproxy를 통해 접근할 수 있다.

Freenet is a separate network that runs over the Internet. However, other than tor, its content can be accessed only through Freenet including: Freesites (websites on Freenet), in-Freenet chat forums (FMS, Sone, etc), files shared within Freenet, and in-Freenet email.

It has a large distributed database. Thus the more popular a file or page, the more widely it will be cached and the faster it will download. With an appropriate key, Freenet returns the proper file which a user have requested. Here is the location to store data: C:\Users\[UserID]\AppData\Local\Freenet\datastore. There is little or no control over what is stored in the datastore folder as you might imagine.

There are four different keys associated with contents, and you have to get access to them with fproxy.

(3) Gnunet (https://gnunet.org/)

Gnunet은 2001년도에 시작한 프로젝트로 안전한 p2p 네트워크를 목적으로 하고 있다. ECRS라는 컨텐츠 인코딩 방식을 사용하며 검열에 대응한 파일 공유 기법이다. 정식 웹사이트에서는 중앙 데이터베이스를 사용하지 않은 안전한 개별 간 네트워킹 프레임워크를 사용한다고 소개한다.

Gnunet은 주로 파일 공유를 목적으로 하며 실제 웹을 통한 접속은 tor를 이용하라고 권고한다. 파일 공유, 검색, 분배, 캐싱 등을 익명으로 할 수 있도록 설계한 대표적인 익명 네트워크다.

Gnunet has started in late 2001. It also aims to implement for secure peer-to-peer networking. It uses improved content encoding: ECRS or the encoding for censorship resistant sharing. Accroding to Gnunet official website, it is a framework for secure peer-to-peer networking that does not use any centralized database.

Gnunet mainly focuses on anonymous censorship-resistant file-sharing, which provides anonymity by
. making messages originating from a peer indistinguishable from messages that the peer is routing
. acting as routers and use link-encrypted connections with stable bandwidth utilization
It is similar to tor, but limited to share files anonymously, searching, swarming, and caching.

I2P는 2003년에 시작한 익명 네트워크로 낮은 지연율을 자랑한다. 설계 목표는 완전히 분산된, 확장 가능하고 익명의 견고하고 안전한 네트워크를 지향하고 있다. 모든 데이터는 여러 겹의 암호화 과정을 거쳐 종단간 암호화하는데, 이를 특히 Garlic Routing (마늘 라우팅)이라고 한다. tor의 양파 라우팅과 대조적으로 이름을 붙였고 실제 가상의 경로(터널)과 수많은 일방향 인바운드 아웃바운드 터널이 있는 노드로 구성된다. tor의 경우 하나의 라우팅 경로가 수립되면 양방향 통신에 사용하는 것에 비해 이는 일방향으로 송수신 터널이 다르다는 점이 특징이다. 중앙에서 관리하는 구조가 아니고 분산/동적 환경이며 제3의 신뢰자 역시 존재하지 않는다. 안전한 라우팅과 정보는 Kademlia라는 알고리즘 변형을 사용하는 내부 네트워크 데이터베이스를 보유하고 있다.

I2P has begun in 2003, which is an anonymizing network, a low latency mix network. According to the original designers, the goal is to to produce a low latency, fully distributed, autonomous, scalable, anonymous, resilient, and secure network. All data is wrapped with several layers of encryption. (End-to-End) This is called Garlic Routing. I2P is made up of a set of nodes (“routers”) with a number of unidirectional inbound and outbound virtual paths (“tunnels”).

The network is both distributed and dynamic, with no trusted parties and no centralized resources. Moreover it has its own internal network database (using a modification of the Kademlia algorithm) for distributing routing and contact information securely.

Anonymizing Activities: Tor (The Onion Routing)

사람들이 오프라인 상에서 자신만의 공간을 추구하듯이 온라인 상에서도 익명성을 요구하는 노력이 진행되었는데 대표적인 결과물이 tor(The Onion Routing)다. 토르는 인터넷 상에서 프라이버시와 보안을 향상시킬 수 있는 가상 터널 네트워크라고 정의하고 있다. (https://www.torproject.org/about/overview.html.en#overview)

  • 동작원리: 각 노드는 자신만의 키 쌍을 가지고 라우터 역할을 하는데 공개키로 라우팅 정보를 암호화하여 다음 노드는 이전 경로를 알 수 없도록 함
  • 마지막 노드(exit node)에서 데이터를 볼 수 있는데 이를 악용하는 경우도 있음
  • 익명성은 강화되지만 속도가 느리다는 단점이 있음
  • SOCKS와 HTTPS를 지원함
간단히 정리한 내용은 아래 링크를 참조하기 바란다.
Anonymizing Activities: Tor(The Onion Routing)

대표적으로 구현한 소프트웨어는 다음과 같다.

오래 전 Bruce Schneier은 자신의 블로그에서 관련된 공격(MITM)에 대해 논의된 바 있으며 공식 웹사이트에서도 익명성에 대한 공격 가능성을 언급한다.

또한 tor 경유지 노드 또는 마지막 노드 현황은 아래 링크에서 찾을 수 있으니 참고하자.

As people pursue their own privacy at offline, many attempts have been made to keep anonymity online as well. Tor(The Onion Routing) is one of them. Tor is defined as “a network of virtual tunnels that allows people and groups to improve their privacy and security on the Internet.” according to the torproject.org website.
Each node has its own public/private key pair, and the next node does not know where the packets come from by encrypting routing information. However make sure that the exit node to the destination could be compromised by malicious user. It is true that tor considerably improves anonymity but the speed of connection would somewhat slow down. It supports SOCKS and HTTPS.