« [P2P]SkipGraphを利用した部分一致検索の提案 | トップページ | P2P・DHTオフ会 in 関西(12/3[日]開催) »

2006.11.03

[P2P][DHT]ゼロ知識証明によるP2P認証方法の提案

□はじめに
セキュリティの興味深いトピックとしてゼロ知識証明というテクニックがある。
ゼロ知識証明
http://www.venture.nict.go.jp/series/cryptography/chapter2/2_4.html

ゼロ知識証明は簡単に言うとつぎのようなものである。
[1]ユーザAは大きな素数A,BよりC=A×Bを作成する。
[2]ユーザBはユーザAとある通信をすることで、ユーザAがCの素因数分解ができるか否かを検証することができる。(それもユーザAがユーザBにA,Bの情報を提示せず!)

筆者はゼロ知識証明について昔から興味を頂き、この技術の応用を模索していた。今回はゼロ知識証明を使う事でP2P(具体的にはDHT)認証方法として応用する事を提案する。

以下については11/4に大幅修正を加えています。


□認証プトロコル
プロトコルは次のとおり

☆ノードID作成プロトコル
[1]各ユーザは大きな素数A,BよりC=A×Bを作成する。ただし、Cはハッシュ空間Hの最大値よりも小さい事が必要である。今、ユーザAがCを作成したとする。
[2]IPアドレスとポート番号の組み合わせをDとしてこのハッシュ値Z=Hash(D)をノード固有情報とする。
[3]ユーザAはDHTに参加する際に、ノードID=Hash(C^m×Z mod T)とする。ここでHash()とはハッシュ関数である。今、C^mとはCのm乗を意味する。mはべき乗数と呼ぶ事にしよう。mは各ノードが乱数で決定し、十分大きい数とする。またID、Z、mをDHTノードに公開する。Tは各ノード共通である。

なおノードIDにZという要素が必要な理由は、大きく分けて2つである。
理由1:たまたまノードID=CでユーザAとユーザBが一致した場合、ユーザBはユーザAの成りすましが可能である。(ユーザAもユーザBもCを素因数分解できるため。ちなみにある数Rは一意に素因数分解できることが知られている)
理由2:ノードID=Cとすると、ノードIDは相当大きな数になってしまい、ハッシュ空間にノードIDを均一に存在させる事が難しくなる。
*こちらの理由は正しくありませんでした。削除します。(11/4)
☆認証プロトコル
今、ユーザBがユーザAを認証しようとする。ユーザAはノードID=P、固有情報=Q,べき乗数=RをDHT参加ノードに公開している。

[1]ユーザBはユーザAを認証したい。ユーザBはDHTよりユーザAの公開情報(P,Q,R)を入手する。このとき、ユーザBはユーザAと直接通信することで、ユーザのIPアドレス及びポート番号の情報Eを手に入れ、Q=Hash(E)を検証する。Q≠Hash(E)ならMan-in-the-middle atatckをされる可能性がある。
[2]ユーザAは(ユーザBの求めに応じて)ユーザBにCを通知する。ここでユーザBはHash(C^R×Q mod T)を計算しPと合致するか計算する。
[3]ユーザBはゼロ知識証明よりユーザAが確かにCを素因数分解できることを証明する。
[4]結果としてユーザBはユーザAが(P,Q,R..C)の組を保有し且つCの素因数分解ができる正当性を検証できる。

□終わりに

今回提案したプロトコルを使えば、認証の際にPKIやPGPを使う必要がない。非常にシンプルなプロトコルなので、実装も容易である。簡易なP2Pの認証方法として期待できそうだ。

なお、この提案に対するBlogコメントがあります。コメントに対するレスは後ほど書いてみます。(11/4追記)
http://d.hatena.ne.jp/smoking186/20061104

|

« [P2P]SkipGraphを利用した部分一致検索の提案 | トップページ | P2P・DHTオフ会 in 関西(12/3[日]開催) »

P2P」カテゴリの記事

コメント

ゼロ知識認証については、中間浸入攻撃でなりすましは可能です。

ただし中間浸入攻撃がない場合には、原則認証されるノード、認証するノードはチャレンジレスポンスのような振る舞いをするので盗聴してもリプレイ攻撃は困難です。
http://c4t.jp/introduction/cryptography/cryptography06.html

投稿: Tomo | 2006.11.11 10:52

>[3]ユーザBはゼロ知識証明よりユーザAが確かにCを素因数分解できることを証明する。

ここで言うCは,Aがネットワーク参加時に一度生成したものを何度も使うわけですよね?

それだと、AとBとのやり取りを盗み見られたら、次回B以外の悪意のあるノードが、同じように振舞うことで偽装ができてしまいませんか?

http://www.venture.nict.go.jp/series/cryptography/chapter2
のやり方のように,AとB以外に、信頼できるノードが仲介を行わないとゼロ知識証明にならないのではないでしょうか。

投稿: Ryo | 2006.11.06 10:24

コメントありがとうございます。
ゼロ知識証明なので、成りすましは難しいです。盗聴してもなにも情報は得られません。

投稿: Tomo | 2006.11.03 22:42

僕の理解が間違っているかもしれませんが

ノードID=Pが一度のネットワークの参加の間(脱退をはさまない間)は固定的に各ノードが保持しているのだとしたら、認証を行っている通信を傍受された場合に成りすましが可能になってしまいませんか?


ああ、そういう意味で簡易な認証ということですか。

投稿: Ryo | 2006.11.03 16:10

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/12534977

この記事へのトラックバック一覧です: [P2P][DHT]ゼロ知識証明によるP2P認証方法の提案:

« [P2P]SkipGraphを利用した部分一致検索の提案 | トップページ | P2P・DHTオフ会 in 関西(12/3[日]開催) »