Short Paper: Challenges in protecting Tor
hidden services from botnet abuse
Nicholas Hopper?
University of Minnesota, Minneapolis, MN USA
hopper@cs.umn.edu

1

Introduction

In August, 2013 the Tor anonymity network saw a rapid spike in the number of
directly connecting users, due to the large “mevade” click-fraud botnet runningits command and control (C&C) as a Tor Hidden Service. Figure 1(a) shows that
estimated daily clients increased from under 1 million to nearly 6 million in three
weeks. Figure 1(b) shows the effects on performance: measured downloading
times for a 50 KiB file doubled, from 1.5 seconds to 3.0 seconds.
However, the amount of traffic being carried by the network did not change
dramatically. The primary cause of the problems seems to be the increased processing load on Tor relays caused by the large increase in key exchanges required
to build anonymous encrypted tunnels, or circuits. When a Tor client connects tothe network, it sends a create cell to a Tor node, called a guard, which contains
the first message g a in a Diffie-Hellman key exchange, called an “onion skin”;
the node receiving the create cell computes the shared key g ab and replies withthe second message g b , creating a 1-hop circuit. After this, the client iteratively
sends onion skins in extend cells to the end of the circuit, which extracts theonion skins and sends them in create cells to the next relay, until all three hops
have exchanged keys.
– Extending a circuit – decrypting an “onion skin” and participating in a
Diffie-Hellman key exchange – is sufficiently compute expensive that busy
relays can become CPU-bound.
– The hidden service protocol – explained in section 2 – causes at least threecircuits to be built every time a bot connects.
– When onion skins exceed the processing capacity of a relay, they wait indecryption queues, causing circuit building latencies to increase.
– Queued onion skins eventually time out either at the relay or the client,causing the entire partial circuit to fail, causing more onion skins to be
injected to the network.
In response to this, the Tor Project released a modified version (0.2.4.17rc) that prioritizes processing of onionskins using the more efficient ntor [8] key
exchange protocol. Adoption of this release has helped the situation: as Figure 1 shows, measured download 50 KiB times as of late September decreased?

Work done while on sabbatical with the Tor Project5000000

4000000

3000000

2000000

1000000

0Time in seconds to complete 50 KiB request
Measured times on all sources
26−Aug02−Sep per day

19−Aug09−Sep16−SepMedianThe Tor Project− https://metrics.torproject.org/(a)
1st to 3rdquartile

4

3

2

1

0
19−Aug26−Aug02−Sep09−Sep16−Sep23−Sep30−Sep(b)

The Tor Project − https://metrics.torproject.org/

Fig. 1. (a) Estimated daily Tor users, and (b) Measured 50 KiB download times, inseconds, 18 August to 13 September 2013

to roughly 2.0 seconds. Figure 2 shows that failed circuit extensions using tor
version 0.2.4.17-rc range between 5% and 15%, while circuit extensions using thestable release, version 0.2.3.25, range between 5% and 30%.
In this paper, we consider long-term strategies to ease the load on the network and reduce the impact on clients, and describe the challenges in evaluating
and deploying these schemes. We assess these strategies with the security goal of
ensuring the availability of Tor under the threat of a botnet that uses hidden services as its primary C&C channel, keeping in mind that a “long-term” strategy
must contend with a botnet that could be deployed in response to these strategies, where the behavior of both the botnet and the Tor software can change
adaptively to circumvent mitigation mechanisms.

2

Background: Tor Hidden Services

The Tor network provides a mechanism for clients to anonymously provide services (e.g., websites) that can be accessed by other users through Tor. We briefly
review the protocol for this mechanism:
1. The hidden service (HS) picks a public “identity key” P KS and associatedsecret key SKS . The HS then computes an “onion identifier” oS = H(P KS )

0.4

0.2.4.17-rc
0.2.3.25

onionskin fail rate

0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
0

12 24 36 48 60 72 84 96 108 120 132
hour

Fig. 2. Hourly measured failure rates, starting 27 Sept. 2013, of extend cells

