ミックスネットワーク

シンプルな復号ミックスネット。メッセージは公開鍵のシーケンスで暗号化されます。各ミックスノードは、自身の秘密鍵を使用して暗号化レイヤーを1つ解除します。ノードはメッセージの順序をシャッフルし、結果を次のノードに送信します。

ミックスネットワーク^{[ 1 ]}は、ミックス^{[ 2 ]}と呼ばれるプロキシサーバーのチェーンを用いて追跡困難な通信を実現するルーティングプロトコルです。これらのプロキシサーバーは複数の送信者からのメッセージを受け取り、それらをシャッフルし、ランダムな順序で次の宛先（場合によっては別のミックスノード）に送信します。これにより、リクエストの送信元と宛先の間のリンクが切断され、盗聴者がエンドツーエンドの通信を追跡することが困難になります。さらに、ミックスはメッセージを受信したノードと、シャッフルされたメッセージを送信する直近の宛先のみを認識するため、悪意のあるミックスノードによる攻撃に対してネットワークは耐性を持ちます。^{[ 3 ] [ 4 ]}

各プロキシへのメッセージは公開鍵暗号を用いて暗号化され、その結果得られる暗号化はマトリョーシカ人形のように階層化されます（各「人形」は同じ大きさです）。メッセージは最内層となります。各プロキシサーバーは自身の暗号化層を剥ぎ取り、次にメッセージを送信する場所を明らかにします。1つを除くすべてのプロキシサーバーがトレーサーによって侵害された場合でも、比較的弱い攻撃者に対しては追跡不可能な状態を維持できます。

電子メールの文脈におけるミックス「暗号システム」の概念は、1981年にデイビッド・ショームによって「トラフィック分析問題」（トラフィック分析）のために初めて説明されました。^{[ 5 ]} この概念に基づくアプリケーションには、匿名リメーラ（ Mixmasterなど）、オニオンルーティング、ガーリックルーティング、キーベースルーティング（ Tor、I2P、Freenetなど）などがあります。^{[ 6 ]}ミックスネットワーク概念の大規模な実装は、プライバシー保護技術と分散型インフラストラクチャの進歩に後押しされて、2020年代に登場し始めました。

歴史

デイビッド・ショームは、 1979年に修士論文^{[ 7 ]}の中で「ミックス」という概念を発表しました。これは、彼が公開鍵暗号、マーティン・ヘルマン、ホイットフィールド・ディフィー、ラルフ・マークルらの研究を通して暗号学の分野に初めて触れた直後のことでした。公開鍵暗号は情報のセキュリティを暗号化しますが、ショームは通信に含まれるメタデータに個人のプライバシーを侵害する脆弱性があると考えました。個人のプライバシーを侵害する脆弱性には、送受信されたメッセージの時刻、メッセージのサイズ、元の送信者のアドレスなどが含まれていました。^{[ 2 ]}彼は論文の中で、マーティン・ヘルマンとホイットフィールドの論文「暗号学の新しい方向性」（1976年）を引用しています。

1990年代: サイファーパンク運動

イアン・ゴールドバーグやアダム・バックといった革新者たちは、ミックスネット技術に多大な貢献をしました。この時代は、暗号技術が大きく進歩し、ミックスネットの実用化に大きく貢献しました。ミックスネットは学界で注目を集め始め、その効率性とセキュリティの向上に関する研究がさらに進みました。しかし、実用化への普及は依然として限定的で、ミックスネットは主に実験段階にとどまりました。個人がミックスネットを使って匿名メールを送信しやすくするために、「サイファーパンク・リメーラー」と呼ばれるソフトウェアが開発されました。^{[ 8 ]}

2000年代: 他の匿名ネットワークへのインスピレーション

