New client puzzle outsourcing techniques for DoS resistance

ABSTRACT

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 out-sourcing of puzzles; 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 special purpose server. Our out-sourcing techniques help eliminate puzzle distribution as a point of compromise.

Our design has three main advantages over prior approaches. First, it is more resistant to DoS attacks aimed at the puzzle mechanism itself, withstanding over 80% more attack traffic than previous methods in our experiments. Second, our scheme 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, reducing the need for users to wait while their computers solve puzzles. We present a prototype implementation of our approach, and we describe experiments that validate our performance claims.

REFERENCES

• 1: M. Abadi, M. Burrows, M. Manasse, and T. Wobber. Moderately hard, memory-bound functions. In NDSS'03, pages 107--121. Internet Society, 2003.
• 2: D. Adkins, K. Lakshminarayanan, A. Perrig, and I. Stoica. Taming IP packet ooding attacks. In HotNets-II. ACM Press, 2003.
• 3: Micah Adler, Tradeoffs in probabilistic packet marking for IP traceback, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509969]
• 4: D. G. Andersen. Mayday: Distributed filtering for Internet services. In USENIX Symposium on Internet Technologies and Systems (USITS), 2003.
• 5: T. Anderson, T. Roscoe, and D. Wetherall. Preventing Internet denial-of-service with capabilities. In HotNets-II. ACM Press, 2003.
• 6: Tuomas Aura , Pekka Nikander , Jussipekka Leiwo, DOS-Resistant Authentication with Client Puzzles, Revised Papers from the 8th International Workshop on Security Protocols, p.170-177, April 03-05, 2000
• 7: A. Back. Hashcash - a denial-of-service countermeasure, 2002. Original system developed in 1997. Manuscript. Referenced 2004 at http://www.hashcash.org/hashcash.pdf.
• 8: Paul Barford , Jeffery Kline , David Plonka , Amos Ron, A signal analysis of network traffic anomalies, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637210]
• 9: S. Bellovin, M. Leech, and T. Taylor. ICMP traceback messages, 2003. Internet Draft.
• 10: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 11: Wei Dai. Crypto 5.1 benchmarks. Web site at http://www.eskimo.com/ weidai/benchmarks.html.
• 12: Drew Dean , Matt Franklin , Adam Stubblefield, An algebraic approach to IP traceback, ACM Transactions on Information and System Security (TISSEC), v.5 n.2, p.119-137, May 2002 [doi>10.1145/505586.505588]
• 13: D. Dean and A. Stubblefield. Using client puzzles to protect TLS. In 10th USENIX Security Symposium, pages 1--8, 2001.
• 14: W. Diffie and M.E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22:644--654, 1976.
• 15: C. Dwork, A. Goldberg, and M. Naor. On memory-bound functions for fighting spam. In D. Boneh, editor, CRYPTO '03, pages 426--444. Springer-Verlag, 2003.
• 16: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 17: Matthew K. Franklin , Dahlia Malkhi, Auditable Metering with Lightweight Security, Proceedings of the First International Conference on Financial Cryptography, p.151-160, February 24-28, 1997
• 18: Eran Gabber , Markus Jakobsson , Yossi Matias , Alain J. Mayer, Curbing Junk E-Mail via Secure Classification, Proceedings of the Second International Conference on Financial Cryptography, p.198-213, February 23-25, 1998
• 19: Virgil D. Gligor. Guaranteeing access in spite of service- ooding attacks. In Security Protocols Workshop, 2003.
• 20: David M. Goldschlag , Stuart G. Stubblebine, Publicly Verifiable Lotteries: Applications of Delaying Functions, Proceedings of the Second International Conference on Financial Cryptography, p.214-226, February 23-25, 1998
• 21: Alefiya Hussain , John Heidemann , Christos Papadopoulos, A framework for classifying denial of service attacks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863968]
• 22: Markus Jakobsson , Ari Juels, Proofs of Work and Bread Pudding Protocols, Proceedings of the IFIP TC6/TC11 Joint Working Conference on Secure Information Networks: Communications and Multimedia Security, p.258-272, September 20-21, 1999
• 23: A. Juels and J. Brainard. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In Proceedings of the 1999 ISOC Network and Distributed System Security Symposium, pages 151--165, 1999.
• 24: Angelos D. Keromytis , Vishal Misra , Dan Rubenstein, SOS: secure overlay services, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 25: Ratul Mahajan , Steven M. Bellovin , Sally Floyd , John Ioannidis , Vern Paxson , Scott Shenker, Controlling high bandwidth aggregates in the network, ACM SIGCOMM Computer Communication Review, v.32 n.3, p.62-73, July 2002 [doi>10.1145/571697.571724]
• 26: Ralph C. Merkle, Secure communications over insecure channels, Communications of the ACM, v.21 n.4, p.294-299, April 1978 [doi>10.1145/359460.359473]
• 27: The Netfilter/Iptables Project. Web site at http://www.netfilter.org.
• 28: The GNU MP Project. Web site at http://www.gnu.org/software/gmp/gmp.html.
• 29: R. L. Rivest , A. Shamir , D. A. Wagner, Time-lock Puzzles and Timed-release Crypto, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 30: Stefan Savage , David Wetherall , Anna Karlin , Tom Anderson, Practical network support for IP traceback, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.295-306, August 28-September 01, 2000, Stockholm, Sweden
• 31: C.-P. Schnorr and M. Jakobsson. Security of discrete log cryptosystems in the random oracle and generic model. In The Mathematics of Public-Key Cryptography. The Fields Institute, 1999.
• 32: IP Security Protocol Charter. Web site at http://www.ietf.org/html.charters/ipsec-charter.html.
• 33: D. X. Song and A. Perrig. Advanced and authenticated marking schemes for IP traceback. In IEEE INFOCOM, pages 878--886, 2001.
• 34: R. Stone. CenterTrack: An IP overlay network for tracking DoS oods. In USENIX Security '00, 2000.
• 35: L. von Ahn, M. Blum, N.J. Hopper, and J. Langford. CAPTCHA: Using hard AI problems for security. In E. Biham, editor, Eurocrypt '03, pages 294--311. Springer-Verlag, 2003.
• 36: XiaoFeng Wang , Michael K. Reiter, Defending Against Denial-of-Service Attacks with Puzzle Auctions, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.78, May 11-14, 2003
• 37: Abraham Yaar , Adrian Perrig , Dawn Song, Pi: A Path Identification Mechanism to Defend against DDoS Attacks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.93, May 11-14, 2003

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
DoS, client puzzles, denial-of-service