using a cryptographic hash function H. Currently, the hash function H isthe output of SHA1, truncated to 80 bits. This 10-byte identifier is base32encoded to produce a 16-byte .onion address that Tor users can use toconnect to HS, such as 3g2upl4pq6kufc4m.onion.
2. The HS constructs circuits terminating in at least three different relays, andrequests these relays to act as its introduction points (IPs).
3. The HS then produces a “descriptor,” signed using the SKS , that lists P KS
and its IPs. This descriptor is published through a distributed hash ring of
Tor relays, using oS and a time period τ as an index.
4. A client connects to the HS by retrieving the descriptor using oS and τ ,and building two circuits: one circuit terminates at an IP and the otherterminates at a randomly-selected relay referred to as the rendezvous point(RP). The client asks the IP to send the identity of the RP to the HS.
5. The HS then builds a circuit to the RP, which connects the client and HS.
Since lookups to the distributed hash ring are performed through circuits as well,and each descriptor has three redundant copies, a client connecting to a hidden
service could require building up to 6 circuits; to reduce this load, clients cachedescriptors and reuse rendezvous circuits any time a request is made less thanten minutes after the previous connection.

3

Can we throttle by cost?

Since the primary concern from the point of view of the other users of Tor is
the rate at which botnet nodes consume the collective computing resources of
the relays, one set of potential solutions is to attempt to throttle or otherwise
limit the rate of requests from the botnet. Two key points to recall in evaluating
solutions from this class are that (i) in many ways the botnet has more resources
available than the set of all regular Tor clients and (ii) neither bots nor the
C&C server are constrained to follow the standard Tor algorithms, although thecurrent implementations may do so.

One way to control the rate at which circuit building requests enter the
network is by making it costly to send them. Tor could do this by requiring
proof of the expenditure of a scarce resource, for example, human attention,
processor time, bitcoins, and so on. If the cost to build a circuit or connect toa hidden service can be correctly allocated it could be the case that ordinary
users and services can easily afford the cost while the price for a botnet becomesprohibitive. Depending on the resource used, correctly allocating the cost is an
important research question; we consider the problem for Proof of Work (CPUbased) and CAPTCHA (human attention-based) systems below.
Besides the cost allocation problem, another technical challenge is ensuringthat resources can’t be double-spent, so that each resource expenditure in agiven time period only authorizes a single circuit or hidden service connection.
Several approaches exist, but each would require further investigation:– Make the unit of pay cover a single circuit extension and have one of therelays extending the circuit issue a challenge back to the client, which thenmust be answered before the create (or extend) cell is processed, similar
to the scheme described by Barbera et al. [3]. This has the unfortunate side
effect of adding an extra round-trip time to every circuit-building request.
Finding a way to hide this extra round-trip time could make it a viable
alternative, for some resources.
– Relay descriptors could include “puzzle specifications” that describe what
the challenge will be for a given time period, requiring a method to prevent“precomputing” a batch of payments before the time period; how to solve
this problem is an open question.
– Another method would use an extra trusted server that verifies resource
expenditures and issues relay- and time period-specific signed tokens, similar to ripcoins [12] or the tokens in BRAIDS [10]. Using blinded tokens
would limit the trust required in the server so that it can’t compromiseanonymity, and relay-specificity would allow each relay to verify that tokens
aren’t double-spent. However, this adds an extra signature-verification to
the task of onion-skin processing and another server and key that must be
maintained.
Proof of work (proves once more not to work?) When the resource inquestion is processor time and challenges are, e.g. hashcash [2] targets, the costallocation strategy should dictate that the hidden service must pay a cost foreach connection, since bots clients and normal hidden service clients will haveessentially identical use profiles (from the point of view of relays) and computational resources. On the other hand, the C&C hidden server(s) will collectively
initiate many more circuits than any single “normal” hidden server.
The key security challenge when considering an adaptive botmaster’s response to this approach is the “chain-proving” attack (by analogy to chain voting [11]). In this attack, the C&C server solves the first challenge it receives
when a bot contacts the hidden service, but then on each additional challenge,
the previous bot is asked to solve the puzzle in time to allow the next bot toconnect. In principle the difference in latencies (caused by the need to pass a
puzzle to the bot through Tor) could potentially be detected, but an adaptive
botmaster could well build shorter circuits, and employ multiple bots in an effort
to reduce the time needed to solve a “proof of work” puzzle.

