Ari Juels and John Brainard
Citation: Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks. In S. Kent, editor, Proceedings of NDSS '99 (Networks and Distributed Security Systems), pages 151-165, 1999.
Abstract: We introduce a cryptographically based countermeasure against connection depletion attacks. Connection depletion is a denial-of-service attack in which an attacker seeks to initiate and leave unresolved a large number of connection requests to a server, exhausting its resources and rendering it incapable of servicing legitimate requests. TCP SYN flooding is a well-known example of such an attack. We introduce a countermeasure that we refer to as a client puzzle protocol. The basic idea is as follows. When a server comes under attack, it distributes small cryptographic puzzles to clients making service requests. To complete its request, a client must solve its puzzle correctly. In this paper, we describe the client puzzle protocol and its proper parameterization, and give a rigorous proof of its security characteristics.
Note: Both the construction and proofs in the paper are more
complicated than necessary. In our model, the computational effort involved
submitting a guess is equivalent to that of testing a random solution.
Therefore, we need not concern ourselves with guessing by an adversary,
and consequently can reduce the number of sub-puzzles in a puzzle to