群衆（匿名ネットワーク）

Crowds は、匿名の Web 閲覧用に提案された匿名ネットワークです。Crowds 匿名プロトコルの背後にある主なアイデアは、各ユーザーの通信を類似ユーザーのグループ内でランダムにルーティングすることで、それらの通信を隠すことです。そのため、共同作業グループのメンバーもエンド レシーバーも、パケットがグループ内のどこで発信されたかはわかりません。Crowds は、Michael K. ReiterとAviel D. Rubinによって設計されました。内部攻撃者や不正なレシーバーからは防御しますが、グローバル攻撃者やローカル盗聴者に対しては匿名性を提供しません (「Crowds: Web トランザクションの匿名性」を参照)。Crowds は、先行攻撃に対して脆弱です。これは Reiter と Rubin の論文で説明され、Matthew K. Wright、Micah Adler、Brian Neil Levine による「先行攻撃: 匿名通信システムに対する脅威の分析」でさらに詳しく説明されています。Crowds は、ユーザーがコンピューターの群衆に溶け込むという概念を導入しました。^[1]

1. 各ユーザーは、メンバーシップ管理を担当する単一のサーバーであるブレンダーに登録することで、他のユーザーの群衆に参加します。ユーザーが登録すると、群衆内の他のすべてのメンバーに通知されます。ブレンダーは、仮想パスに沿ってルーティングされたパケットの暗号化と復号化に使用される対称キーを個々のジョンドペアに配布するため、キー配布も担当します。^[2]
2. 各ユーザーは、ユーザーのコンピューター上で実行されるアプリケーションである、そのユーザーのマシン上の jondo によって表されます。
3. 各 jondo は、エンド サーバーにリクエストを送信するか、ランダムに選択された jondo (場合によっては自分自身) にリクエストを転送します。その他の jondo タスクには、Cookie や識別ヘッダー フィールドなどの個人情報の削除があります。
4. ジョンドは、リクエストが前のジョンドによって開始されたのか、それともそれより前のジョンドによって開始されたのかを判断できません。
5. リクエストと応答は、確率を含むアルゴリズムを使用して構築された同じ仮想パスに従います。仮想パスは、新しく追加されたメンバーの匿名性を確保するために、定期的に破棄され、再構築されます。

Crowds では次の用語が使用され、定義されています。

送信者

メッセージの発信者

受信機

メッセージの最終受信者

無罪の可能性

攻撃者は、いずれかのノードがメッセージを開始したという確信を 50% 以上持つことができません (ノードがメッセージを開始した可能性と開始しなかった可能性は同じであり、各ユーザーが無実である可能性の方が高いです)。

ローカル盗聴者

ノードの適切なサブセットのすべての受信メッセージと送信メッセージを監視できる攻撃者

破損したノード

メッセージの転送から得た情報を使用して送信者を特定するノードは破損している。

${\displaystyle C}$

破損したノードの数

${\displaystyle N}$

ノード数（良好なノード数）${\displaystyle N-C}$

${\displaystyle p_{f}}$

転送の確率

クラウドは、各ノードがメッセージの発信者である可能性を等しく見せることで機能します。前述のように、各ノードはジョンド(「John Doe」から) を開始してネットワークに参加します。ジョンドは、他のユーザーからのリクエストを転送および受信する小さなプロセスです。ジョンドが開始されると、ネットワーク内のすべてのノードに新しいノードの参加が通知され、そのノードを転送者として選択し始めます。実際にメッセージを送信するには、ノードがネットワーク内のすべてのノードからランダムに (均一な確率で) 選択し、それらのノードにメッセージを転送します。メッセージを受信すると、ノードは偏ったコインを投げ (確率)、表が出た場合は別のランダムなノードに転送し、それ以外の場合は最終的な宛先に転送します。各ノードは、別のノードに転送するときに前のノードを記録し、このようにしてトンネルが構築されます。これは、送信者と受信者の間の通信に使用されます。 ${\displaystyle p_{f}>{\frac {1}{2}}}$

OnReceive(Node P, Message M)

