commit 45d6743548f56d63ece3d1e13abb047f78cd8151
Author: Karsten Loesing <karsten.loesing(a)gmx.net>
Date: Thu Oct 29 18:58:18 2015 +0100
Add Nick's dos-taxonomy report.
---
2015/dos-taxonomy/.gitignore | 5 +
2015/dos-taxonomy/Makefile | 31 +++
2015/dos-taxonomy/dos-taxonomy.md | 498 +++++++++++++++++++++++++++++++++++++
2015/dos-taxonomy/tex_header.tex | 38 +++
2015/dos-taxonomy/tortechrep.cls | 1 +
5 files changed, 573 insertions(+)
diff --git a/2015/dos-taxonomy/.gitignore b/2015/dos-taxonomy/.gitignore
new file mode 100644
index 0000000..f16048a
--- /dev/null
+++ b/2015/dos-taxonomy/.gitignore
@@ -0,0 +1,5 @@
+dos-taxonomy.html
+dos-taxonomy.pdf
+dos-taxonomy-2015-10-29.pdf
+dos-taxonomy.tex
+
diff --git a/2015/dos-taxonomy/Makefile b/2015/dos-taxonomy/Makefile
new file mode 100644
index 0000000..fa8e85f
--- /dev/null
+++ b/2015/dos-taxonomy/Makefile
@@ -0,0 +1,31 @@
+.PHONY : main
+
+MAIN=dos-taxonomy
+LATEX=pdflatex
+MARKDOWN=maruku
+
+all: paper html tidy
+
+html: $(MAIN).md
+ $(MARKDOWN) $(MAIN).md
+
+$(MAIN).tex.tmp: $(MAIN).md
+ $(MARKDOWN) --tex $(MAIN).md -o $(MAIN).tex.tmp
+
+$(MAIN).tex: $(MAIN).tex.tmp tex_header.tex
+ cat tex_header.tex > $(MAIN).tex
+ perl -ne 'BEGIN{$$P=0;} print if $$P; if (/begin.document/) {$$P=1;} ' $(MAIN).tex.tmp >> $(MAIN).tex
+
+paper: $(MAIN).pdf
+
+$(MAIN).pdf: $(MAIN).tex
+ $(LATEX) $(MAIN)
+ # bibtex $(MAIN)
+ $(LATEX) $(MAIN)
+ $(LATEX) $(MAIN)
+
+tidy:
+ rm -f *.dvi *.aux *.log *.nav *.snm *.toc *.out *.vrb *.bbl *.blg $(MAIN).tex.tmp
+
+clean:
+ rm -f *.dvi *.aux *.log *.nav *.snm *.toc *.out *.vrb *.bbl *.blg $(MAIN).ps $(MAIN).pdf $(MAIN).tex $(MAIN).tex.tmp
diff --git a/2015/dos-taxonomy/dos-taxonomy.md b/2015/dos-taxonomy/dos-taxonomy.md
new file mode 100644
index 0000000..6d3c6e3
--- /dev/null
+++ b/2015/dos-taxonomy/dos-taxonomy.md
@@ -0,0 +1,498 @@
+
+Introduction
+------------
+
+This document surveys what we know about potential denial-of-service
+attacks against Tor, in order to focus our efforts over the coming years
+to increase Tor's resistance against these attacks.
+
+Why? We spend a lot of time thinking about anonymity defenses and
+security defenses, and less about DoS defenses. And while actual DoS
+attacks up to present have been (with a couple of exceptions)
+comparatively unsophisticated, we should not let our approach to them
+become reactive: instead we should systematize our approach to defending
+Tor against these attacks, and take a proactive stance towards them.
+
+Denial of service attacks are a special problem for anonymity networks,
+since many of them can be adapted to weaken anonymity. Bugs
+that would simply be annoying resource exhaustion issues against other
+network programs can be a real threat to user security.
+
+Here we provide an overview of denial-of-service vectors against
+anonymity networks in general and Tor in particular, and discuss how
+best to prioritize responses against them.
+
+We'll conclude below that our best focus in each area is to look for
+categorical defenses and protocol improvements, to better resist
+more categories of attacks before they occur.
+
+
+Methodology
+-----------
+
+There are quite a few ways to classify DoS attacks: by the exhausted
+resource, by the kind of service targeted, by the required
+attacker resources, by the required attacker expertise, etc.
+
+Here we are considering each attack in terms of how well the attack
+achieves the attacker's goals. For each attack we will consider:
+
+ * How difficult the attack is to perform.
+ * How difficult it is to exploit the attack to achieve particular
+ outcomes.
+ * How repeatable the attack is over time. (How hard it is to detect;
+ how hard it is to prevent once detected.)
+ * The difficulty of mitigating this sort of attack.
+
+Results and Taxonomy
+--------------------
+
+### Attacks by resource ###
+
+#### CPU consumption attacks ####
+
+Onion routing servers perform expensive cryptographic computations on behalf of
+their users. Additionally, some computations internal to the Tor process
+use inefficient algorithms (like linear searches), which might
+prove problematic if those algorithms' inputs prove large.
+
+An attacker could mount CPU consumption attacks by running a large
+number of legitimate clients and shoving traffic through them.
+That's comparatively simple to do, but comparatively expensive.
+
+Worse, an attacker could construct bogus cryptographic requests that
+require relays to perform a lot of computation before realizing that
+the request was spurious. An attacker can also mount CPU
+consumption attacks by finding an inefficient algorithm in and
+provoking it to be used far more than it would be in ordinary
+operation. These attacks need a little engineering and programming
+skill, but create a higher impact for a given amount of computation.
+
+CPU exhaustion attacks can reduce the CPU resources available for
+legitimate operations. They can also interfere with other traffic,
+thereby creating patterns in users' streams that can be observed
+elsewhere in the network.
+
+CPU exhaustion attacks are usually noticeable only when
+done blatantly. If a large number of nodes suddenly see their
+CPU load spike, or if usage slows to a crawl across the whole
+network, we'll get reports of it-- but small
+interference with targeted relays or nodes is harder to
+detect.
+
+To defend against CPU exhaustion attacks, our best responses are:
+
+ * To improve the efficiency of our implementation in places where
+ it uses inefficient algorithms.
+
+ * To move more work from the main thread into other threads,
+ thereby increasing other threads.
+
+ * To modify our protocols so that an attacker cannot spend a small
+ amount of CPU in order to force the server to use a lot.
+
+ * To radically improve our work- and cell-scheduling architectures
+ so that it is harder for one user's traffic to interfere with
+ another's.
+
+ * Possibly, to instrument our code so that we can better detect
+ strange patterns in CPU usage. We'd need privacy-preserving
+ ways to do this.
+
+#### RAM consumption attacks ####
+
+Tor servers will, for many purposes, allocate memory in order to fulfil
+un-trusted requests. Operations that allocate memory are below. Ones
+that Tor currently handles in its OOM-handler (see below) are marked
+with HANDLED.
+
+ * Queueing cells on a circuit for transmission. (HANDLED)
+ * Queueing data to be sent on an edge connection. (HANDLED)
+ * Storing hidden service directory entries. (HANDLED)
+ * Queueing directory data for compression. (HANDLED)
+ * Internal OpenSSL buffers. (HANDLED.)
+
+ * Storing uploaded descriptors as a directory authority. (!)
+ * Key-pinning entries on directory authorities. (!)
+ * Cached DNS replies. (!)
+
+ * Replay caching on hidden services.
+ * Storing votes from other directory authorities.
+ * Storing statistics as a statistics-collecting node.
+ * Per-circuit storage.
+ * Per-connection storage.
+ * Per-stream storage.
+ * Queued circuit-creation requests.
+
+
+For cases when Tor knows how to handle memory pressure in a given
+area, it keeps track of the amount allocated, and responds to memory
+pressure by killing off long-unused connections and circuits.
+
+When Tor has not been taught to handle memory pressure in a
+particular area, it runs a risk of running out of memory in response
+to attacks. Whens the Tor process uses too much memory, the OS will
+respond in one of two ways:
+
+ 1. On some operating systems, memory allocation functions will
+ return NULL. Tor responds to this currently by aborting the
+ process.
+
+ 2. On Linux, the kernel kills processes when the system runs low
+ on memory, using a set of heuristics that pleases nobody.
+
+Memory exhaustion attacks per se are comparatively inexpensive: the most
+usual types require the attacker to transmit only one encrypted byte
+per byte consumed on the target. (Tor already takes steps to prevent the
+even cheaper versions, where the attacker uploads a compressed zlib bomb.)
+
+The impact of a memory exhaustion attack can be blatant (crashing the
+Tor process, see below), or subtle (triggering the Tor process's
+internal OOM handler and causing _other_ circuits or connections to get
+closed, or information to get dropped). We'll focus on subtle
+exhaustion here; for analysis on crashes, see the next section.
+
+Memory exhaustion attacks usually require a little programming
+skill to exploit, and more if the goal is more subtle than shutting
+down a server.
+
+The most promising ways to resist memory-exhaustion DoS attacks are:
+
+ * Include more types of memory (see list above) among those that
+ the OOM handler is able to free on demand. Those marked with
+ (!) seem most valuable to do first.
+
+ * Extend our OOM handler to be triggered by raw memory
+ allocation or by detectable OOM events. This would allow it to
+ _respond_ to every kind of RAM exhaustion attack, though it
+ would not necessarily be able to correct every time.
+
+More difficult methods would include:
+
+ * Improve our OOM handler to offload offending information to
+ disk rather than deleting it entirely.
+
+ * Analyze memory leak bugs discovered in the past,
+ looking for patterns. Preliminary analysis suggests
+ that our biggest antipatterns here are:
+
+ * Forgetting to call free;
+
+ * Using any kind of memory management more complicated
+ than alloc/free pairs;
+
+ * Forgetting to run Coverity right before a release.
+
+#### Crash attacks ####
+
+Due to programming errors, there may be as-yet-unknown ways to shut down Tor
+and/or other programs remotely, either with a memory violation, with an
+assertion failure, or with RAM exhaustion.
+
+Generally, these require that the attacker discover a programming
+flaw in the program. So long as Tor is actively maintained, these
+attacks can't be used too often without being detected, since they
+usually leave a trace of why servers are crashing--either as a
+stack trace in the log, or an assertion failure message, or both.
+Thus, they require an up-front investment with a limited shelf life.
+
+Nevertheless, these attacks are problematic when they have the ability
+to force a user to change guards (see the Sniper Attack paper by Jansen
+et al.); to mount traffic confirmation attacks; or to attack anonymity
+in other ways as well.
+
+To resist these attacks better we could:
+
+ * Further improve our guard node selection algorithms to resist
+ multiple induced guard failures.
+
+ * Consider designs that would allow circuits and their traffic to
+ migrate across different nodes, so as to better survive the
+ collapse of a single node. (HARD!)
+
+ * Get stack trace support working on Windows, so we can better
+ detect patterns in Windows crashes.
+
+ * Use fewer assertions, and more circuit-level or
+ connection-level error handling.
+
+ * Introduce patterns for handling unexpected bugs more
+ gracefully, possibly modeling them on the BUG_ON() etc macros
+ used by the Linux kernel.
+
+ * Analyze memory crash bugs discovered in the past, and search for
+ trends to identify more. Preliminary analysis suggests that our
+ most crash-prone code has historically been:
+ * Parsing text-based formats.
+ * Parsing binary formats.
+ * Failing to enforce checks in one part of the code that are
+ later enforced with an assertion.
+ * Hand-coded state machines with unexpected transition modes.
+ * Extending the type of an existing field (especially IPv4->IPv6)
+ and elsewhere asserting that the field is the original type.
+ * High-complexity functions, especially ones with "you must
+ call A after B" dependencies.
+ * Code not currently tested by our integration tests.
+
+#### Disk space exhaustion attacks ####
+
+Attacks of this kind are most threatening to systems with extremely
+low disk capacity. To carry one out, an attacker needs a way to
+force the target to store an unbounded amount of information.
+
+Directory authorities are also a concerning target for disk exhaustion
+attacks, since they store published relay descriptors on request.
+To mount a disk exhaustion attack against a non-authority Tor process, an
+attacker would need either to compromise enough authorities to make
+the directory grow without bound, to run enough legitimate-looking
+nodes to make the directory grow without bound, to find an
+unsuspected bug in Tor's code, or to fill up the disk with log
+messages.
+
+Our best defenses here are:
+
+ * Work harder to make directory authorities throw away
+ descriptors if they become low on disk space.
+
+ * Ensure that all of our packages use log rotation.
+
+ * Respond to low disk space by diminishing the amount of storage
+ we use.
+
+#### Bandwidth consumption attacks ####
+
+These attacks are among the most fundamental. A Tor server's job,
+after all, is to receive bytes, transform them, and retransmit
+them. Simply by sending data to a Tor server, an attacker forces
+that server to receive and retransmit the data.
+
+Servers defend themselves against some of these attacks already: by
+declining to accept data on circuits whose buffers are already too
+full, and by using fairness metrics to ensure that quieter circuits
+receive priority service.
+
+The potential impact of one of these attacks can be degraded service
+from a targeted server. But the most dangerous aspect is that it
+can interfere with other traffic, introducing patterns to it that
+can be observed remotely.
+
+Mounting these attacks requires only a botnet running traffic generation
+code. Exploiting interference is a little trickier, and requires a bit
+of engineering.
+
+The highest-impact bandwidth consumption attacks are those with a
+bandwidth multiplier: that is, those in which an attacker can spend
+only a little bandwidth (and minimal CPU) in order to force the
+server to spend a lot. These include directory fetches, HTTP
+requests, and any other traffic pattern where a small request
+generates a large response.
+
+These attacks are difficult to detect in practice.
+
+Our most promising ways to prevent or mitigate these attacks
+include:
+
+ * Possibly, when bandwidth is scarce, consider prioritizing 1:1
+ traffic over asymmetric traffic.
+
+ * Implement KIST (or something like it) to become more responsive
+ to TCP congestion.
+
+ * Implement a scheme like DonnchaC's "split
+ introduction/ rendezvous" proposal (#255) in order to make it
+ harder to congest a hidden service's bandwidth.
+
+ * Improve TorFlow (or another bandwidth scanning system) to
+ follow less predictable patterns for bandwidth scanning.
+
+ * As above, consider schemes to allow busy circuits to migrate
+ from one path to another.
+
+#### Socket/port usage attacks ####
+
+TCP reserves around 64000 usable ports per IP address. In practice, the
+operating system will often have us use many fewer sockets than this.
+By exhausting the available port count, an attacker can prevent a server
+from opening new connections to other servers, prevent an exit server
+from making new exit connections, or prevent a hidden service from
+serving additional users.
+
+These attacks are less easy to turn into a deanonymization vector
+than others, except that by reducing service at a guard or exit
+server, an attacker can force its users to use another. The attacker
+does not control the next server chosen, though, so unless the client
+retries indefinitely, the attack has low odds of success.
+
+These attacks require a little engineering to perform optimally,
+but a less skilled attacker can make a skill/resource tradeoff.
+
+These attacks can be noticed, but are hard to distinguish
+(currently) from legitimate port/socket exhaustion.
+
+To defend against these attacks, we have a few options:
+
+ * Respond to socket/port exhaustion as we currently respond to
+ memory exhaustion: not only refusing to accept new connections,
+ but by looking for long-idle connections that might need to get
+ closed.
+
+ * When looking for connections to close, we could look for
+ suspicious patterns (many connections to the same address,
+ many outbound connections to relays not listed in the
+ consensus, etc). This could be a bad resource use, however,
+ since these patterns are easy to suppress in practice.
+
+ * Make better use of systems where we have multiple interfaces to
+ use for outbound connections.
+
+ * Make better use of multiple IPv6/IPv4 addresses on a single
+ relay, to increase the number of CPU ports we can use.
+
+ * Possibly, deploy some sort of UDP-based transport, to prevent
+ socket exhaustion from interfering with client-relay or
+ relay-relay connections.
+
+### Attacks by target ###
+
+In parallel to considering DoS attacks based on the resource
+exhausted, we can also distinguish them based on the sort of
+system that they target.
+
+#### Attacking clients ####
+
+Performing resource-based DoS attacks against Tor clients serves a
+couple of possible purposes:
+
+ * Traffic confirmation, by forcing a suspected client to degrade
+ performance or to leave the network entirely, and looking to
+ see whether other observed circuits degrade in a corresponding
+ way.
+
+ * Traffic shifting, by encouraging users to stop using Tor,
+ thereby receiving less cover themselves and providing less
+ cover than others.
+
+#### Attacking applications ####
+
+Performing a denial-of-service attack against a (client- or
+server-side) application can serve an attacker's goals by:
+
+ * Encouraging the client to shift to a less-anonymized
+ application
+
+ * Gaining a resource-multiplier effect by forcing the client
+ to introduce itself to more nodes on the Tor network.
+
+#### Attacking hidden services ####
+
+There are a few key opportunities to perform denial-of-service
+attacks against hidden services:
+
+ * Attacking (or becoming) hidden service directories, so clients
+ can't find how to contact a targetted HS.
+
+ * Attacking (or becoming) introduction points, so clients can't
+ make contact with a targetted HS
+
+ * Attacking a hidden service itself.
+
+Similarly, these attacks can be used either to degrade a HS's
+performance, or to attempt to mount traffic confirmation against it.
+
+#### Attacking relays ####
+
+Attacking a relay is at its most powerful when that relay is known
+to be the guard node for a user of interest, and at its next most
+powerful when an attacker is running a large number of their own
+relays and wants to shift traffic onto them.
+
+#### Attacking directory authorities ####
+
+The directory authorities, thanks to their special position in the
+Tor network, are an especially concerning attack for DoS attacks.
+Remove a few authorities, and the voting process becomes less
+robust; remove enough of them, and the entire network becomes
+inoperable.
+
+Our best approach here is separating authority functions and
+isolating their most sensitive duties from their most expensive.
+(Proposal 257 has more ideas on this topic.)
+
+#### Attacking other services via Tor ####
+
+By using the Tor network as a vector for performing
+denial-of-service attacks on other services, an attacker can
+encourage those services to block or restrict Tor users over time,
+thereby discouraging Tor usage. This attack can also make it more
+difficult to host exit nodes.
+
+The best known methodology for resisting these attacks is:
+
+ * Developing technology to restrict abusive Tor users without
+ blocking non-abusive ones, and encouraging the use of this
+ technology. (The present author is a fan of various anonymous
+ blacklistable credential systems, but they have yet to be used
+ in practice, and might prove too unwieldy when actually
+ deployed. We should also consider other approaches.)
+
+
+#### Attacking project infrastructure ####
+
+All attacks become stronger when engineers can't respond to them.
+If, instead of targetting the Tor network, an attacker targets the
+infrastructure that Tor developers use to coordinate, any other
+attack will be more powerful and successful.
+
+Our best response here is likely to ensure that we have backup means
+of coordination and communication prepared _before_ we need them.
+
+Similarly, an attack against user-facing project infrastructure
+could prevent us from communicating with users during an emergency,
+or prevent us from distributing updates effectively.
+
+To resist this kind of attack, we should grow our mirror
+capacity, and build an emergency response plan for a temporary DoS
+against our current software distribution methods.
+
+Recommendations
+---------------
+
+In general, we should favor defenses that close multiple
+attack vectors simultaneously over defenses that simply close one at a
+time. Remember: An attacker needs only one attack that works, while
+we need to prevent _every_ good attack.
+
+Therefore, we should look for general solutions and process
+improvements, rather than piecemeal responses to a single discovered
+attack at a time.
+
+Solutions with the potential to close many attack vectors at once
+include:
+
+ * Changes to the Tor network's structure to prevent single-server
+ attacks from aiding traffic confirmation attacks. These seem
+ particularly difficult, but quite powerful if we can come up
+ with a design that works.
+
+ * Changes to the directory authority infrastructure to remove
+ them (in part or entirely) as a viable DoS target.
+
+ * Changes in our coding practices to make it more difficult for
+ programming errors to propagate into large-scale DoS vectors.
+
+ * Changes in the code used to handle resource exhaustion should
+ look at the consumed resource directly rather than at indirect
+ counts of it. For example, our OOM-handler should look at the
+ operating system's view of our memory consumption, rather than
+ simply counting an incomplete set of memory consumers.
+
+ * Future revisions of our public-key algorithms should consider
+ resource-exhaustion attacks and resource asymmetries.
+
+ * Look for areas that have been historically problematic for
+ programming errors, and investigate ways to reduce future
+ errors of this kind.
+
+ * Isolate parts of the Tor process to different modules, and try
+ to make crashes or resource exhaustion in any particular part
+ as survivable as possible.
diff --git a/2015/dos-taxonomy/tex_header.tex b/2015/dos-taxonomy/tex_header.tex
new file mode 100644
index 0000000..b9ef0d6
--- /dev/null
+++ b/2015/dos-taxonomy/tex_header.tex
@@ -0,0 +1,38 @@
+\documentclass{tortechrep}
+\usepackage{url}
+\usepackage{graphicx}
+\usepackage{hyperref}
+\usepackage{longtable}
+\usepackage{paralist}
+
+%\usepackage{styles/pdfdraftcopy}
+%\draftcolor{gray20}
+%\draftstring{DRAFT}
+%\draftfontsize{150pt}
+
+\begin{document}
+
+\title{Denial-of-service attacks in Tor: Taxonomy and defenses}
+
+\author{Nick Mathewson\\The Tor Project\\ \href{mailto:nickm@torproject.org}{nickm@torproject.org} }
+%\footnotemark[\ref{tpi}]
+
+\reportid{2015-10-001}
+\date{October 29, 2015}
+
+\maketitle
+
+% Text conventions
+% - Each sentence ends with a newline, even inside a paragraph.
+% - Lines are at most 74 characters wide.
+% - Abbreviations are best avoided.
+% - Code, cell names, etc. are put inside \verb+...+.
+
+%\tableofcontents
+
+\begin{abstract}
+This document surveys what we know about potential denial-of-service
+attacks against Tor, in order to focus our efforts over the coming years
+to increase Tor's resistance against these attacks.
+\end{abstract}
+
diff --git a/2015/dos-taxonomy/tortechrep.cls b/2015/dos-taxonomy/tortechrep.cls
new file mode 120000
index 0000000..4c24db2
--- /dev/null
+++ b/2015/dos-taxonomy/tortechrep.cls
@@ -0,0 +1 @@
+../../tortechrep.cls
\ No newline at end of file
