Using rhythmic nonces for puzzle-based DoS resistance

ABSTRACT

To protect against replay attacks, many Internet protocols rely on nonces to guarantee freshness. In practice, the server generates these nonces during the initial handshake, but if the server is under attack, resources consumed by managing certain protocols can lead to DoS vulnerabilities. To help alleviate this problem, we propose the concept of rhythmic nonces, a cryptographic tool that allows servers to measure request freshness with minimal bookkeeping costs. We explore the impact of this service in the context of a puzzle-based DoS resistance scheme we call "SYN puzzles". Our preliminary results based on mathematical analysis and evaluation of a prototype suggests that our scheme is more resistant than existing techniques.

REFERENCES

• 1: National Solar Observatory/Sacremento Peak. Images and Current data. http://nsosp.nso.edu/data.
• 2: USGS Earthquake Hazards Program. Latest earthquakes in the world - past 7 days. http://earthquake.usgs.gov/eqcenter/recentqsww/Quakes/quakes all.php.
• 3: Martin Abadi , Mike Burrows , Mark Manasse , Ted Wobber, Moderately hard, memory-bound functions, ACM Transactions on Internet Technology (TOIT), v.5 n.2, p.299-327, May 2005 [doi>10.1145/1064340.1064341]
• 4: 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
• 5: A. Back. Hashcash - A Denial of Service Countermeasure. http://www.hashcash.org/hashcash.pdf, 2002.
• 6: Drew Dean , Adam Stubblefield, Using client puzzles to protect TLS, Proceedings of the 10th conference on USENIX Security Symposium, p.1-1, August 13-17, 2001, Washington, D.C.
• 7: S. Doshi, F. Monrose, and A. D. Rubin. Efficient Memory Bound Puzzles Using Pattern Databases. In ACNS, pages 98--113, 2006.
• 8: C. Douligeris and A. Mitrokotsa. Denial-of-Service Challenges from Oblivious Online Sources. Proceedings of the 14th ACM Conference on Computer and Communications Security (CCS 2007), 2007.
• 9: European Network of Excellence for Cryptology. Ecrypt yearly report on algorithms and keysizes 2006.
• 10: J. Alex Halderman , Brent Waters, Harvesting verifiable challenges from oblivious online sources, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315287]
• 11: A. Juels and J. Brainard. Client puzzles: A Cryptographic Countermeasure against Connection Depletion Attacks. Proceedings of the Network and Distributed System Security Symposium, pages 151--165, 1999.
• 12: J. Mirkovic, J. Martin, and P. Reiher. A Taxonomy of DDoS Attacks and DDoS Defense Mechanisms, 2001.
• 13: T. Moran, R. Shaltiel, and A. Ta-Shma. Non-interactive timestamping in the bounded storage model. In Advances in Cryptology (CRYPTO 04), volume 3152 of Lecture Notes in Computer Science. Springer, December 2004.
• 14: 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
• 15: Brent Waters , Ari Juels , J. Alex Halderman , Edward W. Felten, New client puzzle outsourcing techniques for DoS resistance, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030117]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Security

Keywords:
security