Nymble Anonymous IP Address Blocking Peter C Johnson1 Apu Kapadia1 2 Patrick P Tsang1 and Sean W Smith1 1 Department of Computer Science Dartmouth College Hanover NH 03755 USA 2 Institute for Security Technology Studies Dartmouth College Hanover NH 03755 USA pete akapadia patrick sws cs dartmouth edu Abstract Anonymizing networks such as Tor allow users to access Internet services privately using a series of routers to hide the client s IP address from the server Tor s success however has been limited by users employing this anonymity for abusive purposes such as defacing Wikipedia Website administrators rely on IPaddress blocking for disabling access to misbehaving users but this is not practical if the abuser routes through Tor As a result administrators block all Tor exit nodes denying anonymous access to honest and dishonest users alike To address this problem we present a system in which 1 honest users remain anonymous and their requests unlinkable 2 a server can complain about a particular anonymous user and gain the ability to blacklist the user for future connections 3 this blacklisted user s accesses before the complaint remain anonymous and 4 users are aware of their blacklist status before accessing a service As a result of these properties our system is agnostic to different servers definitions of misbehavior 1 Introduction Anonymizing networks such as Crowds 25 and Tor 15 route traffic through independent nodes in separate administrative domains to hide the originating IP address Unfortunately misuse has limited the acceptance of deployed anonymizing networks The anonymity provided by such networks prevents website administrators from blacklisting individual malicious users IP addresses to thwart further abuse they blacklist the entire anonymizing network Such measures eliminate malicious activity through anonymizing networks at the cost of denying anonymous access to honest users In other words a few bad apples can spoil the fun for all This has happened repeatedly with Tor 3 Some approaches for blacklisting abusive users are based on pseudonyms 11 13 14 19 In these systems of which Nym 17 seems most relevant users are required to log into 3 This research was supported in part by the NSF under grant CNS 0524695 and the Bureau of Justice Assistance under grant 2005 DD BX 1091 The views and conclusions do not necessarily reflect the views of the sponsors The Abuse FAQ for Tor Server Operators lists several such examples at http tor eff org faqabuse html en 2 websites using an assigned pseudonym thus assuring a level of accountability Unfortunately this approach results in pseudonymity for all users ideally honest users should enjoy full anonymity and misbehaving users should be blocked To this end we present a secure system in which users acquire an ordered collection of nymbles a special type of pseudonym to connect to websites Without additional data these nymbles are computationally hard to link and hence using the stream of nymbles simulates anonymous access to services Websites however can blacklist users by obtaining a trapdoor 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 honest users to connect anonymously Our system ensures that users are aware of their blacklist status before they present a nymble and disconnect immediately if they are blacklisted Furthermore websites avoid the problem of having to prove misbehavior they are free to establish their own independent blacklisting policies Although our work applies to anonymizing networks in general we consider Tor for purposes of exposition In fact any number of anonymizing networks can rely on the same nymble system blacklisting anonymous users regardless of their anonymizing network s of choice Our research makes the following contributions Blacklisting anonymous users We provide a means by which servers can blacklist users of an anonymizing network without deanonymizing them Honest users enjoy anonymous access and are unaffected by the misbehavior of other users Practical performance A system such as ours relying on a server to issue nymbles will be adopted only if performance is acceptable Our protocol minimizes storage requirements and the use of expensive asymmetric cryptographic operations Prototype implementation With the goal of contributing a workable system we have built a prototype implementation We provide performance statistics to show that our system is indeed a viable approach for selectively blocking users of large scale anonymizing networks such as Tor Many in the community worry that deanonymization will become a vehicle for suppressing individuals rights This project moves in the other direction by allowing websites to block users without knowing their identities hopefully increasing mainstream acceptance of anonymizing technologies such as Tor 2 Related Work Anonymous credential systems such as Camenisch and Lysyanskaya s 7 8 use group signatures for anonymous authentication wherein individual users are anonymous among a group of registered users Non revocable group signatures such as Ring signatures 26 provide no accountability and thus do not satisfy our needs to protect servers from misbehaving users Basic group signatures 1 2 3 12 allow revocation of anonymity by no one except the group manager As only the group manager can revoke a user s anonymity servers have no way of linking signatures to previous ones and must query the group manager for every signature this lack of scalability makes it unsuitable for our goals Traceable signatures 18 30 allow the group manager to release a trapdoor that allows all signatures generated by a particular user to be traced such an approach does not provide the 3 backward anonymity that we desire where a user s accesses before the complaint remain anonymous Specifically if the server is interested in blocking only future accesses of bad users then such reduction of user anonymity is unnecessarily drastic When a user makes an anonymous connection the connection should remain anonymous And misbehaving users should be blocked from making further connections after a complaint In some systems misbehavior can be defined precisely For instance double spending of an e coin is considered misbehavior in anonymous electronic cash systems 4 10 Likewise compact e cash 6 k times