CAPTCHAs If CAPTCHAs are used to verify expenditure of human attention, the relative cost allocation should change to favor the client: clients of most
hidden services will have human users, while hidden servers will not. This raises
additional technical problems, such as how CAPTCHAs can be served throughTor without a GUI interface, how a user’s solution can be transferred to thehidden service without violating privacy or allowing overspending, and how todeal with the needs of completely headless services where neither the HS client
nor the HS server have a user’s attention to give.
Another technical challenge to deploying CAPTCHAs is how to defeat computationally expensive automated solvers. Most commercially-deployed CAPTCHAs
can be solved with success rates on the order of 10% per challenge [7, 1], andthe typical service mitigates this by temporarily blacklisting an IP address after a small number of attempts. With anonymous users, this becomes a morechallenging problem to solve; without blacklisting a bot can simply attempt as
many CAPTCHAs as necessary to obtain an automated solution.

4

Can we throttle at the entry guard?

A more direct approach would be to simply have guard nodes rate-limit the
number of extend cells they will process from a given client. If the entry guard
won’t process the extend cell needed to build a circuit, the hidden server can’t
flood the network with onion-skins. Notice that this measure won’t prevent botsfrom flooding the network with circuit requests; it simply makes the network
ineffective from the botmaster’s standpoint and thus, motivates botmasters tofind some other C&C channel that causes less stress on the Tor network.
Effective circuit throttling at the guard node faces a number of challenges,
however. Biryukov et al [4] found that the most popular hidden services see over1000 requests per hour; if we assume that these hidden services won’t modify
Tor’s default behavior, then guard nodes need to allow each client to extend
over 300 circuits per hour; but since there are currently over 1200 relays acting
as guards, a single C&C server run by an adaptive botmaster could build 360
000 circuits per hour at this rate. We could decrease the cap and try to make iteasier for busy hidden servers to increase their guard count, but this significantly
increases the chance that a hidden server chooses a compromised guard and canbe deanonymized.
One possibilty would be to use assigned guards. In this approach, ordinaryclients would pick guards as usual, and guards would enforce a low rate-limitBulk 5 MiB Clients Last Byte

0.8
0.6
0.4
0.2
0.0

regularbotnetthrottle

0

Circuit Build Times

1.0
Cumulative Fraction

Cumulative Fraction

1.0

0.8
0.6
0.4
0.2
0.0

100 200 300 400 500 600 700
Download Time (s)0regularbotnetthrottle

5

10
15
20
Time to Build Circuit (s)(a)

8Total Failed (10 s ma)

Total Read (MiB/s)(b)

Network Data Read Over Time

10

6
4
2
0

0

regularbotnetthrottle

10

20

30
40
Tick (m)
(c)

25

50

60

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
0

Circuits Failed Per Second

regularbotnetthrottle

10

20

30
40
Tick (m)

50

60

(d)

Fig. 3. Results of guard throttling: 20 relays, 200 clients, 500 bots. (a) 5MiB download
times, (b) Circuit build times, (c) Total bytes read (d) circuit failuresrdefault on circuit extensions, for example 30 circuits per hour. 1 Clients thatneed to build circuits at a higher rate rserver – say, 2000 per hour – could follow
a cryptographic protocol that would result in a verifiable token that assigns a deterministic, but unpredictable, guard node for the OP when running on a given
IP address. These OPs could then show this token to the assigned guard andreceive a level of service sufficient for a busy hidden server, but not for a floodof circuit extensions. An example of this type of protocol appears as Protocol
3 (section 3.3) in the BRAIDS design by Jansen et al. [10]. The rates rdefault
and rserver could appear in the network consensus, to allow adjustments for thevolume of traffic in the network. Figure 3 shows the result of simulating thisstrategy with rdefault = 10 and rserver = 2000 using the shadow simulator [9]; despite nearly identical bandwidth usage, the throttled simulation has performance
characteristics similar to the simulation with no botnet.
An additional technical challenge associated with guard throttling is the needto enforce the use of entry guards when building circuits. If the C&C server joins
the network as a relay, create cells coming from the hidden service would be
1

