ガイド付きツアーパズルプロトコル

ガイド付きツアー パズル (GTP) プロトコルは、アプリケーション層のサービス拒否攻撃を軽減するための暗号化プロトコルです。このプロトコルの目的は、クライアントが CPU やメモリにバインドされた難しいパズルを計算する必要がある計算ベースのパズル プロトコルの欠点を克服することです。このパズル プロトコルでは、クライアントは計算リソースが豊富であるため有利です。ガイド付きツアー パズル プロトコルは、プルーフ オブ ワーク(POW) プロトコルの一種と見なすことができます。

ガイド付きツアー パズル プロトコルのプロトコル手順は、クライアント パズル プロトコルの手順に似ています。サーバーが現在サービス拒否攻撃を受けていると疑っている場合、または負荷が定義済みのしきい値を超えている場合は、すべてのクライアントはサーバーからサービスを受ける前にガイド付きツアー パズルを完了する必要があります。簡単に言うと、ガイド付きツアー パズルは、ツアー ガイドと呼ばれる一連の特別なノードを順番に複数回往復することで完了する必要があるツアーです。ツアー ガイドを訪問する順序はクライアントには不明であり、クライアントが正しい順序でツアーを完了できるように、各ツアー ガイドがクライアントを次のツアー ガイドに誘導する必要があるため、ガイド付きツアーと呼ばれます。1 つのツアー ガイドがツアー内で複数回登場することがあるため、ストップという用語はツアー内でのツアー ガイドの 1 回の登場を表すために使用されます。クライアントは、現在のストップへの訪問を完了して初めて、次のストップにどのツアー ガイドがいるかがわかります。

ガイド付きツアーのパズルを解くことは、ガイド付きツアーを正しい順序で完了することと本質的に同じです。最初のストップから始めて、クライアントは各ストップに連絡し、応答を受け取ります。各応答には一意のトークンが含まれています。現在のストップからの応答メッセージ内のトークンは、次のストップのツアーガイドのアドレスを計算するために使用されます。最初のストップのツアーガイドのアドレスは、パズルプロセスの開始をクライアントに通知するサーバーの最初の応答メッセージに含まれるトークンを使用して計算されます。^{[引用が必要]}

クライアントは、現在の停留所のツアー ガイドから受け取ったトークンを次の停留所のツアー ガイドに送信する必要があります。次の停留所のツアー ガイドは、トークン計算関数への入力としてそれを使用します。最後の停留所のツアー ガイドから受け取ったトークンとサーバーのパズル メッセージからのトークンは、ツアーの完了の証明としてサーバーに送信されます。サーバーは、これら 2 つのトークンを効率的に検証し、その有効性を証明した後にのみクライアントにサービスを許可します。^{[引用が必要]}

ガイド付きツアー パズルを開始する前に、ツアー ガイドをシステム内にセットアップする必要があります。ここで、 です。一方、サーバーは、安全なチャネルを使用して各ツアー ガイドと共有秘密を確立します。ここで、 です。サーバーは、パズル メッセージの一部としてクライアントに返される最初のハッシュ値を計算するための短命の秘密を保持します。パズル メッセージには、ツアーの長さも含まれており、これを使用してガイド付きツアー パズルの難易度を制御します。図は、およびの場合のガイド付きツアーの例を示しています。 ${\displaystyle N}$${\displaystyle N\geq 2}$ ${\displaystyle k_{js}}$${\displaystyle G_{j}}$${\displaystyle 0\leq j<N}$${\displaystyle K_{s}}$${\displaystyle L}$${\displaystyle N=2}$${\displaystyle L=5}$

ガイドツアーパズルプロトコルの各プロトコルステップの詳細については、以下で説明します。^[1]

• サービス要求: クライアントはサーバーにサービス要求を送信します。サーバーの負荷が正常であれば、クライアントの要求は通常どおり処理されます。サーバーの負荷が過負荷の場合は、最初のパズル生成ステップに進みます。${\displaystyle x}$
• 初期パズル生成: サーバーは、ガイド付きツアーを完了するようにクライアントに通知するパズル メッセージをクライアントに返信します。パズル メッセージには、ツアーの長さとハッシュ値が含まれます。サーバーは次の式を使用して計算します。${\displaystyle x}$${\displaystyle L}$${\displaystyle h_{0}}$${\displaystyle h_{0}}$

${\displaystyle h_{0}=hash(A_{x}\;||\;L\;||\;ts\;||\;K_{s})}$

ここで、は連結を意味し、はクライアントのアドレス（または任意の一意の値）、は粗いタイムスタンプ、はSHA-1などの暗号化ハッシュ関数です。${\displaystyle ||}$${\displaystyle A_{x}}$${\displaystyle x}$${\displaystyle ts}$${\displaystyle ハッシュ}$

• パズルの解決: クライアントは、次の式を使用して、ツアーの - 番目の停止地点におけるツアー ガイドのインデックスを計算します。${\displaystyle l}$

${\displaystyle S_{l}=(h_{l-1}\;mod\;N)}$

