Guided tour puzzle protocol
Encyclopedia
Guided tour puzzle protocol is a cryptographic protocol
for mitigating application layer denial of service attacks
. It aims to overcome the shortcoming of computation-based puzzle protocols
, in which clients
are required to compute hard CPU or memory-bound puzzles that favor clients with abundant computational resources. Guided tour puzzle protocol can be seen as a form of proof-of-work
(POW) protocol.
, if the server suspects it is currently under denial of service attack
or its load exceeds a pre-defined threshold. Simply put, a guided tour puzzle is a tour that needs to be completed by taking multiple round-trips
to a set of special nodes, called tour guides, in a sequential order. It is called a guided tour, because the order in which the tour guides are visited is unknown to the client, and each tour guide has to direct the client towards the next tour guide for the client to complete the tour in correct order. A single tour guide may appear multiple times in a tour, so the term stop is used to denote a single appearance of a tour guide in a tour. A client knows which tour guide is at the next stop, only after completing its visit to the current stop.
Solving a guided tour puzzle is essentially equal to completing a guided tour in the correct order. Starting from the first stop, the client contacts each stop and receives a reply. Each reply contains a unique token. The token in the reply message from the current stop is used for computing the address of the next stop tour guide. The address of the first stop tour guide is computed using the token contained in the server's first reply message that informs the client of the start of a puzzle process.
The client must send the token received from the current stop tour guide to the next stop tour guide, which will use it as an input to its token calculation function. The token received from the last stop tour guide plus the token from the server's puzzle message are sent to the server as the proof of completion of a tour. The server can efficiently validate these two tokens, and grants service to the client only after proving their validity.
tour guides has to be set up in the system, where 
. Meanwhile, the server establishes a shared secret
with each tour guide 
using a secure channel, where 
. The server keeps a short-lived secret 
for computing the first first hash value that is returned to the client as part of a puzzle message. A puzzle message also contains the length of the tour 
, which is used to control the difficulty of a guided tour puzzle. The figure shows an example of a guided tour when 
and 
.
The details of the each protocol step of the guided tour puzzle protocol is explained in the following.
, can mitigate the effect of denial of service attack, because the more an attacker wants to overwhelm the server, the more puzzles it has to compute, and the more computational resources of its own it needs to expend. However, due to the variation in the computational powers of clients, clients with strong computational power can solve puzzles at much higher rate than the destitute clients, and can unfairly take up most of the server resources.
Another crucial shortcoming of computational puzzle protocols is that all clients, including all legitimate clients, are required to perform such CPU-intensive computations that do not contribute to any meaningful service or application.
Guided tour puzzle protocol enforces delay on the clients through round trip delays
, so that clients' requests arrive at a rate that is sustainable by the server. The advantage of using round-trip delays, as opposed to hard computational problems, is that the round trip delay of a small packet is determined mostly by the processing delays
, queuing delays
, and propagation delays
at the intermediate routers, therefore is beyond the control of end hosts (clients). As such, even an attacker with abundant computational resources cannot unfairly take advantage over poorly provisioned legitimate clients.
Furthermore, in guided tour puzzle protocol, the computation required for the client is trivial. Since the length of a guided tour is usually a small number in the order of tens or lower, the bandwidth overhead for completing a guided tour is also trivial. As a result, clients are not burdened with heavy computations that is usually required by CPU-bound or memory bound puzzle protocols.
Cryptographic protocol
A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...
for mitigating application layer denial of service attacks
Denial-of-service attack
A denial-of-service attack or distributed denial-of-service attack is an attempt to make a computer resource unavailable to its intended users...
. It aims to overcome the shortcoming of computation-based puzzle protocols
Client Puzzle Protocol
Client Puzzle Protocol is a computer algorithm for use in Internet communication, whose goal is to make abuse of server resources infeasible. It is an implementation of a proof-of-work system ....
, in which clients
Client (computing)
A client is an application or system that accesses a service made available by a server. The server is often on another computer system, in which case the client accesses the service by way of a network....
are required to compute hard CPU or memory-bound puzzles that favor clients with abundant computational resources. Guided tour puzzle protocol can be seen as a form of proof-of-work
Proof-of-work system
A proof-of-work system is an economic measure to deter denial of service attacks and other service abuses such as spam on a network by requiring some work from the service requester, usually meaning processing time by a computer...
(POW) protocol.
Overview
The protocol steps of the guided tour puzzle protocol is similar to that of client puzzle protocol. All clients are required to complete a guided tour puzzle prior to receiving service from the serverServer (computing)
In the context of client-server architecture, a server is a computer program running to serve the requests of other programs, the "clients". Thus, the "server" performs some computational task on behalf of "clients"...
, if the server suspects it is currently under denial of service attack
Denial-of-service attack
A denial-of-service attack or distributed denial-of-service attack is an attempt to make a computer resource unavailable to its intended users...
or its load exceeds a pre-defined threshold. Simply put, a guided tour puzzle is a tour that needs to be completed by taking multiple round-trips
Round-trip delay time
In telecommunications, the round-trip delay time or round-trip time is the length of time it takes for a signal to be sent plus the length of time it takes for an acknowledgment of that signal to be received...
to a set of special nodes, called tour guides, in a sequential order. It is called a guided tour, because the order in which the tour guides are visited is unknown to the client, and each tour guide has to direct the client towards the next tour guide for the client to complete the tour in correct order. A single tour guide may appear multiple times in a tour, so the term stop is used to denote a single appearance of a tour guide in a tour. A client knows which tour guide is at the next stop, only after completing its visit to the current stop.
Solving a guided tour puzzle is essentially equal to completing a guided tour in the correct order. Starting from the first stop, the client contacts each stop and receives a reply. Each reply contains a unique token. The token in the reply message from the current stop is used for computing the address of the next stop tour guide. The address of the first stop tour guide is computed using the token contained in the server's first reply message that informs the client of the start of a puzzle process.
The client must send the token received from the current stop tour guide to the next stop tour guide, which will use it as an input to its token calculation function. The token received from the last stop tour guide plus the token from the server's puzzle message are sent to the server as the proof of completion of a tour. The server can efficiently validate these two tokens, and grants service to the client only after proving their validity.
Protocol Steps
Before the guided tour puzzle can start, tour guides has to be set up in the system, where . Meanwhile, the server establishes a shared secretShared secret
In cryptography, a shared secret is a piece of data, known only to the parties involved, in a secure communication. The shared secret can be a password, a passphrase, a big number or an array of randomly chosen bytes....
with each tour guide using a secure channel, where . The server keeps a short-lived secret for computing the first first hash value that is returned to the client as part of a puzzle message. A puzzle message also contains the length of the tour , which is used to control the difficulty of a guided tour puzzle. The figure shows an example of a guided tour when and .The details of the each protocol step of the guided tour puzzle protocol is explained in the following.
- Service request: A client
sends a service request to the server. If the server load is normal, the client's request is serviced as usual; if the server is overloaded, then it proceeds to the initial puzzle generation step.
- Initial puzzle generation: the server replies to the client
with a puzzle message that informs the client to complete a guided tour. The puzzle message contains the length of the tour 
and a hash value 
. The server computes 
using the following formula:
-
- where,
means concatenation, 
is the address (or any unique value) of the client 
, 
is a coarse timestamp, and 
is a cryptographic hash function such as SHA-1.
- Puzzle solving: A client computes the index of the tour guide at the
-th stop of its tour using the following formula:
-
- where,
. When contacted by a client 
, a tour guide 
computes a hash value 
(
) using the formula:
- where,
means the 
-th stop of the client's tour, 
is the shared key between the tour guide 
and the server. After client 
receives the server's reply message, it starts a guided tour by computing the index 
of the first tour guide using formula for $S_l$. The client then sends a set of values (
, 
, 
) to the tour guide 
, where the second value denotes which stop of a tour the client is currently at. As a response, the client receives a hash value 
from the tour guide 
, where 
is computed using the formula for 
. The client 
repeats this process 
more times and contacts the tour guides 
. The reply message from the last-stop tour guide 
contains the last hash value 
, and the client 
sends (
) to the server as the puzzle answer.
- Puzzle verification: when the server receives a request from client
with a puzzle answer (
, 
) attached, it first checks to see if 
is equal to the 
it computed using the formula for 
. If so, the server computes 
by repeatedly using the formula for 
, and verifies that 
is equal to 
. If both hash values are valid, the server allocates resources to process the client's request. Since the server knows the shared keys 
, it can compute the chain of hashes 
without contacting any tour guide. A loose time synchronization between the server and tour guides is required in order to compute the same hash value at the server and tour guides.
Comparison to other puzzle protocols
CPU-bound computational puzzle protocols, such as the Client Puzzle ProtocolClient Puzzle Protocol
Client Puzzle Protocol is a computer algorithm for use in Internet communication, whose goal is to make abuse of server resources infeasible. It is an implementation of a proof-of-work system ....
, can mitigate the effect of denial of service attack, because the more an attacker wants to overwhelm the server, the more puzzles it has to compute, and the more computational resources of its own it needs to expend. However, due to the variation in the computational powers of clients, clients with strong computational power can solve puzzles at much higher rate than the destitute clients, and can unfairly take up most of the server resources.
Another crucial shortcoming of computational puzzle protocols is that all clients, including all legitimate clients, are required to perform such CPU-intensive computations that do not contribute to any meaningful service or application.
Guided tour puzzle protocol enforces delay on the clients through round trip delays
End-to-end delay
End-to-end delay refers to the time taken for a packet to be transmitted across a network from source to destination.dend-end= N[ dtrans+dprop+dproc]where dend-end= end-to-end delay dtrans= transmission delay dprop= propagation delay...
, so that clients' requests arrive at a rate that is sustainable by the server. The advantage of using round-trip delays, as opposed to hard computational problems, is that the round trip delay of a small packet is determined mostly by the processing delays
Processing delay
In a network based on packet switching, processing delay is the time it takes routers to process the packet header. Processing delay is a key component in network delay....
, queuing delays
Queuing delay
In telecommunication and computer engineering, the queuing delay is the time a job waits in a queue until it can be executed. It is a key component of network delay....
, and propagation delays
Propagation delay
Propagation delay is a technical term that can have a different meaning depending on the context. It can relate to networking, electronics or physics...
at the intermediate routers, therefore is beyond the control of end hosts (clients). As such, even an attacker with abundant computational resources cannot unfairly take advantage over poorly provisioned legitimate clients.
Furthermore, in guided tour puzzle protocol, the computation required for the client is trivial. Since the length of a guided tour is usually a small number in the order of tens or lower, the bandwidth overhead for completing a guided tour is also trivial. As a result, clients are not burdened with heavy computations that is usually required by CPU-bound or memory bound puzzle protocols.