An integrated approach to cryptographic mitigation of denial-of-service attacks

DoS-resistant authentication with fast verification signatures and hash-based puzzles.


Gradual authentication is a principle proposed by Meadows as a way to tackle denial-of-service attacks on network protocols by gradually increasing the confidence in clients before the server commits resources. In this paper, we propose an efficient method that allows a defending server to authenticate its clients gradually with the help of some fast-to-verify measures. Our method integrates hash-based client puzzles along with a special class of digital signatures supporting fast verification. Our hash-based client puzzle provides finer granularity of difficulty and is proven secure in the puzzle difficulty model of Chen et al. (2009). We integrate this with the fast-verification digital signature scheme proposed by Bernstein (2000, 2008). These schemes can be up to 20 times faster for client authentication compared to RSA-based schemes. Our experimental results show that, in the Secure Sockets Layer (SSL) protocol, fast verification digital signatures can provide a 7% increase in connections per second compared to RSA signatures, and our integration of client puzzles with client authentication imposes no performance penalty on the server since puzzle verification is a part of signature verification.

Keywords: denial-of-service, client puzzles, Bernstein's signatures, Secure Sockets Layer (SSL)


Jothi Rangasamy, Douglas Stebila, Colin Boyd, Juan González Nieto. An integrated approach to cryptographic mitigation of denial-of-service attacks. In Ravi Sandhu, Duncan S. Wong, editors, Proc. 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS) 2011, pp. 114-123. ACM, March 2011. © ACM.





This research was supported by:
  • Australia–India Strategic Research Fund (AISRF) project TA020002