2000年代には、インターネットのプライバシーに対する懸念の高まりにより、ミックスネットワーク（ミックスネット）の重要性が浮き彫りになりました。この時代は、2000年代半ば頃にTor（オニオンルーター）が登場したことで特徴づけられました。Torはミックスネットをそのまま実装したものではありませんでしたが、 David Chaumの基本的なアイデア、特にミックスネットの概念に類似したオニオンルーティングの形態を大いに活用していました。この時期には、ミックスネットの原理を様々な程度に取り入れた他のシステムも登場し、いずれも安全で匿名性の高い通信の強化を目的としていました。

2010年代: ミックスネットワークへの学術的関心の高まり

2010年代に入ると、ミックスネットの拡張性と効率性を高めるための大きな転換が起こりました。この変化は、新たなプロトコルとアルゴリズムの導入によって推進され、これまでミックスネットの広範な展開を阻んできた主要な課題のいくつかを克服するのに役立ちました。特に2013年以降、エドワード・スノーデンによる大規模な世界規模の監視プログラムに関する暴露を受けて、ミックスネットの重要性は急上昇しました。この時期、プライバシー保護のための重要なツールとして、ミックスネットに新たな注目が集まりました。

2017年に導入されたLoopix ^{[ 9 ]}アーキテクチャは、既存のプライバシー強化技術を統合し、現代的なミックスネットワーク設計を形成しました。Loopixの主要な要素は次のとおりです。

• 「スフィンクス」^{[ 10 ]}パケット形式はリンク不可能性と階層的暗号化を保証する
• ポアソン過程に基づくパケット伝送。ランダム性を導入してトラフィック相関攻撃を防止します。
• 指数関数的な混合遅延により、トラフィック分析が困難になります。
• ループベースのカバー トラフィック。ダミー パケット (実際のデータが含まれていないプレースホルダー パケット) が継続的に挿入され、実際のデータ フローが隠されます。
• 階層化されたミックス ノードトポロジにより、ネットワーク効率を維持しながら匿名性を最適化します。

ブロックチェーン技術の台頭により、スケーラブルな分散型システムの新たな可能性が開かれ、大規模な分散型ミックスネットワークへの道が開かれました。

2020年代: 最初の大規模導入

2020年代を通して、様々な官民の研究開発プログラムが、最初の大規模ミックスネットワークの実現に貢献しました。2025年までに、0KN、HOPR、Katzenpost、Nym（後のNymVPNのオーバーレイとして）、xx.network （ David Chaumが主導）など、複数のプロジェクト^{[ 6 ]}が活発に開発され、プライバシー保護通信をより広範囲に強化することを目指しています。

仕組み

参加者Aは、参加者Bに配信するメッセージを準備します。メッセージにランダム値Rを付加し、受信者の公開鍵で暗号化し、受信者Bのアドレスを付加し、最後にそのミックスの公開鍵で暗号化します。Mは自分の秘密鍵でメッセージを開き、受信者Bのアドレスを入手した上で、Bに 送信します。${\displaystyle K_{b}}$ ${\displaystyle K_{m}}$ ${\displaystyle K_{b}(メッセージ,R)}$

メッセージ形式

${\displaystyle K_{m}(R1,K_{b}(R0,メッセージ),B)\longrightarrow (K_{b}(R0,メッセージ),B)}$

これを実現するために、送信者はミックスの公開鍵 ( ) を取得し、それを使用して、ランダム文字列 ( )、受信者宛てのネストされたエンベロープ、受信者の電子メールアドレス( B ) を含むエンベロープを暗号化します。このネストされたエンベロープは受信者の公開鍵 ( ) で暗号化され、別のランダム文字列 ( R0 ) と、送信されるメッセージの本文が含まれています。暗号化された最上位のエンベロープを受信すると、ミックスはその秘密鍵を使用してそれを開きます。エンベロープの中には、受信者のアドレス ( B ) と、 B宛ての暗号化されたメッセージがあります。ランダム文字列 ( ) は破棄されます。 ${\displaystyle K_{m}}$ ${\displaystyle R1}$ ${\displaystyle K_{b}}$ ${\displaystyle R1}$

