RSA Laboratories

Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks

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 one.

Click here for paper

Click here for slides

Full Publication List