We explore the use of cryptographic puzzles as a countermeasure to low-level denial-of-service (DoS) attacks, such as IP-layer flooding. In previous work, puzzles have served mainly as tools for DoS mitigation in higher protocol layers, for session-establishment protocols or applications like e-mail.

In addition to its applicability to IP-level attacks, our approach is distinctive in two regards. First, we illustrate a way in which puzzles serve to protect public channels of communication for a server, rather than specific service requests from clients. We provide a detailed analysis of the resulting quality of service in different attack scenarios.

Second, 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.