【論文メモ】A survey of DHT security techniques
修論のためにDHTのセキュリティサーベイの論文を読んだのでポイントのメモ。
- A survey of DHT security techniques
- Journal ACM Computing Surveys
- Volume 43 Issue 2, January 2011
- https://dl.acm.org/citation.cfm?id=1883615
- Guido Urdaneta(VU University)
- Guillaume Pierre (VU University)
- Maarten Van Steen (VU University)
- Journal ACM Computing Surveys
Sybil Attack
- 複数のidentityを攻撃者が作成する
- DHTの動作自体を妨げるものではない
- プロトコルを騙ることによって、冗長性による仕組みを覆す
- DHTのセキュリティは$f$ノードが安全であることで保証する
- 攻撃者が物理的なidentityとは別に仮想的に複数identityを作成することで、$f$ノード以上のidentityをOverlay上に配置し、安全性を破壊する
対抗策
- Centralized Certification
- Distributed Registration
- CAを複数配置する
- Sybil Attackを完全に特定はできないが、CCの問題を緩和する
- 分散的なアプローチは、各ノードで全体を把握しないので、攻撃の一部しか見れない
- DHT自体と同様
- Physical Network Characteristics
- ノードの物理特性は騙ることは困難であることを利用
- Sybil Attackは単体のコンピュータまたは似た特性を持つコンピュータで行われる
- ノードを特定し、ネットワークの特徴からそれらを分類する試み
- この手法は、参加者にとって透明性があり、採用する障壁は低い
- しかし、信頼できるNetwork監視基盤が必要である
- CCアプローチと同様の課題を抱える
- また、攻撃者のノードはその位置情報を騙ることなどが可能
- ネットワーク上の位置をノードの特定に用いる場合、本手法は困難になる
- ノードの物理特性は騙ることは困難であることを利用
- Social Networks
- 限られたSybil Attackに有効
- 各ノードは小さな認証局のように動く
- 欠点
- Social Networkに各ノードは登録されてなければならない
- メッセージングなどで実現可能
- ファイル共有アプリなどで用いられる
- オフラインでの対称鍵交換を行わなければならない
- Social Networkに各ノードは登録されてなければならない
- Computational Puzzles
- 善良なノードは他のノードに計算コストをかけることを要求する
- 数学的パズルを解くことを要求
- 物理的な攻撃者のノードはidentityを複数作るために計算擦ろをかけなければならない
- 全てのidentityが即座に検証されていればこの手法は有効
- それはノードが自由に離脱・参加する大規模システムでは現実的には不可能
- そのため、本手法では定期的な全ノードの検証を行う必要がある
- 欠点
- 善良なノードも計算コストをかけ続ける必要がある
- またパズルの難易度も、他の作業ができるキャパシティを残して多くの善良なノードが解くことができる難易度でなければならない
- 実際のP2Pシステムでは各ノードのCPUパワーはばらつきがある
- 善良なノードは他のノードに計算コストをかけることを要求する
- Game Theory
- 全ノードは合理的である推測の元成り立つ
- しかし実際には各ノードは独立しておらず、攻撃者ノード軍は共謀する
- 特定の利益を得るために合理的でない選択をすることがある
- 面白いが、現実的な対抗策になりうるかは要検討
Eclipse Attack
- Routing Tableをhijackすることでネットワークを分断し、DHTの正常動作を阻害する
対抗策
- Routing Tableで使われるノードのIDに制約を加える
- Chordで採用されている
- ノードIDがランダムかつ固定で、攻撃者ノードがID空間上に分散していれば有効
- これを実現するもっとも簡単な方法は認証局を作ること
- またはchurn状態で参加したノードにランダムなIDを割り当てる
- 一方でID割り当てのランダム化は隣接ノードの選択とパフォーマンス効率化を妨げる
- Pastryで用いられている効率化が妨げられる
- routing tableに対する弱い制約
- 結果として多くのノードがIDの制約を満たし、 ネットワークの計測が最適な隣接ノードの選択に使われる
- Pastryで用いられている効率化が妨げられる
- 制約を設けることで、攻撃者ノードはrouting tableにどのように配置されるかを容易に考えられる
- Pastryでは15%の攻撃者ノードによって80%のroutingエントリが汚染される
- Pastry likeなrouting tableを持つDHTに対してEclipse Attackは考慮する必要がある
- 簡単な対抗策は冗長routingを用いること
- 他の手法としては、冗長routingとIDへの制約を組み合わせる
- 最適化されたrouting tableは段階的に汚染される
- そこで制約を持つtableを使う
- 汚染されたtableを用いることと、複雑な障害検知手法によるオバーヘッドが存在する
- 他の対策としては、ノードあたりのincomingとoutgoingリンクの数に制約をつける
- 攻撃者ノードの次数は善良なノードよりも大きいことを利用
- 分散的な手法が存在するが、攻撃が行われていなくても、lookupの時間が増加する
- Eclipse Attackの対抗策にはパフォーマンスと複雑性のトレードオフがある
- 対抗策はDHT本来のオペレーション外の作業を必要とする
Routing and Storage Attacks
- 正規のroutingとは異なるroutingを行ったり、異なるdataを返す攻撃
対抗策
- 基本的に冗長Sotageと冗長Routingで対応する
- レプリケーション手法
- ID空間上で近接するノードにレプリカを配置する
- ID空間上に広がってレプリカを配置する
- ランダムに再配置することで実現
- 1と2を併用する
- ランダムに配置して、その近接ノードにも配置する
- 1の優位点は有効なレプリケーションの度合いを維持し、一貫性を保持するのが容易
- レスポンスが正しいかどうかはあまり意識されていない
- それはアプリケーションレベルで解決できる問題
- valueのhashをkeyにすることで、レスポンスがkeyに対するものか検証可能
- 自分の持つデータのみで検証ができることがポイント
- それはアプリケーションレベルで解決できる問題
- Read-onlyで自分で検証できることがもっとも好まれるケースは、レプリカが正しいかの検証
- それにより、冗長的なroutingを用いず正しいデータが得られる可能性が増える
- レスポンスの検証失敗すれば、複数レプリカとメタデータを取得すれば、アプリレベルで解決できる
- バージョンがもっとも高いものを選択する
- 多数決
- 特定のkeyの担当への到達可能性を担保するには冗長routingを用いる
結論
- DHTへ攻撃としては、主にSybil Attack、Eclipse Attack、Routing and Storage Attacksが挙げられる
- 対抗策として、 ノードIDの安全な割り当て、全体参加者に対して攻撃者ノードの割合を低くする、攻撃者ノードがID空間上で分散するようにする、正しいレプリカへの到達可能性を確保するroutingメカニズムが挙げられる。
- こうした対抗策の提案はそれぞれ異なる前提に基づいている
- アプリにとって最適な対抗策は、その前提を何を持つかによって組み合わせ、考える必要がある
感想
結構昔からこういった分散システムで計算コストを掛けさせることで守るというモデルがあることは、新たな発見だった*1。またそのモデルと、ゲーム理論的モデルでは、攻撃者は攻撃をして利益を挙げるために行動するので、合理的でない攻撃をするということが起こりうる、というのは先述出した論文に近いところがあるので、その辺は精査してみたい。
*1:まぁPoWとか別にBlockchain特有のものではないので当然といえば当然だが
