Nymは従来のmixnet設計をどのように改良しているのでしょうか？（2020.2.25）
匿名通信ネットワークの目標は、インターネット上で送信されるあらゆるデータパケットを、他のパケットと区別できないようにすることである。この目標を実現するためには、ネットワーク全体を見渡すことができる敵対者から防御するために、2つの要素が必要です：
すべてのパケットは、サイズだけでなく、そのビットの点でもリンク不可能でなければなりません。Nymでは、先日の技術紹介で説明したSphinxのパケットフォーマットでこれを実現しています。
また、パケットがいつ送信されたかという点でも、リンクされないことが必要です。そこで、パケットを "ミックスする（mixing）"という概念が登場します。
mix network "とは何なのかについて、多くの関心が寄せられ、また混乱も生じています。ミックスネットワークは、実際にパケットを混ぜて送信時刻の情報を破壊し、この情報は、攻撃者がパケットの送信者や含まれるデータまで特定することができるものです。
Lokiのようなインターネットの上に匿名のオーバーレイネットワークを構築する多くのプロジェクトは善意であるが、攻撃を防ぐために意味のある方法でパケットを「ミックス」していないのにmixnetであると主張している。 さらに混乱させるのは、HOPRのような「mix network」を謳うプロジェクトはSphinxのパケットフォーマットを使っていますが、HOPRは現在パケットをミックスしていないので、強力な敵はビットがリンクされていなくてもタイミングに基づいて簡単にパケットの匿名化を解除できてしまうことです。さらに、HOPRのSphinxの実装はパディングが不正確で、前回の記事で紹介したKuhnによる攻撃に対して現時点では脆弱である。ライトニング・ネットワークもSphinxを使用していますが、そのプライバシー特性を壊すような方法で使用しています。
“mixnet”という言葉の使い方が破綻していたり、間違っていたりするので、そろそろ整理しておきたいところです。 最近、NymのCTOがmix networkに関する非技術的な入門書を発表しましたが、これはこの技術がどのようなものかを理解したい場合に最適な出発点となります。この記事では、mix networkの技術的な機能と、Nym mixnetが従来のmix network設計とどのように異なるのかについて、もう少し深く掘り下げて説明することにします。
Chaumian mix networksの簡単な紹介
1981年、David Chaumは、インターネット通信の特徴的な特性、いわゆるメタデータを隠すことによって、リンク不能性を確保する分散型中継ネットワークであるmix network[1]という画期的なアイデアを提唱しました。ネットワークメタデータには膨大な量の機密情報が含まれており、その結果、ユーザーのオンライン上の活動や関連性を詳細に把握することができます。このメタデータの漏洩は、ゼロ知識証明技術を含む高度な暗号化技術による機密性をも損なうものです。Mix networkは、高度なトラフィック解析技術に対しても、メタデータを保護することができます。
「メタデータは、その人の人生のすべてを教えてくれる。十分なメタデータがあれば、コンテンツは必要ないのです。- 元NSA顧問弁護士 Stewart Baker
従来のmix network設計
従来のmixネットワークでは、ノードは一定のカスケード状に並んでおり、各パケットは最初のノードから最後のノードまで各ノードを経由してルーティングされます。複数のmixを使用することで、mix間の信頼を分散させ、カスケード内の1つのmixが誠実である限り、匿名性は保たれるのです。
MIXネットワークで中継される各パケットは、公開鍵暗号方式（public-key cryptography）でレイヤー暗号化（言い換えればオニオン暗号化）されています。各パケットを受信すると、mixはシングルレイヤーの暗号化を解除します。これにより、ネットワークを監視している人が、パケットのバイナリ表現を見て、パケットを追跡することはできません。
バイナリパターンを変えても、mixが先入れ先出しで暗号化パケットを転送すれば、盗聴者は異なるリンク上の暗号化パケットのタイミングを相関させることができます。実際、これこそがTorが脆弱な攻撃なのです。そこで、それを防ぐために、各mixは一定数のパケットを集め、解読すると同時に、秘密の順列に従ってパケットを並び替える（mixする！）のです。トランプのシャッフルに似ているので、"ミキシング "の代わりに "シャッフル "という言葉が使われることもありますね。
パケットがシャッフルされると、mixはカスケードの次のノードにパケットを送ります。 バッチ(batch)で受け入れられなかった他のパケットは、その後のラウンドで送信されます。これは、いわゆるバッチアンドリオーダーミキシング手法（batch-and-reorder mixing technique）である。
従来のmix network設計の限界
オリジナルのmix network設計は、リサーチコミュニティによって長年研究されてきました。そして判明したことは、それにはいくつかの限界があるということです：
固定カスケードのトポロジーは、スケールが小さい。
オニオン暗号化を行うためには、各クライアントやmix nodeで時間のかかる公開鍵操作を行う必要がある。
匿名性セットのサイズは、バッチのサイズにのみ制限される。
自分のパケットがどのバッチで受け入れられるか分からないので、パケットのEnd-to-Endのレイテンシは制限されない。
従来のミックスは、トラフィック確認攻撃やアクティブ攻撃のような様々な巧妙な攻撃の影響を受けやすい[3,4]。
そうした制約から、Nymは従来のmix network設計を採用せず、Loopix[2]と呼ばれる最新の低遅延匿名通信システムをベースにしています。では、私たちの設計は、従来のmix networkの上記の問題にどのように取り組んでいるのでしょうか？また、cMixのようなChaumian mix networkに基づく他のデザイン、Elixxirが使用しているデザイン、mixnetと主張されているHOPRのような伝統的なP2Pデザインとの比較はどうでしょうか？
Nym Mixnet
Networkテクノロジー
匿名は集団を好む（Anonymity loves company.）ので、スケーラビリティはmix networkの重要な特性の1つである。 固定カスケードのトポロジーは、スケーラビリティの味方ではありません。カスケードが最大容量に達すると、それ以上のトラフィックをサポートすることができなくなり、信頼性の問題が発生することがよくあります。
スケーラビリティを大幅に向上させるソリューションとして、複数のカスケードを導入して並列に動作させる方法がありますが、まさにElixxirはそれを実現しています。 しかし、このアプローチには1つの制限があります。トラフィックは不連続なカスケード間で分割されるため、大量のトラフィックから匿名性の面で有利になることはありません。
一方、HOPRはノード間でPeer-to-Peer接続を確立するため、非常に優れた拡張性を持っています。 しかし、P2Pトポロジーは、カスケードよりも匿名性が弱いのです。カスケードでは、ノードがすべてのパケットに対して同じパスホップ（path hop）にあるため、同じmixで出会うパケットは常にmixされます。 Peer-to-Peerネットワークでは，パケットのパス上のホップが異なれば，パケットは同じノードを通過してもmixしないことがある [5]のです 。
そのため、Nym mixnetは、研究が示すように、匿名性とスケーラビリティに最適な階層型トポロジー（ stratified topology）を導入しています[5]。階層型トポロジーのミックスノードは層状に配置されます。第i層の各ノードは、前後の層の各ノードと接続されています。
パケットはソース・ルーティング（source-routed）され、送信者が宛先までの全てのパスを選択することを意味します。各パケットは、各レイヤーからランダムに1つのノードを選ぶことで構成される独立したパスで送信されます。パケットは独立したパスで送られますが、階層化されたトポロジーにより、ネットワーク上のある地点で互いに交わるため、最終的にトラフィック全体が混ざり合います。
最も重要なことは、mixをレイヤーに集約することで、トラフィックを少数のリンクに集中させる疎なトポロジーを確保し、Nym mixnetが水平方向に拡張できるようにすることです。というのは、サーバーを少しずつ増やしていくことで、ネットワーク全体の容量を増やすことができるという意味です。
したがって、Nym mixnetのトポロジーは、強力な匿名性とスケーラビリティを両立しています。
オニオン暗号化（Onion encryption）
従来のmix network設計で必要とされる時間のかかる公開鍵操作は、高いレイテンシーオーバーヘッドを課すため、ほとんどのアプリケーションで実用的ではありません。 一つの解決策として、ElixxirのcMixデザインで使われているprecomputation phaseが考えられます。 このアイデアにより、リアルタイム通信時に計算量の多い暗号演算を回避することができますが、事前計算に必要な時間は匿名性セットのサイズに比例して大きくなり（論文参照）、各リアルタイムフェーズの前に繰り返し実行する必要があります。
一方、Nymは、公開鍵の運用に時間がかかるという問題を解決するために、Sphinxというパケットフォーマット（そう、Lightning Networkで使われているのと同じものです！）を使ってパケットをオニオン暗号化しています。Sphinxがどのような仕組みで、どのようなセキュリティ特性を持つのかについては、先日詳しい記事を書きました。一言で言えば、Sphinxは証明可能安全性（provably secure）を持った暗号パケットフォーマットです。また、オーバーヘッドが数百バイトと最もコンパクトで、これまでに提案されたパケットフォーマットの中で最も計算効率の高いフォーマットです。私たち自身のRust Sphinx実装の基準では、1つのパケットを処理するのに、平均0.157ミリ秒が必要で、1つのパケットを作成するのに、平均0.386ミリ秒が必要です！そして、これはまだ最適化のトリックがない状態です！さらに、本実装はKuhnらによって最近発見された脆弱性にも耐性があります（詳細はこちらを参照）。
SphinxはHOPRでも使用されています。しかし、我々の実装とは対照的に、HOPRによるSphinxの実装は、Kuhnらが示した攻撃に対して脆弱であり、パケットが通過するパス長（path length）に関する情報を漏洩してしまうのです。
Mixing
しかし、本当のゲームチェンジャーは、Nym mixnetが使用する再配列技術（ reordering technique）です。従来のmix networkやcMixのようなシステムで使われている バッジ処理&再配列技術（batch-and-reorder technique）の手法の代わりに、stop-and-go technique（continues-time mixesとも呼ばれる）を使っています。 つまり、ある閾値のパケットをバッチ処理する代わりに、mixは各パケットを遅延させてから次のホップに転送します。パケットが各mixで待つ必要のある時間は、送信者が指数分布からランダムに選びます。 したがって、送信者はパケットのEnd-to-Endのレイテンシーを推定することができます。
そして、なぜこの技術を使おうと思ったのか？匿名性のためです！
指数分布には、無記憶性（memoryless property）という素晴らしい性質があります。何のことかわからない人は、直感的に宝くじの例で考えてみてください：あなたが普通の宝くじプレイヤーだと想像してください。これまでに、100回遊んで100回負けたとします。しかし、あなたは、"あれだけ負けたのだから、今当たる確率はもっと高いはずだ！"と思っているはずです。しかし、もし宝くじに記録がないのであれば、100回負けても、当選確率は初めて宝くじに挑戦したときと同じということになります。 1000回、10000回、100000回、...と試したとしても同じです（すみません！）。しかし、これがパケットの混ざり具合にどう反映されるのでしょうか？
前述したように、batch-and-reorder techniqueを用いたmix networkでは、バッチサイズが匿名性セット（anonymity set）のサイズとなります。 mixがある一定の数のパケット、例えば100個収集した場合、全体として数千のパケットがmix networkで処理されたとしても、あなたの匿名性セットは100しかありません。
Nym mixnetは、より大きな匿名性セットを提供します。どのように？パケットが次々とmixに到着していく様子を想像してください。今回は、パケットをグループ単位でバッチ処理するのではなく、mixに入った各パケットは、敵にはわからないランダムな時間だけそこに滞留するようにしました。しかし、ミキシングとしての遅延はどのように機能するのでしょうか？直感的に、ランダムな遅延が追加されているけれども、早く入ったパケットは早く出て行くはずだと言うかもしれませんね？いえ、違います。これが無記憶性のマジックなのです。 パケットがある時刻にミックスから離れる確率は、その到着時刻に依存しないのです。つまり、敵がミックスから出るパケットを見たとき、そのパケットがミックスに入るのを観察したことのあるパケットのいずれかである可能性があるということである。その結果、バッチミックス（batch mixes）と比較して、Nymで使用される連続時間ミックス（continuous-time mixes）は、より大きな匿名性セットを持つことになります。 つまり、あなたは他のパケットの小さなグループの中だけでなく、ネットワークに入るすべてのパケットの中でも匿名なのです。敵がどれほど混乱するか、想像してみてください！
HOPRはElixxirやNymと異なり、ミキシング技術を実装していないため、トラフィック解析に対する耐性がなく、結果的に匿名性を確保することができない設計となっています。しかし、現在、将来のバージョンにおいて原始的なミキシング技術を追加するよう取り組んでいるそうです。
トラフィックのカバー
オンラインユーザーは持続的な行動パターンを持っており、時間の経過とともに、あなたのコミュニケーションに関する情報を開示する可能性があります。 例えば、敵がアリスが送信したパケットの突然のバーストと、同時に他のユーザやサービスが受信したパケットの突然のバーストを見た場合、アリスの通信の宛先を推測することができます（トラフィック確認攻撃、traffic confirmation attacks）。
そこで、Nymクライアントは、ユーザーが実際にいつmixnetを利用しているか、どれだけのパケットを送受信しているかを隠すために、ポアソン過程（Poisson process、一種のランダム化）に従ってパケット送信のスケジューリングを行います。 もし、ユーザーがmix networkに転送するパケットを予定していない場合、クライアントは代わりにループカバーパケット、すなわち、最終的な宛先が送信者であるダミーのペイロードのパケットを送信します。 ループカバートラフィックを使用することで、敵の視点から見ると、ユーザーは常にアクティブであるように見えます。つまり、敵はユーザーが実際の通信パケットを送信または受信しているときに区別することはできません。これはしばしば観測不可能性（Unobservability）と呼ばれ、既存の実装されたmixnetのうち、Nym mixnetのみがこの性質を保証しています。
また、Mixは、例えばフラッディング攻撃（flooding attacks）などのアクティブな攻撃を検出するために、クライアントのトラフィックと区別がつかないループカバートラフィック（ loop cover traffic）を送信します[5]。 さらに、このようなループカバーパケットによって、ネットワークのサービス品質をチェックし、悪意のある行動を検出することができます（詳しくは次回の記事で説明します）。
Nym mixnetは、連続的な時間のミックスと調整可能なカバートラフィックの組み合わせにより、強力な匿名性を保証するのに十分なトラフィックをネットワーク上に常に確保し、様々な待ち時間や帯域幅の制約があるアプリケーションをサポートすることができます。
結論：Nymは匿名性のトリレンマを解決するか？
匿名通信ネットワークの先行研究では、強い匿名性、低遅延、低オーバーヘッドコストの間には自然なトレードオフが存在することが示されています[7]。 もちろん、匿名性は無償ではありえません。常に何らかのトレードオフが存在します。mixnetのデザインについては、どのようなトレードオフを選択するか、そしてその設計が拡張可能かどうかが問題です。Nymは、最先端のデザインを採用しているため、最もスケーラブルで匿名性の高いmixnetデザインだと考えています。
要約すると、Nymはスケーラビリティ、強い匿名性、低レイテンシーを同時に提供する最初の匿名通信システムです：Nymは匿名性のトリレンマのスイートスポットを突いているのです[7]。Chaumによる最初のmix network デザインの導入以来、40年にわたり研究されてきた数々のベストオブブリードテクニックを組み合わせています。
Elixxirは、匿名性とメタデータの排除に関する強力な証明可能な特性を持つ、最高のChaumian batch mixnetです。Elixxirは、伝説的なChaum自身によって設計されたので、これは驚くことではありません！ しかし、Elixxirは独自の量子耐性を持つ暗号通貨を用いたクローズドソースコードをベースとしており、高速性を得るためにはChaumの新しい飛躍的な事前計算フェーズ（precomputation phase）を必要とし、匿名性の面ではそのスケーリングがbatch mixnet cascade設計の限界にぶつかっています。
つまり、ElixxirベースのシステムであればNymを必要としないが、すでに存在するソフトウェアの世界もあるのだ。ElixxirよりもTorのように、継続的なmixとして、Nymはあらゆるブロックチェーンと相互運用し、高度な統計技術によってあらゆるインターネットトラフィックを匿名化できるよう、汎用的でオープンソースの道を選びました。Nymに流入するトラフィックが多ければ多いほど、Nymのスケールは向上し、匿名性を高めることができます。
Nymは、P2Pトポロジーではなく、階層型（stratified）トポロジーを採用しています。P2Pトポロジーは、パケットを均等に「mix」しないため匿名性に劣りますが、NymはNymネットワークに入るすべてのパケットのプライバシーを保証したいためです。 Nymの上にアプリケーションを構築したり、既存のアプリケーションを統合したい場合は、私たちのTelegramチャンネルに連絡してください。
Nymがインターネットトラフィックのスケーラブルな匿名性に焦点を当てていることを考えると、次の明白な疑問は、NymがTorや新興の "分散型VPN "の世界と比較してどうなのかということです。 この問題については、次回に紹介する予定ですが、その間もTwitterやTelegramで質問を受け付けています。Mixnetは複雑かもしれませんが、NSAのような強力な敵に対して匿名性を確保するための最良のチャンスです。
Sponsor
HStorage は高度なセキュリティ機能を提供している
オンラインストレージサービスです。
参考文献:
[1] “Untraceable electronic mail, return addresses, and digital pseudonyms”, D. L. Chaum; Communications of the ACM; Link
[2] “The Loopix Anonymity System”, A. M. Piotrowska, J. Hayes, T. Elahi, S. Meiser and G. Danezis; USENIX Security Symposium; Link to the paper and presentation video.
[3] “Statistical disclosure or intersection attacks on anonymity systems”, G. Danezis, A. Serjantov; International Workshop on Information Hiding; Link
[4] “From a trickle to a flood: Active attacks on several mix types”, A. Serjantov, R. Dingledine, P. Syverson; International Workshop on Information Hiding; Link
[5] “Impact of network topology on anonymity and overhead in low-latency anonymity networks”, C. Diaz, S. J. Murdoch and C. Troncoso; Privacy Enhancing Technologies Symposium; Link
[6] “cMix: Mixing with Minimal Real-Time AsymmetricCryptographic Operations”, D. Chaum, D. Das, F. Javani, A. Kate, A. Krasnova, J. De Ruiter, A. T. Sherman; Conference on Applied Cryptography and Network Security; Link
[7] “Anonymity trilemma: Strong anonymity, low bandwidth overhead, low latency-choose two.” , D. Das, S. Meiser, E. Mohammadi, and A. Kate; IEEE Symposium on Security and Privacy (SP); Link
原文記事：
この記事が気に入ったらサポートをしてみませんか？