tor-parallel-relay-conn/doc/tor-design.tex

\documentclass[times,10pt,twocolumn]{article}
%\usepackage{/home/syverson/papers/latex8}
%\usepackage{/home/syverson/papers/times}
\usepackage{latex8}
\usepackage{times}
\usepackage{url}
\usepackage{graphics}
\usepackage{amsmath}

\pagestyle{empty}

\renewcommand\url{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
\newcommand\emailaddr{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}

% If an URL ends up with '%'s in it, that's because the line *in the .bib/.tex
% file* is too long, so break it there (it doesn't matter if the next line is
% indented with spaces). -DH

%\newif\ifpdf
%\ifx\pdfoutput\undefined
%   \pdffalse
%\else
%   \pdfoutput=1
%   \pdftrue
%\fi

\begin{document}

%% Use dvipdfm instead. --DH
%\ifpdf
%  \pdfcompresslevel=9
%  \pdfpagewidth=\the\paperwidth
%  \pdfpageheight=\the\paperheight
%\fi

\title{Tor: Design of a Next-Generation Onion Router}

\author{Anonymous}
%\author{Roger Dingledine \\ The Free Haven Project \\ arma@freehaven.net \and
%Nick Mathewson \\ The Free Haven Project \\ nickm@freehaven.net \and
%Paul Syverson \\ Naval Research Lab \\ syverson@itd.nrl.navy.mil}

\maketitle
\thispagestyle{empty}

\begin{abstract}
We present Tor, a connection-based low-latency anonymous communication
system which addresses many limitations in the original onion routing design.
Tor works in a real-world Internet environment,
requires little synchronization or coordination between nodes, and
protects against known anonymity-breaking attacks as well
as or better than other systems with similar design parameters.
\end{abstract}

%\begin{center}
%\textbf{Keywords:} anonymity, peer-to-peer, remailer, nymserver, reply block
%\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Section{Overview}
\label{sec:intro}

Onion routing is a distributed overlay network designed to anonymize
low-latency TCP-based applications such as web browsing, secure shell,
and instant messaging. Users choose a path through the network and
build a \emph{virtual circuit}, in which each node in the path knows its
predecessor and successor, but no others. Traffic flowing down the circuit
is sent in fixed-size \emph{cells}, which are unwrapped by a symmetric key
at each node, revealing the downstream node. The original onion routing
project published several design and analysis papers
\cite{or-journal,or-discex,or-ih,or-pet}. While there was briefly
a network of about a dozen nodes at three widely distributed sites,
the only long-running and publicly accessible
implementation was a fragile proof-of-concept that ran on a single
machine. Many critical design and deployment issues were never implemented,
and the design has not been updated in several years.
Here we describe Tor, a protocol for asynchronous, loosely
federated onion routers that provides the following improvements over
the old onion routing design:

\begin{itemize}

\item \textbf{Perfect forward secrecy:} The original onion routing
design is vulnerable to a single hostile node recording traffic and later
forcing successive nodes in the circuit to decrypt it. Rather than using
onions to lay the circuits, Tor uses an incremental or \emph{telescoping}
path-building design, where the initiator negotiates session keys with
each successive hop in the circuit. Onion replay detection is no longer
necessary, and the network as a whole is more reliable to boot, since
the initiator knows which hop failed and can try extending to a new node.

\item \textbf{Applications talk to the onion proxy via Socks:}
The original onion routing design required a separate proxy for each
supported application protocol, resulting in a lot of extra code (most
of which was never written) and also meaning that a lot of TCP-based
applications were not supported. Tor uses the unified and standard Socks
\cite{socks4,socks5} interface, allowing us to support any TCP-based
program without modification.

\item \textbf{Many applications can share one circuit:} The original
onion routing design built one circuit for each request. Aside from the
performance issues of doing public key operations for every request, it
also turns out that regular communications patterns mean building lots
of circuits can endanger anonymity \cite{wright03}. Tor multiplexes many
connections down each circuit, but still rotates the circuit periodically
to avoid too much linkability.

\item \textbf{No mixing or traffic shaping:} The original onion routing
design called for full link padding both between onion routers and between
onion proxies (that is, users) and onion routers \cite{or-journal}. The
later analysis paper \cite{or-pet} suggested \emph{traffic shaping}
to provide similar protection but use less bandwidth, but did not go
into detail. However, recent research \cite{econymics} and deployment
experience \cite{freedom2-arch} indicate that this level of resource
use is not practical or economical; and even full link padding is still
vulnerable to active attacks \cite{defensive-dropping}.

\item \textbf{Leaky pipes:} Through in-band signalling within the circuit,
Tor initiators can direct traffic to nodes partway down the circuit. This
allows for long-range padding to frustrate timing attacks at the initiator
\cite{defensive-dropping}, but because circuits are used by more than
one application, it also allows traffic to exit the circuit from the
middle -- thus frustrating timing attacks based on observing exit points.
%Or something like that. hm.

\item \textbf{Congestion control:} Earlier anonymity designs do not
address traffic bottlenecks. Unfortunately, typical approaches to load
balancing and flow control in overlay networks involve inter-node control
communication and global views of traffic. Our decentralized ack-based
congestion control maintains reasonable anonymity while allowing nodes
at the edges of the network to detect congestion or flooding attacks
and send less data until the congestion subsides.

\item \textbf{Directory servers:} Rather than attempting to flood
link-state information through the network, which can be unreliable and
open to partitioning attacks or outright deception, Tor takes a simplified
view towards distributing link-state information. Certain more trusted
onion routers also serve as directory servers; they provide signed
\emph{directories} describing all routers they know about, and which
are currently up. Users periodically download these directories via HTTP.

\item \textbf{End-to-end integrity checking:} Without integrity checking
on traffic going through the network, an onion router can change the
contents of cells as they pass by, e.g. by redirecting a connection on
the fly so it connects to a different webserver, or by tagging encrypted
traffic and looking for traffic at the network edges that has been
tagged \cite{minion-design}.

\item \textbf{Robustness to node failure:} router twins

\item \textbf{Exit policies:}
Tor provides a consistent mechanism for each node to specify and
advertise an exit policy.

\item \textbf{Rendezvous points:}
location-protected servers

\end{itemize}

We review previous work in Section \ref{sec:background}, describe
our goals and assumptions in Section \ref{sec:assumptions},
and then address the above list of improvements in Sections
\ref{sec:design}-\ref{sec:maintaining-anonymity}. We then summarize
how our design stands up to known attacks, and conclude with a list of
open problems.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Section{Threat model and background}
\label{sec:background}

anonymizer
pipenet
freedom
onion routing
isdn-mixes
crowds
real-time mixes, web mixes
anonnet (marc rennhard's stuff)
morphmix
P5
gnunet
rewebbers
tarzan
herbivore

\SubSection{Known attacks against low-latency anonymity systems}



We discuss each of these attacks in more detail below, along with the
aspects of the Tor design that provide defense. We provide a summary
of the attacks and our defenses against them in Section \ref{sec:attacks}.

\Section{Design goals and assumptions}
\label{sec:assumptions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Section{The Tor Design}
\label{sec:design}


\Section{Other design decisions}

\SubSection{Exit policies and abuse}
\label{subsec:exitpolicies}

\SubSection{Directory Servers}
\label{subsec:dir-servers}

\Section{Rendezvous points: pseudonyms with responder anonymity}
\label{sec:rendezvous}

\Section{Maintaining anonymity sets}
\label{sec:maintaining-anonymity}

\SubSection{Using a circuit many times}
\label{subsec:many-messages}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Section{Attacks and Defenses}
\label{sec:attacks}

Below we summarize a variety of attacks and how well our design withstands
them.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Section{Future Directions and Open Problems}
\label{sec:conclusion}

Tor brings together many innovations from many different projects into
a unified deployable system. But there are still several attacks that
work quite well, as well as a number of sustainability and run-time
issues remaining to be ironed out. In particular:

\begin{itemize}
\item foo
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Section{Acknowledgments}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{latex8}
\bibliography{minion-design}

\end{document}

% Style guide:
%     U.S. spelling
%     avoid contractions (it's, can't, etc.)
%     'mix', 'mixes' (as noun)
%     'mix-net'
%     'mix', 'mixing' (as verb)
%     'Mixminion Project'
%     'Mixminion' (meaning the protocol suite or the network)
%     'Mixmaster' (meaning the protocol suite or the network)
%     'middleman'  [Not with a hyphen; the hyphen has been optional
%         since Middle English.]
%     'nymserver'
%     'Cypherpunk', 'Cypherpunks', 'Cypherpunk remailer'
%
%     'Whenever you are tempted to write 'Very', write 'Damn' instead, so
%     your editor will take it out for you.'  -- Misquoted from Mark Twain