08-03-2012, 02:38 PM
Nymble: Blocking Misbehaving Users in Anonymizing Networks
[attachment=18110]
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 Web sites
such as Wikipedia. Since Web site 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 toWebsites. Without
additional information, these nymbles are computationally
hard to link,4 and hence, using the stream of nymbles
simulates anonymous access to services. Web sites, 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.
Servers can therefore blacklist anonymous users without
knowledge of their IP addresses while allowing behaving
users to connect anonymously.
1.2 Contributions of This Paper
Our research makes the following contributions:
. Blacklisting anonymous users. We provide a means
by which servers can blacklist users of an anonymizing
network while maintaining their privacy.
. Practical performance. Our protocol makes use of
inexpensive symmetric cryptographic operations to
significantly outperform the alternatives.
. Open-source implementation. With the goal of
contributing a workable system, we have built an
open-source implementation of Nymble, which is
publicly available.5 We provide performance statistics
to show that our system is indeed practical.
2 AN OVERVIEW TO NYMBLE
We now present a high-level overview of the Nymble
system, and defer the entire protocol description and
security analysis to subsequent sections.
2.1 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.
2.2 The Pseudonym Manager
The user must first contact the Pseudonym Manager (PM) and
demonstrate control over a resource; for IP-address blocking,
the user must connect to the PM directly (i.e., not
through a known anonymizing network), as shown in Fig. 1.
We assume the PM has knowledge about Tor routers, for
example, and can ensure that users are communicating with
it directly.6 Pseudonyms are deterministically chosen based
on the controlled resource, ensuring that the same pseudonym
is always issued for the same resource.
Note that the user does not disclose what server he or she
intends to connect to, and the PM’s duties are limited to
mapping IP addresses (or other resources) to pseudonyms.
As we will explain, the user contacts the PM only once per
linkability window (e.g., once a day).
[attachment=18110]
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 Web sites
such as Wikipedia. Since Web site 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 toWebsites. Without
additional information, these nymbles are computationally
hard to link,4 and hence, using the stream of nymbles
simulates anonymous access to services. Web sites, 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.
Servers can therefore blacklist anonymous users without
knowledge of their IP addresses while allowing behaving
users to connect anonymously.
1.2 Contributions of This Paper
Our research makes the following contributions:
. Blacklisting anonymous users. We provide a means
by which servers can blacklist users of an anonymizing
network while maintaining their privacy.
. Practical performance. Our protocol makes use of
inexpensive symmetric cryptographic operations to
significantly outperform the alternatives.
. Open-source implementation. With the goal of
contributing a workable system, we have built an
open-source implementation of Nymble, which is
publicly available.5 We provide performance statistics
to show that our system is indeed practical.
2 AN OVERVIEW TO NYMBLE
We now present a high-level overview of the Nymble
system, and defer the entire protocol description and
security analysis to subsequent sections.
2.1 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.
2.2 The Pseudonym Manager
The user must first contact the Pseudonym Manager (PM) and
demonstrate control over a resource; for IP-address blocking,
the user must connect to the PM directly (i.e., not
through a known anonymizing network), as shown in Fig. 1.
We assume the PM has knowledge about Tor routers, for
example, and can ensure that users are communicating with
it directly.6 Pseudonyms are deterministically chosen based
on the controlled resource, ensuring that the same pseudonym
is always issued for the same resource.
Note that the user does not disclose what server he or she
intends to connect to, and the PM’s duties are limited to
mapping IP addresses (or other resources) to pseudonyms.
As we will explain, the user contacts the PM only once per
linkability window (e.g., once a day).