Nymble Overview

The purpose of the Nymble project is to allow for responsible, anonymous access online. It provides a mechanism for server administrators to block misbehaving users while allowing for honest users to stay anonymous; in fact even the blocked users remain anonymous.

The name "Nymble" comes from a play on the word "pseudonym" and "nimble". Instead of giving users a simple pseudonym, the Nymble system assigns users "nymbles"; that is, a pseudonym with better anonymity properties.

The Problem: Abuse of Anonymizing Networks

Tor is an anonymizing network—it hides a client's identity (actually, your computer's IP address) from the servers that it accesses. Tor keeps a client's IP-address anonymous by bouncing its data packets through a random path of relays. Each relay knows only of the relay that sent it data and the next relay in the random path. As long as the entry and exit nodes do not collude, the client's connections remain anonymous.

Tor provides anonymity, but some people abuse this anonymity. Since website administrators depend on blocking the IP addresses of misbehaving users, they are unable to block misbehaving users who connect through Tor—their IP address is hidden after all. Frustrated by repeated offenses through the Tor network, the usual response for websites such as Slashdot and Wikipedia is to block the entire Tor network. This is hardly an optimal solution, as honest users are denied anonymous access to these websites through Tor (or any anonymizing network for that matter). For an extensive list of the many legitimate uses of Tor, see Who uses Tor?

The Solution: Using Nymble for Blacklisting Anonymous Users

By providing a mechanism for server administrators to block anonymous misbehaving users, we hope to make the use of anonymizing networks such as Tor more acceptable for server administrators everywhere. All users remain anonymous— misbehaving users can be blocked without deanonymization, and their activity prior to being blocked remain unlinkable (anonymous).

How Nymble Works

Nymble is based on two administratively-separate "manager" servers, the Pseudonym Manager (PM) and the Nymble Manager (NM). The PM is responsible for pairing a user's IP address with a pseudonym deterministically generated based on the user's IP address. The NM pairs a user's pseudonym with the target server. As long as the two managers are not colluding, the user's connections remain anonymous to the PM, pseudonymous to the NM (note that the user does not communicate directly with the NM, and connects to the NM through Tor), and anonymous to servers that the user connects to.

Pseudonym Manager

The user (in this case, Alice) must first demonstrate control over a resource, that is the Alice's IP-address. To do this Alice must first connect directly with the PM before receiving a pseudonym. The PM has knowledge of existing Tor routers, and thus can ensure that Alice is communicating with it directly. Note that the PM has no knowledge of the user's destination, similar to the entry node in Tor. The PM's sole responsibility it to map IP addresses to pseudonyms. The reason for this is explained next.

Nymble Manager

Alice then connects to the NM through Tor presenting her pseudonym and her target server. The NM does not know the IP address of the user, but the pseudonym provided by the PM guarantees that some unique IP address maps to the pseudonym. She receives a set of nymble tickets as her credential for the target server. These nymble tickets are unlinkable, and therefore Alice can present these nymble tickets (once each) to gain anonymous access at the target server.

The nymble ticket provides cryptographic protection as well as a trap door that can be accessed using a linking token.

Connecting to a Server

Blacklisting a User

Servers can present a user's nymble ticket to the NM as part of a complaint. The NM extracts a "linking token" from the nymble ticket, that will allow the server to link future connections by the blacklisted user. The NM also issues servers with blacklists, which users can examine before performing any actions at the server. By checking servers' blacklists, blacklisted users are assured that their privacy is not compromised. We now explain the process of blacklisting in a little more detail. We first explain how nymble tickets are bound to certain "time periods" and "linkability windows."

Blacklisting

Time in the nymble protocol is divided into linkability windows of some duration (default is 1 day). A linkability window is then further divided into smaller time periods (default is 5 minutes). We illustrate the concepts in the diagram bellow; the linkability window is represented by the large, transparent rectangle while the time periods are labeled t0, t1, t2, etc.

Linking Tokens

A user's connections within a time period are tied to a single nymble ticket. If and when a user misbehaves, the server may not realize it for some amount of time and may not report it until a later time period. However, after receiving a linking token the server is able to block all future connections until the next linkability window. This is done for two reasons:

  • Dynamism: IP-addresses can be reassigned to different, well-behaved users making it undesirable to permanently blacklist IP-addresses.
  • Forgiveness: It ensures that bad behavior is forgiven after a certain amount of time.

Nymble is a system that allows websites to selectively blacklist users of anonymizing networks such as Tor without knowing the user's IP-address. Users not on the blacklist enjoy anonymity while blacklisted users are not allowed future connections for a duration of time while their previous connections remain unlinkable. Since Nymble allows websites to blacklist anonymious users of their choice, and since users are notified of their blacklist status, Nymble gives websites the power to define their own definition of "misbehavior". Our hope is that Nymble's properties well make the usage of anonymizing networks such as Tor more acceptable.

For more detail on the security implications of using this protocol, please check out our Security FAQ.