RSA Laboratories

New Client Puzzle Outsourcing Techniques for DoS Resistance

B. Waters, A. Juels, A. Halderman, and E. Felten

Citation: B. Waters, A. Juels, A. Halderman, and E. Felten. New Client Puzzle Outsourcing Techniques for DoS Resistance. In ACM CCS, pp. 246—256. 2004

We explore new techniques for the use of cryptographic puzzles as a countermeasure to Denial-of-Service (DoS) attacks.

We propose simple new techniques that permit the outsourcing of puzzles, meaning their distribution via a robust external service that we call a bastion. Many servers can rely on puzzles distributed by a single bastion. We show how a bastion, somewhat surprisingly, need not know which servers rely on its services. Indeed, in one of our constructions, a bastion may consist merely of a publicly accessible random data source, rather than a server. Our outsourcing techniques help eliminate puzzle distribution as a point of compromise.

Our method has three main advantages over prior approaches. First, our method is more resistant to DoS attacks that are aimed at the puzzle mechanism itself, withstanding more than 80% more attack traffic than previous methods, according to our experiments. Second, our method is cheap enough to apply at the IP level, though it also works at higher levels of the protocol stack. Third, our method allows clients to solve puzzles offline, so that users do not have to sit and wait while their computers solve puzzles.

We present a prototype implementation of our approach, and we describe experiments that validate our performance claims.

Click here for paper

Full Publication List