Douglas Stebila

Efficient modular exponentiation-based puzzles for denial-of-service protection

A new client puzzle based on modular exponentiation.

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. 14th International Conference on Information Security and Cryptology (ICISC) 2011, LNCS, vol. 7259, pp. 319-331. Springer, November 2011. © Springer.

Download

Presentations

• 2011-12-02: ICISC 2011. (PDF slides)

BibTeX

@inproceedings{ICISC:RSBGK11,
 	Author = {Jothi Rangasamy and Douglas Stebila and Colin Boyd and Juan {Gonz{\' a}lez Nieto} and Lakshmi Kuppusamy},
 	Booktitle = {Proc. 14th International Conference on Information Security and Cryptology (ICISC) 2011},
 	Doi = {10.1007/978-3-642-31912-9\_21},
 	Editor = {Howon Kim},
 	Month = {November},
 	Pages = {319--331},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {Efficient modular exponentiation-based puzzles for denial-of-service protection},
 	Volume = {7259},
 	Year = {2011}
 }

Funding

• Australia–India Strategic Research Fund (AISRF) project TA020002