$ \def\vector#1{\boldsymbol{#1}} $

Mix Network

2020年10月20日 #MixNetwork #OnionRouting #Tor

概要

Mix Network は受信者のみが解読できる暗号でメッセージを秘匿し、さらにランダムに選んだ多段のノードで中継させることでメッセージの発信者や伝達経路と通信内容の両方を秘匿することを目的としたネットワーク。メッセージを中継するノードを一般にルーター (router) と呼ぶ。

概要
1. 多重暗号
オニオンルーティング
1. 論理回路の構築
2. メッセージの送受信
参考文献

多重暗号

Mix Network の秘匿通信は中継するルーターごとに階層的に暗号化された多重暗号 (multiple encryption; カスケード暗号) を用いて行う: ノード A が Mix Network を通じてノード B へ秘匿メッセージを送信するとき、まずメッセージの転送経路となる順序付けられた $n$ 個のルーター $R_1,$ $R_2,$ $\ldots,$ $R_n$ を選択する。次に送信者 A はそれぞれのルーター $R_i$ の鍵 $S_i$ を使用してメッセージ $m$ から以下のような多重暗号文を作成する: \[ {\rm enc}(S_1, {\rm enc}(S_2, \ldots {\rm enc}(S_n, m) \ldots )) \] この暗号化メッセージを受け取った最初のルーター $R_1$ は、自身の鍵 $S_1$ を使って最外層の暗号を除去し $R_2$ に転送する。$R_2$ は同様に自身の鍵 $S_2$ で最外層の暗号を除去し $R_3$ へ転送する。この作業を繰り返すことによって最終的に $R_n$ のみがメッセージの平文と受信者 B を知ることができるが、中継したルーター、$R_n$ 及びノード B はメッセージの送信者を知ることができない。

メッセージの内容を最後のルーター $R_n$ から秘匿するためにはノード A と B との間で end-to-end 暗号を行う必要がある。

このような Mix Network を用いても、ネットワーク全体の監視者が存在するケースでは、メッセージの送受信とその直後の逆方向への送受信を追跡してパターンを分析することで双方のノードがリクエスト/レスポンス型のプロトコルに関与していると推測することができる。このため、メッセージを乱数でパディングしたり、意図的な応答/転送遅延を追加したり、または covering traffic と呼ばれる偽のメッセージを発生させるといった方法で追跡を困難にしている。

オニオンルーティング

オニオンルーティング (Onion routing) は Mix Network に基づいた経路秘匿のメッセージ送信を行うシステムである。Tor (The Onion Routing) の接頭辞で知られているオニオンルーティングネットワークは発信元の追跡を困難にするためにオニオンルーター (onion router; OR) を多層に介してルーティングするように設計されたボランティアネットワークである。

メッセージはネットワークに送信される前に暗号化されるため中継するルーターがその内容を盗聴することはできない。ネットワーク全体が監視されている場合であっても、トラフィック分析によって真の送信元と受信先を特定するには通信経路上の全てのルーターの受信と送信を詳細に追跡する必要があり現実的には非常に困難であると言われている。

一般的に Tor は人権や政治の内部告発者がジャーナリストとのコミュニケーションのために使用されているが、しばしば違法行為のためにもされていることから多くの国では政府の監視対象となっている。

論理回路の構築

前述のような多重暗号を用いた Mix Network システムではメッセージの受信側が応答を返すことができない問題が残っていた。Tor では最初に経路を確立するため TCP のような双方向の end-to-end 通信を行うことができる。この論理回路上のルーターは自分の前後のノードしか知ることができない。

