論文紹介 - "Riffle: An Efficient Communication System With Strong Anonymity"

初めに

この記事は情報セキュリティ系論文紹介 Advent Calendar 2016の24日目の記事です。 半年くらい前に話題になっていたRiffleというプロトコルの論文の紹介です。 周りが強い人たちばかりで怖いですが、よろしくお願いします。

TL;DR

匿名化ネットワークを、ダウンロードにPrivate Information Retrievalを、アップロードにmixnetsとVerifiable Shuffleを用いて構築する。また、このシステムは、既存の主流な匿名化ネットワークに欠けているトラフィック解析への耐性と、それ以上の匿名性を併せ持つ。

背景

匿名化ネットワークは現在いくつかあるが、主流になっているネットワークのトラフィック解析に対する耐性は疑わしい。そこで、提案こそ以前からあるものの技術的課題の多かった、mixnetsや他の様々な技術を改善し、かつ組み合わせることで、新たな匿名化ネットワーク「Riffle」を設計した。

前提知識

mixnets とは

古くからある匿名化ネットワークのプロトコルの1つ。クライアントから渡されたデータを、複数のサーバーに中継させ、また、中継時に内容をランダムに並び替えることで、トラフィック解析に対抗する。また、onion-encryptも併用する。いくつかの攻撃手法と、それを改善した派生プロトコルが存在する。

Verifiable Shuffle とは

Verifiable Shuffleとは、データの内容が同一であることを検証可能にしつつ、データをランダムに並び替えるプロトコルである。mixnetなどで悪意のあるサーバーへの対策として使用されるものの、計算量が大幅に増えるという欠点がある。 Riffleでは、TLSのように公開鍵暗号を共通鍵の交換のみに用いることで、計算量を改善したHybrid Verifiable Shuffleと筆者が呼ぶものが使われる。

Private Information Retrieval とは

Private Information Retrieval(以後PIR)とは、クライアントがデータベースを持つサーバーから、どのデータを取得したかサーバーに知られることなく、特定のデータを取得できるプロトコルの総称である。原理的には、ダウンロードの度にデータベースの全てのデータを取得するプロトコルPIRと言える。Riffleでは、XORを用いて実装される。

Riffle

モデル

Riffleは、1つのサーバー群と複数のクライアントが存在し、少なくとも1つのサーバーが信頼できることを前提とする。

f:id:ak1t0:20161224184608p:plain (図は論文からの引用)

プロトコル

Riffleでは、プロトコルの開始から終了までをepoch、その中で鍵の共有などの準備をするsetupと、実際にコミュニケーションを行うcommunicationに分けられる。また、communicationの中で行われる各アップロード/ダウンロードをroundと呼ぶ。

Setup

1. 鍵のシャッフル

  • 通信に関わる全てのサーバーが公開鍵/秘密鍵のペアとシャッフル用パラメータを生成する
  • クライアントが全てのサーバーの公開鍵を取得する
  • クライアントが各サーバー用に共通鍵の配列を生成する
  • 鍵の配列をサーバーから取得した全ての公開鍵でonion-encryptする
  • onion-encryptした共通鍵鍵の配列をアップロード
  • Verifiable Shuffle が行われ各サーバーがクライアントが生成した共通鍵を1つずつ取得

2. PIRの準備

  • クライアントと全てのサーバーがPIRのためのSecretを共有

Communication

1. アップロード

  • クライアントがSetupで共有した共通鍵でメッセージをonion-encryptする
  • 暗号化したメッセージをサーバー群へアップロード

2. シャッフル

  • サーバーは受け取ったメッセージの認証と復号を行う
  • 復号したデータをSetupで生成したパラメータでシャッフル
  • 次のサーバーへシャッフルしたデータを渡す
  • 最後のサーバーは完全に復号されたメッセージを全てのサーバーへ送信

3. ダウンロード

  • Setupで共有したSecretを利用してPIRでサーバーからダウンロード

Accusation

RiffleへのDoS攻撃は、悪意のあるクライアントによる意図的な壊れたデータのアップロードが考えられ、これを防ぐ告発(accusation)というシステムが存在する。 Accusationというのは、悪意のあるクライアントを特定するためのプロトコルで、これによりオーバーヘッド無しに悪意のあるクライアントの特定と排除を実現する。ただし、そのままでは悪意のあるサーバーが乱用できてしまうので、告発には全てのサーバーの同意を必要とすることで、これを防ぐ。

ソースコード

GitHub - kwonalbert/riffle

参考文献

Riffle - people.csail.mit.edu
How to stay anonymous online - MIT News
Here's How Riffle Anonymity Network Protects Your Privacy better than Tor - The Hacker News
MITの匿名ネットワーク通信プロトコルRiffleはTorの長年の王座を揺るがすか