ここで、。クライアントから連絡を受けると、ツアーガイドは次の式を使用して ハッシュ値( ) を計算します。${\displaystyle 0<l\leq L}$${\displaystyle x}$${\displaystyle G_{j}}$${\displaystyle h_{l}}$${\displaystyle 0<l\leq L}$

${\displaystyle h_{l}=hash(h_{l-1}\;||\;l\;||\;L\;||\;A_{x}\;||\;ts\;||\;k_{js})}$

ここで、 はクライアントのツアーの 番目のストップを意味し、 はツアー ガイドとサーバー間の共有キーです。クライアントは、サーバーからの応答メッセージを受信すると、の式を使用して最初のツアー ガイドのインデックスを計算し、ガイド付きツアーを開始します。次に、クライアントは値のセット ( 、、) をツアー ガイド に送信します。ここで、2 番目の値は、クライアントが現在ツアーのどのストップにいるかを示します。応答として、クライアントはツアー ガイド からハッシュ値 を受信します。ここで、は の式を使用して計算されます。クライアントはこのプロセスをさらに繰り返し、ツアー ガイド に連絡します。最後のストップのツアー ガイドからの応答メッセージには最後のハッシュ値 が含まれており、クライアントはパズルの答えとして( ) をサーバーに送信します。${\displaystyle l}$${\displaystyle l}$${\displaystyle k_{js}}$${\displaystyle G_{j}}$${\displaystyle x}$${\displaystyle S_{1}}$${\displaystyle S_{l}}$${\displaystyle h_{0}}$${\displaystyle 1}$${\displaystyle L}$${\displaystyle G_{S_{1}}}$${\displaystyle h_{1}}$${\displaystyle G_{S_{1}}}$${\displaystyle h_{1}}$${\displaystyle h_{l}}$${\displaystyle x}$${\displaystyle L-1}$${\displaystyle G_{S_{2}},G_{S_{3}},...,G_{S_{L}}}$${\displaystyle G_{S_{L}}}$${\displaystyle h_{L}}$${\displaystyle x}$${\displaystyle h_{0},\;h_{L}}$

• パズルの検証: サーバーが、パズルの答え ( 、) が添付されたクライアントからのリクエストを受信すると、サーバーはまずが の式を使用して計算したと等しいかどうかを確認します。等しい場合、サーバーはの式を繰り返し使用して を計算し、が と等しいことを確認します。両方のハッシュ値が有効な場合、サーバーはクライアントのリクエストを処理するためにリソースを割り当てます。サーバーは共有キー を知っているため、ツアーガイドに問い合わせることなくハッシュのチェーンを計算できます。サーバーとツアーガイドで同じハッシュ値を計算するには、サーバーとツアーガイドの間で緩やかな時間同期が必要です。${\displaystyle x}$${\displaystyle h'_{0}}$${\displaystyle h'_{L}}$${\displaystyle h'_{0}}$${\displaystyle h_{0}}$${\displaystyle h_{0}}$${\displaystyle h_{L}}$${\displaystyle h_{l}}$${\displaystyle h'_{L}}$${\displaystyle h_{L}}$${\displaystyle k_{1s},k_{2s},\dots ,k_{Ns}}$${\displaystyle h_{1},h_{2},...,h_{L}}$

クライアントパズルプロトコルなどのCPU依存の計算パズルプロトコルは、サービス拒否攻撃の影響を軽減することができます。これは、攻撃者がサーバーを圧倒しようとするほど、サーバーが計算しなければならないパズルが増え、自身の計算リソースをより多く使用する必要があるためです。強力な計算能力を持つクライアントは、貧弱なクライアントよりもはるかに高い速度でパズルを解くことができ、望ましくないほどサーバーのリソースの大部分を占有する可能性があります。^{[1] [2] [3] [4]}

計算パズル プロトコルのもう 1 つの重大な欠点は、すべてのクライアント (正当なクライアントを含む) が、意味のあるサービスやアプリケーションには貢献しない CPU を集中的に使用する計算を実行する必要があることです。

ガイド付きツアーパズルプロトコルは、ラウンドトリップ遅延を通じてクライアントに遅延を強制し、クライアントのリクエストがサーバーで持続可能な速度で到着するようにします。難しい計算問題ではなくラウンドトリップ遅延を使用する利点は、小さなパケットのラウンドトリップ遅延が、中間ルーターでの処理遅延、キューイング遅延、および伝播遅延によって主に決定されるため、エンドホスト (クライアント) の制御が及ばないことです。そのため、豊富な計算リソースを持つ攻撃者であっても、プロビジョニングが不十分な正当なクライアントよりも優先することはできません。^[要出典]

さらに、ガイド付きツアー パズル プロトコルでは、クライアントに必要な計算はごくわずかです。ガイド付きツアーの長さは通常数十以下の小さな数値であるため、ガイド付きツアーを完了するための帯域幅のオーバーヘッドもごくわずかです。その結果、クライアントは重い計算 (CPU バウンドまたはメモリ バウンドのパズル プロトコルで通常必要) の負担を負いません。^{[引用が必要]}

• プルーフ・オブ・ワークシステム
• クライアントパズルプロトコル
• キャプチャ

• 2009 年コンピュータ セキュリティ アプリケーション カンファレンス プログラム