[DHT]DHTにおけるセキュリティ考察～その１

P2Pの基幹技術としてDHTが随分認知されてきたが、セキュリティの話になると活発な議論がされてない状況である。

ここでは、9月に開催される第2回DHT勉強会で私が講演する内容の概要をBlogにまとめたいと思う。

□DHTのセキュリティ対策

セキュリティ対策には3要素あり、通称CIAと呼ばれている。
Cは機密性、Ｉは完全性、Ａは可用性である。今回はCIA各要素に対してＤＨＴではどのようなセキュリティ対策をすれば良いのか提案あるいは考察をする予定である。

□DHTの大局的な観点における可用性について

全ノードが信頼できるノードである状況はまれで、通常は悪意のあるノードが存在する可能性がある。この際に悪意のあるノードが何％紛れた場合にネットワークが分断されるかが気になるところである。

ここではパーコレーションという物性物理理論のテクニックを使って上記問題を考察してみよう。

□パーコレーションとは？

パーコレーションという語彙を説明するにはまずは下記のサイトを見たほうが早いだろう。
http://www.mi.ics.saitama-u.ac.jp/~yas/research/network/percolation/

パーコレーションは「系全体におけるつながり」を議論する。どのような状況のときに系全体がつながるか、その条件を決めることがパーコレーションにとって重要なことである。このように書いてみると、パーコレーションにおける「つながり」≒ＤＨＴでシステムを維持することであることが分かるだろう。

今、DHTとして2次元CANを考えてみる。CANにおいて、悪意のあるノードがあって、悪意のノードは他ノードからのリクエストを破棄してしまうとしよう。このとき、悪意のノードがどの程度含まれていれば、システムはダウンするだろうか？

パーコレーションはこれに対して明確な答えを出す。答えは50%以上の悪意のノードがあればダウンするということである。（この問題はサイトパーコレーションと呼ばれる）

では、今度は別の見方からパーコレーションを活用してみる。
今、各ノードはリンクがＮ個出ているとする。では各ノードのリンク総数が何％ダウンした場合、システムはダウンするだろうか？

2次元CANであれば、既に答えは判明している。それは、約4割のリンクがダウンすればシステムがダウンしてしまうことである。（この問題はボンドパーコレーションと呼ばれる）

2次元CANで解析した結果から分かるように、DHTでシステム全体をダウンさせるには相当数の悪意のあるノードが必要であることがご理解頂けるだろう。
実は、この結果はWinnyのような多リンクでノードが繋がるシステムをダウンさせることが極めて難しいことを意味している。

□Chordとパーコレーション

では、PastryやChordといわれる、より多リンクのノードの場合、どのぐらいでシステムをダウンできるだろうか？直感的にサイトパーコレーションでも少なくとも50%以上の悪意のノードが必要であることがわかるだろう。

事実、サイトパーコレーションでもボンドパーコレーションでも、多次元になればなるほど悪意のノードが相当多くないとシステムがダウンしないことがわかっている。詳細は下記を見て欲しい。
http://www.geocities.jp/ikuro_kotaro/koramu/kousi2.htm

つまり、悪意のノードがいてもシステムの可用性を極力下げない方法として各ノードにおけるリンク数を増やせばよいことが挙げられる。実際的には50％以上も悪意のあるノードが存在する可能性は少ないので、通常のＤＨＴを使い、さらにそれなりにノード数が存在する場合についてはシステム全体がダウンすることはほとんどないだろう。システムダウンがあるとすれば、DHT経由で各ノードがワームに感染する場合ことが考えられる。

今後は悪意のあるノードが存在した場合の局所的な影響を考察してみたい。