1. 偏ったコインを投げる（） ${\displaystyle \Pr(Heads)=p_{f}}$
   1. 表の場合は一様にランダムなノードを選択し、それらに転送する
   2. それ以外の場合は目的地へ転送
2. トンネルを建設できるようにPを記録する

説明したクラウドのメカニズムを踏まえて、攻撃者が Web トランザクションの送信者と受信者についてどのような情報を入手できるかという問題を検討します。

エンド サーバーへの最終リクエストを除き、パス上で転送されるすべてのメッセージは暗号化されることを思い出してください。したがって、盗聴者はユーザーのコンピューターから発信されるすべてのメッセージを見ることができますが、ユーザーのジョンドが最終的にユーザーのリクエスト自体を送信した場合のみ、エンド サーバーに送信されたメッセージを見ることができます。ユーザーのジョンドが最終的にリクエストを送信する確率は 1/n であり、n はパスが作成された時点の群衆のサイズです。したがって、盗聴者が受信者の ID を知る確率は群衆のサイズの関数として減少することがわかります。さらに、ユーザーのジョンドが最終的にリクエストを送信しない場合、ローカルの盗聴者はエンド サーバーの暗号化されたアドレスのみを表示します。これにより、(非公式に) 疑いの余地のない受信者の匿名性が得られると考えられます。(疑いの余地がない - どのユーザーも他のユーザーよりも疑わしいということはありません)。

群衆の中に、協力して破損したジョンドが一群いるとします。各ジョンドは、そのジョンドを経由してルーティングされるパス上のプレーンテキスト トラフィックを監視できるため、エンド サーバーのアドレスを含むそのようなトラフィックはすべて、この攻撃者に公開されます。ここで検討する問題は、攻撃者がパスを開始したユーザーを特定できるかどうかです。協力者の目標は、パスを開始したメンバーを特定することです。次に、協力者が、直前のユーザーが実際にパスの開始者であると確信できるかどうかを分析します。

1. H _k 、k >= 1は、パス上の最初の共同作業者がパス上の k 番目の位置を占め、開始者自身が 0 番目の位置 (および場合によっては他の位置) を占めるイベントを表します。
2. H _k+ = H _kまたはH _k+1またはH _k+2または . . .と定義します。
3. パス上の最初の共同作業者の直前にパス開始者がいるというイベントを示します。

H ₁ => Iですが、その逆I => H ₁は真ではないことに注意してください。これは、開始ジョンドがパス上に複数回出現する可能性があるためです。パスが次のように構成される場合もあります。

イニシエーター jondo(0 - 位置) ----> jondo(1 - 位置) ---->

開始者 jondo(2 - 位置) ----> 協力者 jondo(3 - 位置)

パス上の最初の共同作業者が 3 番目の位置にあることに注意してください。

4. この表記法に基づいて、共同研究者らは次のことを明らかにしたいと考えています。

P(I|H ₁₊ ) - 協力者がパス上にいる場合、パスの開始者が最初の協力者の直前の協力者である確率はどれくらいですか?

定義: P(I|H ₁₊ )<=1\2
の場合、パス開始者は無実である可能性が高い。

パス開始者の無実の可能性を高めるには、システムで特定の条件を満たす必要があります。特に、 pf > 1/2 (システム内で転送される確率) とします。

（c - 群衆の中の協力者の数）

( n - パスが形成されるときの群衆メンバーの総数)

以下の定理は、パス開始者の無実の可能性を保証するために、pf、c、および n に十分な条件を与えます。

定理: パスの開始者は、c人の協力者に対して無実である可能性が高い。

${\displaystyle n\geq {\frac {p_{f}}{p_{f}-{\frac {1}{2}}}}\left(c+1\right)}$

証明: pf > 1/2   であることを示すには、${\displaystyle n\geq {\frac {p_{f}}{p_{f}-{\frac {1}{2}}}}\left(c+1\right)}$

ご了承ください：

P(H _i ) =${\displaystyle (p_{f}{\frac {n-c}{n}})^{i-1}({\frac {c}{n}})}$