Naturally, finding the right number to use for this default rate is also an interesting
research challenge: a very low rate-limit could prevent bots from flooding the network
but might also disrupt legitimate hidden service clients

indistinguishable from create cells coming from other circuits running throughthe relay, effectively circumventing the rate limit. In principle this could be
detected by a distributed monitoring protocol, but designing secure protocolsof this type that avoid adversarial manipulation has proven to be a difficult
challenge.

5

Can we reuse failed partial circuits?

Part of the problem caused by the heavy circuit-building load is that when acircuit times out, the entire circuit is destroyed. This means that for every failed
create, at least three new create cells will be added to the network’s load.
If we model the entire Tor network as having probability p of having a create
cell timeout, then the expected number of create cells needed to successfullybuild a circuit will be the X0 satisfying the linear system:
X0 = pX0 +(1 − p)X1
+1
X1 = pX0+(1 − p)X2 +1
X2 = pX0+1 ,where Xi is the expected number of cells to complete a partial circuit with i
2
−3p+3
.
hops. This gives us X0 = p(1−p)
3Fig. 4. Expected onion-skin load per circuit created, for failure rate p

Conceptually, we can reduce this load by re-using a partially-built circuit, e.g.
when a timeout occurs, we truncate the circuit and attempt to extend from thecurrent endpoint. In this case, the expected number of create cells needed to3. Figure 4 shows plots of both functions.
build a circuit will be simply X00 = 1−p
We can see that for high enough failure rates, this change causes a substantial
reduction in load for the network. Figure 2 shows typical failure rates for a stable(TAP) and release candidate (ntor) roughly one month after the beginning of
the botnet event; we can see that at the observed failure rates ranging from 10%25%, reusing partial circuits would reduce the load on the network by 10-30%.

Of course, this model ignores the fact that failure probabilities are neither
static nor uniform across the entire Tor network, and the fact that many nodes
use “create fast” cells to exchange a first-hop key without using Diffie-Hellman
key exchange. Reducing the load introduced by failures will also reduce therate of circuit failures overall, but since CPU capacities vary widely across the
Tor network (and load balancing is by the essentially uncorrelated bandwidthof nodes) the size of the actual effect due to this change is difficult to predict.
Further evaluation will be needed. Additionally, this change would also somewhat
increase the power of selective denial of service attacks [6], although such attacks
typically only become noticeably effective in situations where we would alreadyconsider Tor to be compromised.

6

Can we isolate Hidden Service circuits?

Another approach to protect the regular users of the Tor network from resource
depletion by a hidden-service botnet would be to isolate hidden service onion-skinprocessing from ordinary processing. By introducing a mechanism that allows
relays to recognize that an extend or create cell is likely to carry hidden
service traffic, we could provide a means to protect the rest of the system fromthe effects of this traffic, by scheduling priority or simple isolation.
An example of how this might work in practice is to introduce new nohsextend/nohs-create cell types with the rule that a circuit that is created with
an nohs-create cell will silently drop a normal extend cell, or any of the cell
types associated with hidden services. If relays also silently drop nohs-extend
cells on circuits created with ordinary create cells, then nohs-create circuits are guaranteed not to carry hidden service traffic. Updated clients would
then create all circuits with nohs-create unless connecting to a hidden service. When a sufficient number of clients and relays update their Tor version,a consensus flag could be used to signal relays to begin isolating processing of
ordinary create cells. For example, these cells might only be processed in thelast 20ms of each 100ms period, leaving 80% of processing capacity available forregular traffic. The flag could be triggered when hidden service circuits exceed
a significant fraction of all circuits in the network.2
This solution protects the network and typical users from a massive botnet
hidden service, but would, unfortunately, intensify the effect on users of legitimate hidden services in time periods when an attack was detected. As withguard throttling, the intended effect would thus be to encourage botmasters todevelop C&C channels that do not stress the Tor hidden service ecosystem, whileproviding stronger protection against botnet clients flooding the network.
One privacy concern related to this approach is that as the network upgrades
to versions of Tor supporting nohs-create, identification of hidden-service traffic approaches deterministic certainty. By contrast, current hidden service circuits follow traffic patterns that allow them to be identified with high statistical2