${\displaystyle R0}$ 攻撃者がメッセージを推測するのを防ぐには、メッセージに が必要です。攻撃者はすべての受信メッセージと送信メッセージを監視できると想定されています。ランダム文字列 が使用されていない場合（つまり、 のみがに送信されている場合）、攻撃者がメッセージが送信されたと正しく推測できれば、が成り立つかどうかをテストして、メッセージの内容を知ることができます。ランダム文字列 を追加することで、攻撃者はこの種の攻撃を実行できなくなります。たとえ攻撃者が正しいメッセージを推測できたとしても（つまり、が真）、秘密の値 を知らないため、正しいかどうかを知ることはできません。実際には、はソルトとして機能します。 ${\displaystyle (K_{b}(メッセージ))}$ ${\displaystyle B}$ ${\displaystyle message'}$ ${\displaystyle K_{b}(message')=K_{b}(message)}$ ${\displaystyle R0}$ ${\displaystyle message'=message}$ ${\displaystyle R0}$ ${\displaystyle R0}$

返信先住所

今必要なのは、 Aの身元をBから秘密にしたまま、BがAに応答する方法です。

解決策としては、Aが追跡不可能な返信アドレスを生成することが挙げられます。ここで、 は自身の実アドレス、は今回のみ選択された公開ワンタイム鍵、 は暗号化のためのランダム文字列としても機能する鍵です。そして、Aはこの返信アドレスを、既に説明した手法を用いて送信するメッセージの一部として Bに送信します。${\displaystyle K_{m}(S1,A),K_{x}}$ ${\displaystyle A}$ ${\displaystyle K_{x}}$ ${\displaystyle S1}$

B はM に送信し、M はそれを に変換します。 ${\displaystyle K_{m}(S1,A),K_{x}(S0,response)}$ ${\displaystyle A,S1(K_{x}(S0,response))}$

このミックスは、アドレス部分を復号した後に見つかったビット列を鍵として用い、メッセージ部分を再暗号化します。受信者Aのみが出力を復号できます。なぜなら、 Aはとの両方を作成したからです。追加の鍵により、ミックスは返信メッセージの内容を見ることができません。 ${\displaystyle S1}$ ${\displaystyle K_{m}(S1,A)}$ ${\displaystyle K_{x}(S0,response)}$ ${\displaystyle S1}$ ${\displaystyle K_{x}}$ ${\displaystyle K_{x}}$

以下は、B がこの追跡不可能なリターン アドレスを使用して、新しい種類のミックスを介して Aへの応答を形成する方法を示しています。

A Bからのメッセージ: ${\displaystyle \longrightarrow }$

${\displaystyle K_{m}(R1,K_{b}(R0,message,K_{m}(S1,A),K_{x}),B)\longrightarrow K_{b}(R0,message,K_{m}(S1,A),K_{x})}$

B Aからの返信メッセージ: ${\displaystyle \longrightarrow }$

${\displaystyle K_{m}(S1,A),K_{x}(S0,response)\longrightarrow A,S1(K_{x}(S0,response))}$

ここで: = Bの公開鍵、= ミックスの公開鍵。 ${\displaystyle K_{b}}$ ${\displaystyle K_{m}}$

送信先は、送信元の匿名性を損なうことなく送信元に返信できます。返信メッセージは、送信元から送信先への匿名メッセージと同様のパフォーマンスとセキュリティ上の利点をすべて備えています。

脆弱性

ミックスネットワークは、たとえ攻撃者が経路全体を把握できたとしてもセキュリティを確保しますが、ミキシングは完全に完璧ではありません。攻撃者は長期的な相関攻撃を仕掛け、パケットの送信者と受信者を追跡することができます。^{[ 11 ]}

脅威モデル

攻撃者は、ミックスネットワークとの間のトラフィックを監視することで、受動的な攻撃を実行できます。複数のパケット間の到着時間を分析することで、情報を得ることができます。パケットには積極的な変更が加えられないため、このような攻撃は検知が困難です。最悪のケースでは、ネットワークのすべてのリンクが攻撃者によって観測可能であり、ミックスネットワークの戦略とインフラストラクチャが既知であると想定されます。^{[ 2 ]}

入力リンク上のパケットは、パケットの受信時刻、サイズ、または内容に関する情報に基づいて、出力リンク上のパケットと相関させることはできません。パケットのタイミングに基づく相関はバッチ処理によって防止され、内容とパケットサイズに基づく相関は暗号化とパケットパディングによって防止されます。

パケット間隔、つまり2つのネットワークリンクにおける連続する2つのパケットの観測時間差は、それらのリンクが同じ接続を伝送しているかどうかを推測するために使用されます。暗号化やパディングは、同じIPフローに関連するパケット間隔には影響しません。パケット間隔のシーケンスは接続間で大きく異なります。例えば、Webブラウジングではトラフィックがバースト的に発生します。この事実は、接続を識別するために使用できます。

アクティブ攻撃

アクティブ攻撃は、標的のフローに固有のタイミングシグネチャを含むパケットのバーストを注入することで実行できます。攻撃者は、他のネットワークリンク上でこれらのパケットを識別しようとする攻撃を実行できます。攻撃者は、後続のすべてのパケットの対称鍵を知っている必要があるため、新しいパケットを作成できない可能性があります。リプレイパケットも、ハッシュ化とキャッシュによって簡単に防御できるため、使用できません。^{[ 2 ]}

人工的なギャップ

攻撃者がフロー内で大量の連続パケットをドロップすると、対象フローに大きなギャップが生じる可能性があります。例えば、対象フローに3000個のパケットを送信するシミュレーションを実行し、攻撃者はフロー開始から1秒後にパケットをドロップします。ドロップされる連続パケット数が増えるにつれて、防御的なドロップの効果は著しく低下します。大きなギャップを導入すると、ほぼ確実に認識可能な特徴が生じます。

人工バースト

攻撃者は人工的なバーストを作り出すことができます。これは、人工的なパケットをリンク上に一定時間保持し、その後一斉に解放することでシグネチャを作成することで行われます。このシナリオでは防御的なドロップでは防御が機能せず、攻撃者は標的のフローを特定できます。この攻撃を防ぐために講じることができる防御策は他にもあります。そのような解決策の一つとして、アダプティブパディングアルゴリズムが挙げられます。パケットの遅延が大きいほど、動作の特定が容易になり、より効果的な防御が可能になります。

その他の時間分析攻撃

攻撃者は、パケット間隔以外のタイミング攻撃も検討する可能性があります。攻撃者はパケットストリームを積極的に改変することで、ネットワークの動作に生じる変化を観察することができます。パケットを破損させることでTCPパケットの再送信を強制することができ、その動作は容易に観察でき、情報を明らかにすることができます。^{[ 12 ]}

スリーパー攻撃

攻撃者は、閾値ミックスに送受信されるメッセージは観測できるものの、これらのミックスの内部動作や、そのミックスによって何が送信されるかは観測できないと仮定します。攻撃者がそれぞれのミックスに自身のメッセージを残しておき、そのうちの1つを受信したとすると、送信されたメッセージとその送信者を特定できます。攻撃者は、常に自身のメッセージ（アクティブコンポーネント）をミックスに配置する必要があり、メッセージが送信されるまで、メッセージはミックス内に存在し続けなければなりません。これは通常、アクティブ攻撃ではありません。より弱い攻撃者は、この攻撃を他の攻撃と組み合わせて使用​​することで、より多くの問題を引き起こす可能性があります。

ミックスネットワークは、受信メッセージの順序を変更することでセキュリティを確保し、受信メッセージと送信メッセージの間に有意な関連性が生じないようにします。ミックスはメッセージ間の干渉を引き起こします。この干渉によって、ミックスの観測者への情報漏洩率に限界が設けられます。サイズnのミックスでは、ミックスへの入力と出力を観測する攻撃者は、マッチを判断する際に順序nの不確実性を有します。スリーパー攻撃はこれを悪用する可能性があります。各ミックスにスリーパーを含む閾値ミックスの階層化ネットワークでは、送信者からの入力を受信する層と、メッセージを最終宛先に転送する2層目のミックスが存在します。これにより、攻撃者は受信したメッセージが、発火しなかったどのレイヤー1のミックスにも送信者から送られたはずがないと知ることができます。これらのスリーパーによって送受信メッセージが一致する確率が高くなるため、通信は完全に匿名ではなくなります。ミックスは純粋に時間に基づいて行われる場合もあります。つまり、特定の間隔で受信したメッセージの順序をランダム化し、その一部をミックスに添付して、その間隔で受信した内容に関係なく、間隔の終了時に転送します。混合可能なメッセージは干渉しますが、混合可能なメッセージがない場合、受信メッセージとの干渉はありません。^{[ 13 ]}

参考文献

1. 「デジタルミックス」とも呼ばれる
2. Sampigethaya, Krishna; Poovendran, Radha (2006年12月). 「Mixネットワークとそのセキュアアプリケーションに関する調査」. Proceedings of the IEEE . 94 (12): 2142– 2181. doi : 10.1109/JPROC.2006.889687 . ISSN  1558-2256 . S2CID  207019876 .
3. Claudio A. Ardagna他 (2009). 「信頼できないモバイルネットワークにおけるプライバシー保護」 Bettini, Claudio他 (編). 『位置情報アプリケーションにおけるプライバシー：研究課題と新たな動向』 Springer. p. 88. ISBN 9783642035111。
4. Danezis, George (2003-12-03). 「Mix-Networks with Restricted Routes」 . Dingledine, Roger (編). Privacy Enhancing Technologies: Third International Workshop, PET 2003, Dresden, Germany, March 26–28, 2003, Revised Papers . Vol. 3. Springer. ISBN 9783540206101。
5. Chaum, David L. (1981). 「追跡不可能な電子メール、返信先アドレス、デジタル仮名」 Communications of the ACM . 24 (2): 84– 90. doi : 10.1145/358549.358563 . S2CID 30340230 .この暗号システムの利用者には、通信相手だけでなく、配達前に各メールを処理する「ミックス」と呼ばれるコンピュータも含まれます。 
6. 「Mixnet Research Review」（PDF） 2024年4月15日。 2025年2月21日閲覧。
7. 「追跡不可能な電子メール、返信先アドレス、デジタル仮名」（PDF） . chaum.com .カリフォルニア大学バークレー校工学部：UCB/ERL. 1979年2月22日. p. [3] / - 2 - . 2025年5月31日閲覧。メールシステム 暗号システムのメンバーには、通信を希望する人だけでなく、通信経路上で実際に通信をシャッフルする「ミックス」と呼ばれるコンピューターも含まれます。
8. Mazieres, David. 「電子メール仮名サーバーの設計、実装、運用」(PDF) .
9. Piotrowska, Ania M.; Hayes, Jamie; Elahi, Tariq; Meiser, Sebastian; Danezis, George (2017). Loopix匿名システム. USENIX協会. pp.  1199– 1216. ISBN 978-1-931971-40-9。
10. Danezis, George; Goldberg, Ian (2008), Sphinx: A Compact and Provably Secure Mix Format , 2008/475 , 2025年2月21日閲覧
11. Tom Ritter、「オニオンルーティングとミックスネットワークの違い」、 ritter.vg 2016年12月8日閲覧。
12. Shmatikov, Vitaly; Wang, Ming-Hsiu (2006). 「低遅延混合ネットワークにおけるタイミング分析：攻撃と防御」.コンピュータセキュリティ – ESORICS 2006.コンピュータサイエンス講義ノート. 第4189巻. pp.  18– 33. CiteSeerX 10.1.1.64.8818 . doi : 10.1007/11863908_2 . ISBN  978-3-540-44601-9。
13. Paul Syverson、「Sleeping dogs lie on a bed of onions but wake when mixing onions」、 Privacy Enhancing Technologies Symposium、 2016年12月8日閲覧。