Efficient modular exponentiation-based puzzles for denial-of-service protection
Abstract
Client puzzles are moderately-hard cryptographic problems—neither easy nor impossible to solve—that can be used as a countermeasure against denial of service attacks on network protocols. Puzzles based on modular exponentiation are attractive as they provide important properties such as non-parallelisability, deterministic solving time, and linear granularity. We propose an efficient client puzzle based on modular exponentiation. Our puzzle requires only a few modular multiplications for puzzle generation and verification. For a server under denial of service attack, this is a significant improvement as the best known non-parallelisable puzzle proposed by Karame and Čapkun (ESORICS 2010) requires at least 2k-bit modular exponentiation, where k is a security parameter. We show that our puzzle satisfies the unforgeability and difficulty properties defined by Chen et al. (Asiacrypt 2009). We present experimental results which show that, for 1024-bit moduli, our proposed puzzle can be up to 30x faster to verify than the Karame-Čapkun puzzle and 99x faster than the Rivest et al.'s time-lock puzzle.Keywords: client puzzles, time-lock puzzles, denial of service resistance, RSA, puzzle difficulty
Reference
Jothi Rangasamy, Douglas Stebila, Colin Boyd, Juan González Nieto, Lakshmi Kuppusamy. Efficient modular exponentiation-based puzzles for denial-of-service protection. In Howon Kim, editor, Proc. International Conference on Information Security and Cryptology (ICISC) 2011, LNCS, vol. 7259, pp. 319–331. © Springer, 2011.Download
- Publisher’s website: DOI: 10.1007/978-3-642-31912-9_21
- Author’s website: PDF (full version)
- BibTeX@inproceedings{RSBGK11, Abstract = {Client puzzles are moderately-hard cryptographic problems---neither easy nor impossible to solve---that can be used as a countermeasure against denial of service attacks on network protocols. Puzzles based on modular exponentiation are attractive as they provide important properties such as non-parallelisability, deterministic solving time, and linear granularity. We propose an efficient client puzzle based on modular exponentiation. Our puzzle requires only a few modular multiplications for puzzle generation and verification. For a server under denial of service attack, this is a significant improvement as the best known non-parallelisable puzzle proposed by Karame and {\v C}apkun (ESORICS 2010) requires at least 2k-bit modular exponentiation, where k is a security parameter. We show that our puzzle satisfies the unforgeability and difficulty properties defined by Chen et al. (Asiacrypt 2009). We present experimental results which show that, for 1024-bit moduli, our proposed puzzle can be up to 30x faster to verify than the Karame-{\v C}apkun puzzle and 99x faster than the Rivest et al.'s time-lock puzzle.}, Author = {Jothi Rangasamy and Douglas Stebila and Colin Boyd and Juan {Gonz{\'a}lez Nieto} and Lakshmi Kuppusamy}, Booktitle = {Proc. International Conference on Information Security and Cryptology (ICISC) 2011}, Booktitleshort = {Proc. ICISC 2011}, Copyright = {Springer}, Doi = {10.1007/978-3-642-31912-9\_21}, Editor = {Howon Kim}, Keywords = {client puzzles, time-lock puzzles, denial of service resistance, RSA, puzzle difficulty}, Pages = {319--331}, Publisher = {Springer}, Series = {LNCS}, Title = {Efficient modular exponentiation-based puzzles for denial-of-service protection}, Volume = {7259}, Year = {2011}}
Presentations
- 2011/12/02: “Efficient modular exponentiation-based puzzles for denial-of-service protection.” Presented at International Conference on Information Security and Cryptology (ICISC) 2011. (PDF slides)
