Loading article…
Hashcashは、電子メールスパムやサービス拒否攻撃を制限するために使用されるプルーフ・オブ・ワークシステムです。Hashcashは1997年にAdam Backによって提案され[ 1 ]、Backの2002年の論文「Hashcash – サービス拒否攻撃対策」でより正式に説明されました[ 2 ] 。Hashcashでは、クライアントは乱数を文字列に複数回連結し、この新しい文字列をハッシュ化する必要があります。そして、一定数のゼロで始まるハッシュが見つかるまで、これを何度も繰り返す必要があります[ 3 ] 。
「ユーザーに、中程度の難易度ではあるが、不可能ではない関数を計算することを要求する」というアイデアは、シンシア・ドワークとモニ・ナオールが1992年の論文「処理または迷惑メール対策による価格設定」で提案した。[ 4 ]
Hashcashは、計算に必要な作業量を選択的に調整できる暗号学的ハッシュベースのプルーフ・オブ・ワークアルゴリズムですが、証明は効率的に検証できます。電子メールの場合、送信者が電子メール送信前にスタンプの計算に一定のCPU時間を費やしたことを証明するために、Hashcashスタンプのテキストエンコードが電子メールのヘッダーに追加されます。つまり、送信者がスタンプを生成して電子メールを送信するのに一定の時間を要しているため、スパマーである可能性は低いと言えます。受信者は、ごくわずかな計算コストでスタンプの有効性を検証できます。しかし、必要なプロパティを持つヘッダーを見つける唯一の既知の方法は、ブルートフォース攻撃、つまり答えが見つかるまでランダムな値を試すことです。個々の文字列をテストするのは簡単ですが、満足のいく答えはまれであるため、答えを見つけるには相当数の試行が必要になります。
この仮説は、大量のメールを1通あたりのコストを極めて低く抑えて送信することをビジネスモデルとするスパマーは、送信するスパムメール1通あたりにわずかなコストがかかるようになれば、利益を上げられなくなるというものである。受信者は、送信者がそのような投資を行ったかどうかを確認し、その結果をメールのフィルタリングに役立てることができる。
ヘッダー行は次のようになります: [ 5 ]
X-Hashcash: 1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi
ヘッダーには以下が含まれます。
YYMMDD[hhmm[ss]]。ヘッダーには、受信者のメールアドレス、メッセージの日付、および必要な計算が実行されたことを証明する情報が含まれています。受信者のメールアドレスが存在するため、受信者ごとに異なるヘッダーを計算する必要があります。日付によって、受信者は最近受信したヘッダーを記録し、ヘッダーがメールメッセージ固有のものであることを確認できます。
送信者はヘッダーを準備し、乱数で初期化されたカウンタ値を付加します。次に、ヘッダーの 160 ビットSHA-1ハッシュを計算します。ハッシュの最初の 20 ビット (つまり、最上位 5 桁の 16 進数) がすべてゼロであれば、これは有効なヘッダーです。そうでない場合は、送信者はカウンタをインクリメントしてハッシュを再度試行します。 2 160通りのハッシュ値のうち、この条件を満たすハッシュ値は 2 140通りあります。したがって、ハッシュの先頭が 20 個のゼロになるヘッダーをランダムに選択する確率は 2 20分の 1 (約 10 6、つまり約 100 万分の 1) です。送信者が有効なハッシュ値を取得するために試行する必要がある回数は幾何分布でモデル化されます。したがって、送信者は平均して 2 20 回のハッシュ値を試して有効なヘッダーを見つける必要があります。ハッシュ値の計算に必要な時間を妥当な値で見積もると、これを見つけるのにかかる時間は約1秒です。有効なヘッダーを見つけるための、この総当たり方式よりも効率的な方法は知られていません。
デスクトップPCの一般ユーザーにとって、ハッシュキャッシュ文字列の生成に必要な処理時間は大きな不便にはならないだろう。しかし、スパマーにとっては、大量のスパムメールが送信されるため、大きな負担となる。
技術的には、このシステムは以下の手順で実装されます。
"1:20:060408:adam@cypherspace.org::1QTjaYd7niiQA/sc:ePa"を計算します。これは1GHz のマシンで約2マイクロ秒かかり、メールの残りの部分を受信するのにかかる時間よりもはるかに短い時間です。最初の20ビットがすべてゼロでない場合、ハッシュは無効です。（マシンの処理速度が向上するにつれて、後のバージョンではより多くのビットがゼロである必要がある場合があります。）"060408"2006年4月8日を表す）を確認します。現在の日付から2日以内でない場合、その日付は無効です。（2日間の猶予期間は、時計のずれや異なるシステム間のネットワークルーティング時間を補正するためのものです。）ハッシュ文字列がこれらのテストすべてに合格すれば、有効なハッシュ文字列とみなされます。これらのテストは、電子メールの本文を受信するよりもはるかに少ない時間とディスク容量で済みます。
このようなハッシュ部分原像を計算するのに必要な時間は、ゼロビットの数に対して指数関数的に増加します。そのため、スパマーが有効なヘッダー行を生成するのにコストがかかりすぎるまで、ゼロビットを追加することができます（ゼロビットを追加するごとにハッシュの計算に必要な時間が2倍になります）。
ヘッダーが有効であることを確認するのははるかに高速で、有効なヘッダーに必要なゼロビットの数に関係なく、常に同じ時間がかかります。これは、ハッシュ演算が1回しか必要ないからです。
Hashcashシステムは、正規の電子メールに適用されるマイクロペイメントの提案と比べて、実際のお金が一切関わらないという利点があります。送信者も受信者も支払う必要がないため、マイクロペイメントシステムに伴う管理上の問題や、電子メールの料金徴収に関連する倫理的な問題を完全に回避できます。
一方、Hashcashは送信されるメールごとに膨大な計算リソースを必要とするため、クライアントが有効なヘッダーを計算するのに費やす平均時間の理想的な値を調整するのはやや困難です。これは、低スペックの組み込みシステムからのアクセス性を犠牲にするか、あるいはスパム対策として効果的なフィルタリングを行うのに十分な負荷がホストにかからないリスクを負うことを意味します。
Hashcashは、メールのユーザーエージェントやスパムフィルターへの実装も非常に簡単です。中央サーバーは不要です。Hashcashは段階的に導入できます。Hashcashヘッダーは、それを理解できないメールクライアントが受信した場合、無視されます。
ある妥当な分析[ 6 ]では、次のケースのうち1つだけが起こり得ると結論付けています。つまり、スパムではない電子メールは送信者の処理能力不足のために滞留するか、スパム電子メールは必ず通過してしまうかのどちらかです。それぞれの例としては、サーバーが膨大な数の正当な電子メールを送信する集中型電子メールトポロジー（メーリングリストなど）と、スパマーが処理能力を大幅に向上させることができるボットネットやクラスタファームが挙げられます。
これらの問題のほとんどは解決可能です。例えば、ユーザーがCPU負荷の高さに気づいて対策を講じることで、ボットネットはより早く消滅する可能性があります。また、メーリングリストサーバーを購読者のホスト上のホワイトリストに登録することで、ハッシュキャッシュの課題から解放されることができます。
もう一つの懸念事項は、コンピュータの処理速度がムーアの法則に従って向上し続けることです。そのため、必要な計算の難易度も時間とともに上昇していく必要があります。しかし、発展途上国では旧式のハードウェアが使用されることが予想されるため、電子メールシステムへの参加はますます困難になるでしょう。これは、最新のハードウェアを購入できない先進国の低所得者層にも当てはまります。
ハッシュキャッシュと同様に、暗号通貨もプルーフ・オブ・ワーク・システムとしてハッシュ関数を使用しています。暗号通貨の台頭により、 ASICベースのマイニングマシンへの需要が高まっています。ほとんどの暗号通貨はSHA-256ハッシュ関数を使用していますが、同じASIC技術を用いて、一般消費者向けCPUよりも3桁高速なハッシュキャッシュソルバーを作成することも可能であり、スパマーにとっての計算上のハードルを下げることができます。
メールアプリケーションのハッシュキャッシュは、悪意のある送信者を抑止するために受信者が手動で作業量を設定することに依存しているのに対し、ビットコイン暗号通貨ネットワークは、競争力のあるビットコインマイニングを可能にするために、ハッシュベースのプルーフ・オブ・ワークという異なるチャレンジを採用しています。ビットコインマイナーは、ネットワーク上のユーザーから未確認のトランザクションを収集するコンピュータプログラムを実行します。これらのトランザクションはまとめて「ブロック」を形成し、マイナーに報酬をもたらしますが、ブロックはハッシュがネットワークの難易度目標を満たした場合にのみネットワークに受け入れられます。したがって、ハッシュキャッシュと同様に、マイナーはブロックに含めると許容可能なハッシュになる「nonce」を総当たりで発見する必要があります。
Hashcash は、正規のユーザーがスタンプをマイニングするのにかかる余分な時間によって不便を感じることはほとんどないため、自動スパムフィルタリングシステムによる誤検出の潜在的な解決策として使用されました。 [ 7 ] SpamAssassin はバージョン 2.70 からバージョン 3.4.2 まで Hashcash スタンプをチェックすることができ、有効で未使用の Hashcash スタンプにはマイナスのスコア (つまり、スパムである可能性が低い) を割り当てました。ただし、hashcash プラグインはデフォルトで有効になっていますが、使用するには、Hashcash リソースフィールドと一致する必要があるアドレスパターンのリストで構成する必要があります。[ 8 ] 2019 年 6 月 26 日に SpamAssassin のトランクからサポートが削除され、バージョン 3.4.3 以降に影響が出ています。[ 9 ]
SourceForgeのPenny Post ソフトウェア プロジェクト[ 10 ]は、Mozilla Thunderbirdメール クライアントに Hashcash を実装しています。[ 11 ]このプロジェクトは、送信者が 1 ペニーしか支払わなくて済む従来の郵便サービス、いわゆるペニー ポストの歴史にちなんで名付けられました。
Microsoft は、現在非推奨となっている[ 12 ]「Email Postmark」と呼ばれるオープン仕様も設計および実装しました。これは Hashcash に似ています。[ 13 ]これは、Microsoft の協調スパム削減イニシアチブ (CSRI) の一部でした。[ 14 ] Microsoft のメール Postmark バリアントの Hashcash は、Microsoft のメールインフラストラクチャ コンポーネントである Exchange、Outlook、および Hotmail に実装されています。Hashcash と Microsoft のメール Postmark の形式の違いは、Postmark は受信者に加えて本文もハッシュ化し、ハッシュ関数として修正SHA-1を使用し、複数のサブパズルを使用してプルーフ オブ ワークの変動を減らしている点です。
電子メールと同様に、ブログもコメントスパムの被害に遭うことがよくあります。一部のブログ所有者は、コメントスパム送信者を減速させるために、JavaScript言語で書かれたハッシュキャッシュスクリプトを使用しています。 [ 15 ]一部のスクリプト (wp-hashcash など) はハッシュキャッシュを実装していると主張していますが、実際には JavaScript の難読化に依存して、クライアントに一致するキーを生成させるように強制しています。これにはある程度の処理能力が必要ですが、ハッシュキャッシュアルゴリズムやハッシュキャッシュスタンプは使用していません。
デジタルマーケットプレイスでは、サービスプロバイダーはハッシュキャッシュを使用して評判を築き、顧客を引き付けることができます。評判を築くために、サービスプロバイダーはまず公開鍵をIDとして選択し、次に総当たり攻撃によって、IDに連結すると先頭に複数のゼロが付いたハッシュダイジェストになるnonceを発見します。ゼロが多いほど、評判が高くなります。[ 16 ]
Hashcashは特許を取得しておらず、リファレンス実装[ 17 ]および他のほとんどの実装はフリーソフトウェアです。Hashcashは多くのLinuxディストリビューションに付属しているか、利用可能です。
RSA Security は、クライアントパズル (ハッシュキャッシュではない)について説明したRFC [ 19 ]の文脈で、IETFに対してクライアントパズル[ 18 ]に関する知的財産権についての声明を出しました。RFC のタイトルにはハッシュキャッシュが含まれており、ハッシュキャッシュを参照していますが、そこで説明されているメカニズムは既知の解を持つ対話型チャレンジであり、クライアントパズルにより近いものです。ハッシュキャッシュは非対話型であるため、既知の解はありません。いずれにせよ、ハッシュキャッシュは[ 1 ] (1997 年 3 月) よりクライアントパズルの発表[ 20 ] (1999 年 2 月) およびクライアントパズルの特許出願 US7197639 [ 21 ] (2000 年 2 月) より前に発表されているため、RSA の IPR 声明はハッシュキャッシュには適用できません。