Detecting this condition in a privacy-preserving manner represents another technicalchallenge requiring further research.

confidence [5] only. Because (excluding botnet traffic) the base rates of hidden
service traffic compared to all other traffic are low, this will also decrease theprivacy of hidden service users. One potential mitigation mechanism would be tohave clients only use nohs-create when the consensus flag for hidden service
isolation is activated, which would indicate that hidden service clients would
already have a large anonymity set.

7

Conclusion

Although this document has described several possibilities that either limit theattractiveness of Tor Hidden Services as a mechanism for C&C communication
or limit the impact of these services on other users of Tor, all of the approaches
present research challenges for the security community in some way. We hopethat this short paper will encourage new research in this direction.

8

Acknowledgements

Thanks to Mike Perry, Ian Goldberg, and Roger Dingledine for helpful comments
about the problems discussed in this paper. This work was supported by the U.S.
National Science Foundation under grants 1111734 and 1314637 and DARPA.

References
1. Ahmad, A.S.E., Yan, J., Tayara, M.: The robustness of google CAPTCHAs. Technical Report Computing Science Technical Report CS-TR-1278, Newcastle University (2011)
2. Back, A., et al.: Hashcash-a denial of service counter-measure (2002)
3. Barbera, M.V., Kemerlis, V.P., Pappas, V., Keromytis, A.: CellFlood: Attacking
Tor onion routers on the cheap. In: Proceedings of ESORICS 2013. (September
2013)
4. Biryukov, A., Pustogarov, I., Weinmann, R.P.: Content and popularity analysis of
tor hidden services. arXiv [cs.CR] (August 2013)
5. Biryukov, A., Pustogarov, I., Weinmann, R.P.: Trawling for tor hidden services:
Detection, measurement, deanonymization. In: Proceedings of the 2013 IEEE Symposium on Security and Privacy. (May 2013)
6. Borisov, N., Danezis, G., Mittal, P., Tabriz, P.: Denial of service or denial of
security? How attacks on reliability can compromise anonymity. In: Proceedingsof CCS 2007. (October 2007)
7. Bursztein, E., Martin, M., Mitchell, J.: Text-based CAPTCHA strengths andweaknesses. In: Proceedings of the 18th ACM Conference on Computer and Communications Security. CCS ’11, New York, NY, USA, ACM (2011) 125–138
8. Goldberg, I., Stebila, D., Ustaoglu, B.: Anonymity and one-way authenticationin key exchange protocols. Designs, Codes and Cryptography 67(2) (May 2013)
245–269
9. Jansen, R., Hopper, N.: Shadow: Running Tor in a Box for Accurate and Efficient
Experimentation. In: Proceedings of the Network and Distributed System Security
Symposium - NDSS’12, Internet Society (February 2012)10. Jansen, R., Hopper, N., Kim, Y.: Recruiting new Tor relays with BRAIDS. In
Keromytis, A.D., Shmatikov, V., eds.: Proceedings of the 2010 ACM Conference
on Computer and Communications Security (CCS 2010), ACM (October 2010)
11. Jones, D.W.: Chain voting. In: Workshop on Developing an Analysis of Threats
to Voting Systems, National Institute of Standards and Technology. (2005)
12. Reiter, M.K., Wang, X., Wright, M.: Building reliable mix networks with fairexchange. In: Applied Cryptography and Network Security, Springer (2005) 378–
392