Cited By
View all- Alviano M(2023)Hashcash Tree, a Data Structure to Mitigate Denial-of-Service AttacksAlgorithms10.3390/a1610046216:10(462)Online publication date: 30-Sep-2023
Non-Interactive VDF Client Puzzle for DoS Mitigation
Pages 32 - 38
Abstract
Denial of Service (DoS) attacks pose a growing threat to network services. Client puzzles have been proposed to mitigate DoS attacks by requiring a client to prove legitimate intentions. Since its introduction, there have been several constructions of client puzzles. Nevertheless, most of the existing client puzzles are interactive, where a server constructs a puzzle for a client request and asks the client to solve it before giving access to a resource. Additionally, most existing client puzzles do not provide desirable properties such as fairness, non-parallelizability, or non-interactivity. In this work, we propose a non-interactive client puzzle that achieves all these desired properties through a verifiable delay function (VDF). In a non-interactive puzzle, the client generates a puzzle and sends its solution along with the puzzle to access a resource of the server. We present different methods to generate verifiable client puzzles to prevent puzzle forgery and attacks from the client side. Further, we exhibit a transformation of the client puzzle into a DoS-resistant protocol. We also demonstrate the applicability of the DoS-resistant protocol in different contexts of the blockchain ecosystem.
References
[1]
Martin Abadi, Mike Burrows, Mark Manasse, and Ted Wobber. 2005. Moderately hard, memory-bound functions. ACM Transactions on Internet Technology (TOIT) 5, 2 (2005), 299–327.
[2]
Mehmud Abliz and Taieb Znati. 2009. A guided tour puzzle for denial of service prevention. In 2009 Annual Computer Security Applications Conference. IEEE, 279–288.
[3]
Ghous Amjad, Muhammad Shujaat Mirza, and Christina Pöpper. 2018. Forgetting with puzzles: using cryptographic puzzles to support digital forgetting. In Proceedings of the Eighth ACM Conference on Data and Application Security and Privacy. 342–353.
[4]
Vidal Attias, Luigi Vigneri, and Vassil Dimitrov. 2020. Implementation Study of Two Verifiable DelayFunctions.IACR Cryptol. ePrint Arch. 2020 (2020), 332.
[5]
Adam Back 2002. Hashcash-a denial of service counter-measure. ftp://sunsite.icm.edu.pl/site/replay.old/programs/hashcash/hashcash.pdf(2002).
[6]
Adithya Bhat, Nibesh Shrestha, Aniket Kate, and Kartik Nayak. 2020. RandPiper-Reconfiguration-Friendly Random Beacons with Quadratic Communication.IACR Cryptol. ePrint Arch. 2020 (2020), 1590.
[7]
Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. 2018. Verifiable Delay Functions. In Advances in Cryptology – CRYPTO 2018, Hovav Shacham and Alexandra Boldyreva (Eds.). Springer International Publishing, Cham, 757–788.
[8]
Megan Chen, Ran Cohen, Jack Doerner, Yashvanth Kondi, Eysa Lee, Schuyler Rosefield, and Abhi Shelat. 2020. Multiparty Generation of an RSA Modulus. In Annual International Cryptology Conference. Springer, 64–93.
[9]
Alisa Cherniaeva, Ilia Shirobokov, and Omer Shlomovits. 2019. Homomorphic Encryption Random Beacon.IACR Cryptol. ePrint Arch. 2019 (2019), 1320.
[10]
Vassil S Dimitrov, Graham A Jullien, and William C Miller. 2000. Complexity and fast algorithms for multiexponentiations. IEEE Trans. Comput. 49, 2 (2000), 141–147.
[11]
Christos Douligeris and Aikaterini Mitrokotsa. 2004. DDoS attacks and defense mechanisms: classification and state-of-the-art. Computer Networks 44, 5 (2004), 643 – 666. https://doi.org/10.1016/j.comnet.2003.10.003
[12]
Cynthia Dwork and Moni Naor. 1992. Pricing via processing or combatting junk mail. In Annual International Cryptology Conference. Springer, 139–147.
[13]
Cynthia Dwork, Moni Naor, and Hoeteck Wee. 2005. Pebbling and proofs of work. In Annual International Cryptology Conference. Springer, 37–54.
[14]
Wu-chi Feng, Edward Kaiser, and Antoine Luu. 2005. Design and implementation of network puzzles. In Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., Vol. 4. IEEE, 2372–2382.
[15]
Matthew K Franklin and Dahlia Malkhi. 1997. Auditable metering with lightweight security. In International Conference on Financial Cryptography. Springer, 151–160.
[16]
Yi Gao, Willy Susilo, Yi Mu, and Jennifer Seberry. 2010. Efficient trapdoor-based client puzzle against DoS attacks. In Network Security. Springer, 229–249.
[17]
P. Gasti, G. Tsudik, E. Uzun, and L. Zhang. 2013. DoS and DDoS in Named Data Networking. In 2013 22nd International Conference on Computer Communication and Networks (ICCCN). 1–7. https://doi.org/10.1109/ICCCN.2013.6614127
[18]
Stan Higgins. 2015. Bitcoin Mining Pools Targeted in Wave of DDOS Attacks. https://www.coindesk.com/bitcoin-mining-pools-ddos-attacks. [Online; accessed 07-June-2021].
[19]
Yves Igor Jerschow and Martin Mauve. 2010. Offline submission with rsa time-lock puzzles. In 2010 10th IEEE International Conference on Computer and Information Technology. IEEE, 1058–1064.
[20]
Yves Igor Jerschow and Martin Mauve. 2012. Secure client puzzles based on random beacons. In International Conference on Research in Networking. Springer, 184–197.
[21]
Yves Igor Jerschow and Martin Mauve. 2013. Modular square root puzzles: Design of non-parallelizable and non-interactive client puzzles. Computers & Security 35(2013), 25–36. https://doi.org/10.1016/j.cose.2012.11.008 Special Issue of the International Conference on Availability, Reliability and Security (ARES).
[22]
Ari Juels. 1999. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In Proc. Networks and Distributed System Security Symposium (NDSS), 1999.
[23]
Jonathan Katz, Andrew Miller, and Elaine Shi. 2014. Pseudonymous broadcast and secure computation from cryptographic puzzles. Technical Report. Cryptology ePrint Archive, Report 2014/857, 2014.http://eprint.iacr.org
[24]
Kaoru Kurosawa and Tsuyoshi Takagi. 2003. Some RSA-based encryption schemes with tight security reduction. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 19–36.
[25]
Huijia Lin, Rafael Pass, and Pratik Soni. 2020. Two-round and non-interactive concurrent non-malleable commitments from time-lock puzzles. SIAM J. Comput. 49, 4 (2020), FOCS17–196.
[26]
Mohammad Mahmoody, Tal Moran, and Salil Vadhan. 2013. Publicly verifiable proofs of sequential work. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science. 373–388.
[27]
Krzysztof Pietrzak. 2018. Simple verifiable delay functions. In 10th innovations in theoretical computer science conference (itcs 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
[28]
Ronald L Rivest, Adi Shamir, and David A Wagner. 1996. Time-lock puzzles and timed-release crypto. Massachusetts Institute of Technology, Laboratory for Computer Science (1996).
[29]
Muhammad Saad, Laurent Njilla, Charles Kamhoua, Joongheon Kim, DaeHun Nyang, and Aziz Mohaisen. 2019. Mempool Optimization for Defending Against DDoS Attacks in PoW-based Blockchain Systems. In 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). IEEE, 285–292.
[30]
Philipp Schindler, Aljosha Judmayer, Markus Hittmeir, Nicholas Stifter, and Edgar Weippl. 2021. Randrunner: Distributed randomness from trapdoor vdfs with strong uniqueness. (2021).
[31]
Philipp Schindler, Aljosha Judmayer, Nicholas Stifter, and Edgar Weippl. 2020. Hydrand: Efficient continuous distributed randomness. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 73–89.
[32]
Jayasree Sengupta, Sushmita Ruj, and Sipra Das Bit. 2020. A Comprehensive Survey on Attacks, Security Issues and Blockchain Solutions for IoT and IIoT. Journal of Network and Computer Applications 149 (2020), 102481. https://doi.org/10.1016/j.jnca.2019.102481
[33]
Douglas Stebila, Lakshmi Kuppusamy, Jothi Rangasamy, Colin Boyd, and Juan Gonzalez Nieto. 2011. Stronger Difficulty Notions for Client Puzzles and Denial-of-Service-Resistant Protocols. In Topics in Cryptology – CT-RSA 2011, Aggelos Kiayias (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 284–301.
[34]
Suratose Tritilanunt, Colin Boyd, Ernest Foo, and Juan Manuel González Nieto. 2007. Toward non-parallelizable client puzzles. In International Conference on Cryptology and Network Security. Springer, 247–264.
[35]
Brent Waters, Ari Juels, J Alex Halderman, and Edward W Felten. 2004. New client puzzle outsourcing techniques for DoS resistance. In Proceedings of the 11th ACM conference on Computer and communications security. 246–256.
[36]
Benjamin Wesolowski. 2019. Efficient Verifiable Delay Functions. In Advances in Cryptology – EUROCRYPT 2019, Yuval Ishai and Vincent Rijmen (Eds.). Springer International Publishing, Cham, 379–407.
[37]
Nicky Woolf. 2016. DDoS attack that disrupted internet was largest of its kind in history, experts say. The Guardian 26(2016).
Recommendations
New client puzzle outsourcing techniques for DoS resistance
CCS '04: Proceedings of the 11th ACM conference on Computer and communications securityWe 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 ...
The Moderately Hard DoS-Resistant Authentication Protocol on Client Puzzles
Denial-of-service (DoS) attacks against server resources exhaustion are a major security threat to the Internet. A number of defense mechanisms have been proposed against such attacks. Recently, Aura et al. proposed a solution to resist DoS attacks ...
An integrated approach to cryptographic mitigation of denial-of-service attacks
ASIACCS '11: Proceedings of the 6th ACM Symposium on Information, Computer and Communications SecurityGradual 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2021
97 pages
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 November 2021
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
EICC '21
EICC '21: European Interdisciplinary Cybersecurity Conference
November 10 - 11, 2021
Virtual Event, Romania
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 92Total Downloads
- Downloads (Last 12 months)19
- Downloads (Last 6 weeks)1
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
Cited By
View all- Alviano M(2023)Hashcash Tree, a Data Structure to Mitigate Denial-of-Service AttacksAlgorithms10.3390/a1610046216:10(462)Online publication date: 30-Sep-2023
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format