Hide Notes 

Slide 1: Client Puzzles A Cryptographic Defense Against Connection Depletion Attacks Ari Juels and John Brainard RSA Laboratories
Slide 2: The Problem
Slide 3: How to take down a restaurant Restauranteur Saboteur
Slide 4: Table for four at 8 o’clock. Name of Mr. Smith. O.K., Mr. Smith Restauranteur Saboteur Saboteur vs. Restauranteur
Slide 5: Restauranteur Saboteur No More Tables!
Slide 6: An example: TCP SYN flooding “TCP connection, please.” “TCP connection, please.” “O.K. Please send ack.” “O.K. Please send ack.” Buffer
Slide 7:  TCP SYN flooding has been deployed in the real world – Panix, mid-Sept. 1996 (WSJ, NYT) – New York Times, late Sept. 1996 – Others  Similar attacks may be mounted against e-mail, SSL, etc.
Slide 8: Some defenses against connection depletion
Slide 9: Throw away requests Client ” lo? l He “ Server “Hello?” “He llo? ” Buffer Problem: Legitimate clients must keep retrying
Slide 10: IP Tracing (or Syncookies) Client Server Hi. My name is Request 10.100.16.126. Buffer Problems: •Can be evaded, particularly on, e.g., Ethernet •Does not allow for proxies, anonymity
Slide 11: Digital signatures Client Server Buffer Problems: •Requires carefully regulated PKI •Does not allow for anonymity
Slide 12: Connection timeout Server Client Problem: Hard to achieve balance between security and latency demands
Slide 13: Our solution: client puzzles
Slide 14: Intuition ??? Table for four at 8 o’clock. Name of Mr. Smith. O.K.,O.K. Mr. Smith Please solve this puzzle. Restauranteur
Slide 15: Intuition Suppose: A puzzle takes an hour to solve  There are 40 tables in restaurant  Reserve at most one day in advance  A legitimate patron can easily reserve a table, but:
Slide 16: Intuition ??? ??? ??? ??? ??? ??? Would-be saboteur has too many puzzles to solve
Slide 17: The client puzzle protocol Client Service request R Server Buffer O.K.
Slide 18: What does a puzzle look like?
Slide 19: Puzzle basis: partial hash inversion pre-image partial-image hash image Y ? X’X ? k bits 160 bits Pair (X’, Y) is k-bit-hard puzzle
Slide 20: Puzzle construction Client Service request Server R Secret S
Slide 21: Puzzle construction Server computes: secret S time T request R hash pre-image Puzzle X hash image Y
Slide 22: Puzzle properties Puzzles are stateless  Puzzles are easy to verify  Hardness of puzzles can be carefully controlled  Puzzles use standard cryptographic primitives 
Slide 23: Where to use client puzzles?
Slide 24: Some pros Avoids many flaws in other solutions, e.g.: Allows for anonymous connections  Does not require PKI  Does not require retries -- even under heavy attack 
Slide 25: Practical application  Can use client-puzzles without specialpurpose software – Key idea: Applet carries puzzle + puzzlesolving code  Where can we apply this? – SSL (Secure Sockets Layer) – Web-based password authentication
Slide 26: Conclusions
Slide 27: Contributions of paper  Introduces idea of client puzzles for onthe-fly resource access control Puzzle and protocol description Too  Rigorous mathematical treatment of security using puzzles -probabilistic/guessing attack  – Don’t really need multiple sub-puzzles as paper suggests
Slide 28: Puzzles not new (but client-puzzles are)  Puzzles have also been used for: – Controlling spam (DW94, BGJMM98) – Auditing server usage (FM97) – Time capsules (RSW96)
Slide 29: More to be done How to define a puzzle? Search space vs. sequential workload  Can puzzle construction be improved?  – Replace hash with, e.g., reduced-round cipher  Can puzzles be made to do useful work? – Yes. Jakobsson & Juels “Bread Pudding”
Slide 30: Questions?