送信者 A はディレクトリノードからルーターのリスト $\vector{R}$ を取得する (リストにはルーターのアドレスと公開鍵が含まれている)。
送信者 A はリストからランダムにルータを選びチェーンと呼ばれる転送経路 $(R_1,$ $R_1,$ $\ldots,$ $R_n)$ $\in \vector{R}$ を決定する。
送信者 A は以下の手順で $R_n$ までの論理回路を構築する。ここで A とルーター $R_i$ とのやり取りは暗黙的に $i$-重暗号化されていることに注意。
1. 送信者 A はまず $R_1$ と接続し $R_1$ の公開鍵で $R_1$ とのセッション鍵 $S_{a,1}$ を作成する。これより後は A と $R_1$ とのやり取りはこのセッション鍵 $S_{a,1}$ を使用して暗号化される。
2. 送信者 A はルーター $R_1$ に対して $i=2$ 番目のルーターである $R_2$ へ経路を延長するように要求する。$R_1$ は $R_2$ と接続し、その公開鍵でセッション鍵 $S_{1,2}$ を作成する。これより後は $R_1$ と $R_2$ とのやり取りはこのセッション鍵 $S_{1,2}$ を使用して暗号化される。またこの要求/応答のやりとりで A と $R_2$ 間にもセッション鍵 $S_{a,2}$ が作成される。
3. 送信者 A はこの経路の延長を繰り返して最終的に $R_n$ への経路と $n$ 個のセッション鍵 $\{S_{a,1},$ $S_{a,2},$ $\ldots,$ $S_{a,n}\}$ を作成する。

セッション鍵 $S_{x,y}$ とは、ノード $x$ と $y$ の公開鍵を使用して鍵共有アルゴリズム (half Diffie-Hellman) によって $x$ と $y$ の双方で安全に生成される共通鍵暗号のための鍵である。

この操作が完了すると送信者 A には各ルーターとのセッション鍵 $S_{a,1},$ $S_{a,2},$ $\ldots,$ $S_{a,n}$ が構築され、またそれぞれのルーターにも前後のノードとのセッション鍵 $S_{a,1},$ $S_{1,2},$ $\ldots,$ $S_{n-1,n}$ が構築される。Fig 2 はこの論理回路の構築を表している。

ここで経路上のルーター $R_i$ が知っているのは自身の前後のルーター ($i=1$ の場合は A) だけであり、経路の両端が誰であるかを知るすべがない点に注意。

メッセージの送受信

送信者 A から $R_n$ 宛にメッセージ $m$ を送信するケースについて考える。まず A はメッセージ $m$ をチェーンの最後のルーター $R_n$ (exit node) のセッション鍵 $S_{a,n}$ で暗号化する。次にその暗号文をチェーンの最後から 2 番目のルーター $R_{n-1}$ のセッション鍵 $S_{a,n-1}$ とで暗号化する。… この暗号化をチェーンの先頭のルーター $R_1$ (entry node) まで繰り返す。\[ m_i = \left\{ \begin{array}{ll} {\rm enc}(S_n, m) & \mbox{if $i=n$}\\ {\rm enc}(S_i, m_{i+1}) & \mbox{otherwise} \end{array} \right. \] この多層暗号化されたメッセージはルーターを経由するたびにそのルーター $R_i$ のセッション鍵 $S_{a,i}$ で復号化されながら転送され、最終的に $R_n$ のみが元のメッセージ $m$ を入手することができる。実際のメッセージにはさらに改ざん防止のためのハッシュ値の添付やデータサイズからホップ数を推測されないようにパディングなどが行われる。

一般に exit node の $R_n$ は非オニオンネットワークのノード B にメッセージを伝達するプロキシサーバの役割となる。このとき、メッセージ $m$ の内容は $R_n$ から閲覧可能であるため、B 以外にメッセージ内容を明かしたくない場合は A と B との間での end-to-end 暗号を講じなければならない。

description figure of message transmission between node A and B relayed by onion routing — Fig 3. Onion Routing によって中継されるノード A と B のメッセージ交換。

Fig 3 は送信者 A から受信者 B へのメッセージ転送と、B から A への応答を表している。ルーター $R_n$ から A の方向にメッセージを送信するケースでは、各ルーター $R_i$ は自身のセッション鍵 $S_{a,i}$ を用いてメッセージを暗号化して行く。最終的に A が多層暗号化されたメッセージを受信したとき、A は全てのルーターのセッション鍵を用いてその暗号を除去することができる。