最初の協力者がパスのi 番目の位置にいるためには、パスはまず の確率で i-1 人の非協力者のところを毎回巡回し、各非協力者は確率pfでパスを転送することを選択し、その後確率 で協力者に向かう必要があります。 ${\displaystyle {\frac {n-c}{n}}}$${\displaystyle {\frac {c}{n}}}$

次の2つの事実は、このことからすぐに分かります。

P(H ₁₊ ) =${\displaystyle {\frac {c}{n}}\sum _{k=0}(p_{f}{\frac {n-c}{n}})^{k}=({\frac {c}{n}})({\frac {1}{1-{\frac {p_{f}(n-c)}{n}}}})}$

P(H ₂₊ ) =${\displaystyle {\frac {c}{n}}\sum _{k=1}(p_{f}{\frac {n-c}{n}})^{k}=({\frac {c}{n}})({\frac {\frac {p_{f}(n-c)}{n}}{1-{\frac {p_{f}(n-c)}{n}}}})}$

P(H ₁ ) =${\displaystyle {\frac {c}{n}}}$

P(I|H ₁ ) =${\displaystyle 1}$

P(I|H ₂ ) =${\displaystyle {\frac {1}{n-c}}}$

ここで、P(I)は次のように表される。

P(I) = P(H ₁ )P(I|H ₁ ) + P(H ₂₊ )P(IH ₂₊ ) =${\displaystyle {\frac {c(n-np_{f}n+cp_{f}+pf)}{n^{2}-pfn(n-c)}}}$

I=>H _1+なので

P(I|H ₁₊ )= = =${\displaystyle {\frac {P(I\land H1+)}{P(H1+)}}}$${\displaystyle {\frac {P(I)}{P(H1+)}}}$${\displaystyle {\frac {n-p_{f}(n-c-1)}{n}}}$

だから、もし${\displaystyle n\geq {\frac {p_{f}}{p_{f}-{\frac {1}{2}}}}\left(c+1\right)}$

するとP(I|H ₁₊ )<=1\2と なる。

例えば、pf=3\4の場合、n >= 3(c + 1) である限り無罪の可能性が保証されます。

動的パスは、連携ジョンドに対するシステムが提供する匿名性プロパティを低下させる傾向があります。その理由は、連携者が同じジョンドによって開始された多くの異なるパスをリンクできる場合、無実の可能性がなくなるためです。連携ジョンドは、関連するパスの内容またはパス上の通信のタイミングに基づいて、同じ未知のジョンドによって開始されたパスをリンクできる可能性があります。これを防ぐために、パスを静的にしました。これにより、攻撃者は同じジョンドにリンクする複数のパスを持つ必要がなくなります。

HTML ページには、ページが取得されると、ユーザーのブラウザが自動的に別のリクエストを発行する URL (画像のアドレスなど) が含まれることがあります。これらのリクエストの即時性は、共同作業ジョンドによるタイミング攻撃の機会を最も多く提供します。パス上の最初の共同作業ジョンドは、自動的に取得される URL を含む Web ページをそのパスで返すと、その URL のリクエストを受信するまでの期間を計測できます。期間が十分に短い場合、これにより、共同作業者の直前の作業者がリクエストの発信者であることが明らかになる可能性があります。

ジョンドは、ユーザーのブラウザから直接受信したか、エンド サーバーに直接送信されたリクエストに対する HTML 応答を受信すると、HTML ページを解析して、この応答を受信した結果としてユーザーのブラウザが自動的に要求するすべての URL を識別します。パス上の最後のジョンドはこれらの URL を要求し、元のリクエストを受信したのと同じパスに沿ってそれらを返送します。ユーザーのジョンドは、ユーザーのブラウザからこれらの URL のリクエストを受信すると、これらのリクエストをパスに転送せず、URL コンテンツがパスに到着するのを待機し、それらをブラウザにフィードします。このように、パス上の他のジョンドはブラウザによって生成されたリクエストを見ることはなく、したがってそれらからタイミング情報を収集することはできません。

私たちが評価するスケールの尺度は、各ジョンドが任意の時点ですべてのパスに出現する予想される総数です。たとえば、ジョンドが 1 つのパスで 2 つの位置を占め、別のパスで 1 つの位置を占める場合、これらのパスに合計 3 回出現します。

