Nymble: Blocking Misbehaving Users in Anonymizing Networks



  Blocking Misbehaving Users in.pdf (Size: 790.97 KB / Downloads: 4)

INTRODUCTION

Anonymizing networks such as Tor [18] route traffic
through independent nodes in separate administrative
domains to hide a client’s IP address. Unfortunately,
some users have misused such networks —
under the cover of anonymity, users have repeatedly
defaced popular websites such as Wikipedia. Since website
administrators cannot blacklist individual malicious
users’ IP addresses, they blacklist the entire anonymizing
network. Such measures eliminate malicious activity
through anonymizing networks at the cost of denying
anonymous access to behaving users. In other words,
a few “bad apples” can spoil the fun for all. (This has
happened repeatedly with Tor.1)


Our solution

We present a secure system called Nymble, which provides
all the following properties: anonymous authentication,
backward unlinkability, subjective blacklisting,
fast authentication speeds, rate-limited anonymous connections,
revocation auditability (where users can verify
whether they have been blacklisted), and also addresses
the Sybil attack [19] to make its deployment practical.
In Nymble, users acquire an ordered collection of
nymbles, a special type of pseudonym, to connect to
websites. Without additional information, these nymbles
are computationally hard to link,4 and hence using the
stream of nymbles simulates anonymous access to services.
Websites, however, can blacklist users by obtaining
a seed for a particular nymble, allowing them to link
future nymbles from the same user — those used before
the complaint remain unlinkable.



Resource-based blocking

To limit the number of identities a user can obtain (called
the Sybil attack [19]), the Nymble system binds nymbles
to resources that are sufficiently difficult to obtain in
great numbers. For example, we have used IP addresses
as the resource in our implementation, but our scheme
generalizes to other resources such as email addresses,
identity certificates, and trusted hardware. We address
the practical issues related with resource-based blocking
in Section 8, and suggest other alternatives for resources.
We do not claim to solve the Sybil attack. This problem
is faced by any credential system [19], [27], and we suggest
some promising approaches based on resource-based
blocking since we aim to create a real-world deployment.


The Nymble Manager

After obtaining a pseudonym from the PM, the user
connects to the Nymble Manager (NM) through the
anonymizing network, and requests nymbles for access
to a particular server (such as Wikipedia). A user’s
requests to the NM are therefore pseudonymous, and
nymbles are generated using the user’s pseudonym and
the server’s identity. These nymbles are thus specific to
a particular user-server pair. Nevertheless, as long as the
PM and the NM do not collude, the Nymble system
cannot identify which user is connecting to what server;
the NM knows only the pseudonym-server pair, and the
PM knows only the user identity-pseudonym pair.


Notifying the user of blacklist status

Users who make use of anonymizing networks expect
their connections to be anonymous. If a server obtains
a seed for that user, however, it can page link that user’s
subsequent connections. It is of utmost importance, then,
that users be notified of their blacklist status before they
present a nymble ticket to a server. In our system, the
user can download the server’s blacklist and verify her
status. If blacklisted, the user disconnects immediately.


Summary of updates to the Nymble protocol
We highlight the changes to Nymble since our conference
paper [24]. Previously, we had proved only the
privacy properties associated with nymbles as part of
a two-tiered hash chain. Here we prove security at the
protocol level. This process gave us insights into possible
(subtle) attacks against privacy, leading us to redesign
our protocols and refine our definitions of privacy. For
example, users are now either legitimate or illegitimate,
and are anonymous within these sets (see Section 3). This
redefinition affects how a user establishes a “Nymble
connection” (see Section 5.5), and now prevents the
server from distinguishing between users who have
already connected in the same time period and those
who are blacklisted, resulting in larger anonymity sets.