New Client Puzzle Outsourcing Techniquesfor DoS ResistanceBrent Waters1, Ari Juels2, J. Alex Halderman1, and Edward W. Felten11Princeton UniversityPrinceton, NJ{bwaters,jhalderm,felten}@cs.princeton.edu2RSA LaboratoriesBedford, [email protected] explore new techniques for the use of cryptographic puz-zles as a countermeasure to Denial-of-Service (DoS) attacks.We prop ose simple new techniques that permit the out-sourcing of puzzles—their distribution via a robust externalservice that we call a bastion. Many servers can rely onpuzzles distributed by a single bastion. We show how a bas-tion, somewhat surprisingly, need not know which serversrely on its services. Indeed, in one of our constructions, abastion may consist merely of a publicly accessible randomdata source, rather than a special purpose server. Our out-sourcing techniques help eliminate puzzle distribution as apoint of compromise.Our design has three main advantages over prior approaches.First, it is more resistant to DoS attacks aimed at the puzzlemechanism itself, withstanding over 80% more attack traf-fic than previous methods in our experiments. Second, ourscheme is cheap enough to apply at the IP level, though italso works at higher levels of the protocol stack. Third, ourmetho d allows clients to solve puzzles offline, reducing theneed for users to wait while their computers solve puzzles.We present a prototype implementation of our approach,and we des cribe experiments that validate our performanceclaims.Categories and Subject DescriptorsE.3 [Data]: [Data Encryption]General TermsSecurityKeywordsDenial-of-Service, DoS, Client PuzzlesPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.CCS’04, October 25-29, 2004, Washington, DC, USA.Copyright 2004 ACM 1-58113-961-6/04/0010 ...$5.00.1. INTRODUCTIONDenial-of-service (DoS) attacks present a strong and wellestablished threat to the Internet and e-commerce. One pro-posed countermeasure requires clients to commit resourcesto an interaction by successfully solving a computationalproblem known as a client puzzle [16, 23] before a serverwill provide resources to the client. This prevents an at-tacker from consuming a large portion of the resources of atargeted server without commanding and investing consid-erable resources himself.1.1 Shortcomings of Existing SolutionsWhile the deployment of client puzzles in attack scenariosseems promising, we have found that most proposed systemsof this type have two basic shortcomings.The first is that the client puzzle mechanism itself canbecome the target of a denial-of-service attack. In most sys-tems either the puzzle creation or verification operation (orboth) require the server to perform a cryptographic hashcomputation [23, 6, 13]. This opens the possibility that thepuzzle verification mechanism itself will be the target of a de-nial of service attack, in which an attacker floo ds the serverwith bogus puzzle solutions that the server has to process.Thus existing client puzzle mechanisms replace one possibleDoS attack with another. Although the DoS attack on thepuzzle mechanism requires more attack resources than be-fore, this is still not an ideal situation. The experiment wepresent in Section 4.1 demonstrate that puzzle verificationincreases the server’s processing time per new TCP con-nection request by approximately 80 percent with existingsolutions.A few systems [2] attempt to alleviate this problem byoutsourcing the hash computation to a designated gateway,but this merely pus hes the vulnerability to a different target.Furthermore, a gateway in these systems needs to be awareof each server it might service and thus will be difficult toscale. Deploying a robust gateway service in this mannerseems infeasible.The second shortcoming in current solutions is that clientsmust, in practice, solve them in an on-line fashion. Forexample, if a website employs client puzzles, then a userwho wants to visit the site has to wait for his computer tosolve a puzzle before accessing the site. Thus puzzles use upnot only computer time, but also users’ time, which is oftenmuch more valuable. Since many users have little patience246for website delays, a site that imposes long puzzle delays candrive away legitimate users.This puts the adversary at a cost advantage. He is notconcerned with whether there are human operators at themachines he employs for his attack. This means that a puz-zle that costs the attacker some fixed price to solve willcost legitimate clients much more, due to the higher cost ofhuman time for real clients. (Some sites require human in-tervention, by using CAPTCHAs [35], but that raises otherissues.)1.2 Our SolutionIn this paper, we present a new way to use puzzles tomitigate denial-of-service attacks. Our solution has threemain attributes:• The creation of puzzles is outsourced to a secure entitywe call a bastion. An arbitrary number of servers canuse the same bastion, and can safely share the sameset of puzzles, due to special cryptographic propertiesof the puzzles. Once constructed, the puzzles will bedigitally signed by the bastion so that they can beredistributed by anyone.• Verifying a puzzle solution requires very little work fora server. In fact, it only requires a simple table lookup.• Clients can solve puzzles off-line, so that users do nothave to wait for puzzles to be solved.• Solving a puzzle gives a client access, for a time in-terval, to a “virtual channel” on the server—i.e., to asmall slice of the server’s resources—and the server en-sures no virtual channel uses more than its fair shareof available resources.Previous schemes involve puzzle distribution on a per-request or per-session basis. Our approach is more coarse-grained in that it relies on virtual channels, which can beused as an abstraction to protect different typ es of resources.For example, a web server might limit the number of openTCP connections p er channel or a database server couldcontrol the rate of database queries processed. When athigh risk of DoS attack (or in the midst of an attack) a hostin our sys tem accepts communication only v ia a