定理：n の大きさの群衆の中で、あらゆる道で任意のジョンドが出現する期待総数は、 ${\displaystyle O({\frac {1}{(1-p_{f})^{2}}}(1+{\frac {1}{n}}))}$

各ジョンドがパス上に出現する予想回数は、群衆の大きさに応じてほぼ一定です。これは、群衆がかなり大きくなる可能性があることを示唆しています。

Crowds は、すべてのメンバーがイニシエーターであった可能性が等しく見えるため、不正な受信者に対して完全な匿名性を提供します (つまり、匿名性の度合い を参照)。不正なノードの連携に対して示したように、Crowds は、 (この導出については論文を参照)限り無実の可能性が高いことを提供し、匿名性の度合い を提供します。先行攻撃に対して、Crowds は で屈します。この攻撃は、不正なノードがパス内の前のホップを保持することで機能します。ネットワーク再構築のラウンドで、このノードが他のどのノードよりも送信者になるため、イニシエーターが誰であるかが明らかになります。Reiter と Rubin はこれに触れ、パスの再形成 (パス内のノードがネットワークを離れたときに発生) の間隔を長く(可能であれば無限に) することを推奨しています。Crowds はリンク上で暗号化を使用できないため、グローバルな盗聴者から保護できません。これは、Crowds 内の各ノードが他のすべてのノードと通信できるためです (完全に接続されたグラフ)。このため、対称キーの設定にはペアワイズ キーが必要です。これは実現するには数が大きすぎます。また、ローカルの盗聴者に対しても、Crowds は保護を提供しません。盗聴者は、入っていないノードから送信されるメッセージを確認し、これにより、そのノードが送信者であると確実に識別されるからです。 ${\displaystyle d\gets 1}$${\displaystyle N\geq {\frac {p_{f}}{p_{f}-{\frac {1}{2}}}}\left(C+1\right)}$ ${\displaystyle d\gets {\frac {{\frac {N-p_{f}\cdot (N-C-1)}{N}}\cdot \lg \left[{\frac {N}{N-p_{f}\cdot (N-C-1)}}\right]+p_{f}\cdot {\frac {N-C-1}{N}}\cdot \lg \left[N/p_{f}\right]}{\lg(N-C)}}}$${\displaystyle O\left({\frac {N}{C}}\lg(N)\right)}$${\displaystyle O(N^{2})}$

• オニオンルーティング
• Tor（匿名ネットワーク）
• 匿名性の程度
• ミックスネットワーク

1. ^ Claudia Diaz、Stefaan Seys、Joris Claessens、Bart Preneel (2002 年 4 月)。Roger Dingledine、Paul Syverson (編)。「匿名性の測定に向けて」。Privacy Enhancing Technologies Workshop (PET 2002) の議事録。Springer-Verlag、LNCS 2482。2006 年 7 月 10 日のオリジナルからアーカイブ。2005年 11 月 10 日に取得。
2. ^ Michael Reiter および Aviel Rubin (1998 年 6 月)。「Crowds: Web トランザクションの匿名性」(PDF)。ACM Transactions on Information and System Security。1 ( 1)。2005 年 12 月12日のオリジナル(PDF)からアーカイブ。2005年 11 月 23 日閲覧。
3. ^ Matthew K. Wright、Micah Adler、Brian Neil Levine、Clay Shields (2004)。「先行攻撃: 匿名通信システムに対する脅威の分析」(PDF)。ACM Transactions on Information and System Security。7 ( 4)。ACM Press: 489–522。doi : 10.1145 /1042031.1042032。S2CID 7711031。2005-09-24に オリジナル (PDF) からアーカイブ。2005-11-23に取得。
4. ^ Matthew Wright、Micah Adler、Brian Neil Levine、Clay Shields (2002 年 2 月)。「An Analysis of the Degradation of Anonymous Protocols」(PDF)。Proceedings of the Network and Distributed Security Symposium - NDSS '02。IEEE。2006 年 2 月 19 日のオリジナル(PDF)からアーカイブ。2005年 11 月 23 日に取得。

• 匿名書誌
• 暗号学eプリントアーカイブ