TY - GEN
T1 - A guided tour puzzle for denial of service prevention
AU - Abliz, Mehmud
AU - Znati, Taieb
PY - 2009
Y1 - 2009
N2 - Various cryptographic puzzle schemes are proposed as a defense mechanism against denial of service attack. But, all these puzzle schemes face a dilemma when there is a large disparity between the computational power of attackers and legitimate clients: increasing the difficulty of puzzles might unnecessarily restrict legitimate clients too much, and lower difficulty puzzles cannot sufficiently block attackers with large computational resources. In this paper, we introduce guided tour puzzle1, a novel puzzle scheme that is not affected by such resource disparity. A guided tour puzzle requires a client to visit a predefined set of nodes, called tour guides, in a certain sequential order to retrieve an n-piece answer, one piece from each tour guide that appears in the tour. This puzzle solving process is non-parallelizable, thus cheating by trying to solve the puzzle in parallel is not possible. Guided tour puzzle not only achieves all previously defined desired properties of a cryptographic puzzle scheme, but it also satisfies more important requirements, such as puzzle fairness and minimum interference, that we identified. The number of tour guides required by the scheme can be as few as two, and this extra cost can be amortized by sharing the same set of tour guides among multiple servers.
AB - Various cryptographic puzzle schemes are proposed as a defense mechanism against denial of service attack. But, all these puzzle schemes face a dilemma when there is a large disparity between the computational power of attackers and legitimate clients: increasing the difficulty of puzzles might unnecessarily restrict legitimate clients too much, and lower difficulty puzzles cannot sufficiently block attackers with large computational resources. In this paper, we introduce guided tour puzzle1, a novel puzzle scheme that is not affected by such resource disparity. A guided tour puzzle requires a client to visit a predefined set of nodes, called tour guides, in a certain sequential order to retrieve an n-piece answer, one piece from each tour guide that appears in the tour. This puzzle solving process is non-parallelizable, thus cheating by trying to solve the puzzle in parallel is not possible. Guided tour puzzle not only achieves all previously defined desired properties of a cryptographic puzzle scheme, but it also satisfies more important requirements, such as puzzle fairness and minimum interference, that we identified. The number of tour guides required by the scheme can be as few as two, and this extra cost can be amortized by sharing the same set of tour guides among multiple servers.
UR - http://www.scopus.com/inward/record.url?scp=77950803546&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77950803546&partnerID=8YFLogxK
U2 - 10.1109/ACSAC.2009.33
DO - 10.1109/ACSAC.2009.33
M3 - Conference contribution
AN - SCOPUS:77950803546
SN - 9780769539195
T3 - Proceedings - Annual Computer Security Applications Conference, ACSAC
SP - 279
EP - 288
BT - 25th Annual Computer Conference Security Applications, ACSAC 2009
T2 - 25th Annual Computer Conference Security Applications, ACSAC 2009
Y2 - 7 December 2009 through 11 December 2009
ER -