スライド 1

P2Pにおける認証と文字列検索について
2006年12月3日
Tomo’s Hotline
西谷 智広
P2P・DHT勉強会 in 関西資料 西谷 智広
1
目次
自己紹介
ノードIDの検証・認証
文字列検索
質疑応答
P2P・DHT勉強会 in 関西資料 西谷 智広
2
1.ノードIDの検証・認証
ノードID:DHT、Skipgraph等でノードを区別
する識別子としての意味も持つ
ノードIDとノードを1対1で結びつける(本プレ
ゼン)⇒ノードIDの妥当性を検証できる
ノードIDをうまく使って認証に利用できない
か?(最終目標)
スコープ:ノードIDの定義と認証方法の比較
P2P・DHT勉強会 in 関西資料 西谷 智広
3
1-1.ノードIDの検証・認証[案1]
 [案1]ノードのIPアドレス+ポート番号ハッシュ値を
ノードID
メリット
検証、認証が楽(IPアドレス、ポート番号は直接通信する
時に必要)
開発費用小
デメリット
ノードID衝突の可能性(プライベートアドレス同士)
ノードがグローバルアドレスを取得する機構等が必要(U
PnP等)
他のノードが認証されるケースも。(アドレスポート認証)
P2P・DHT勉強会 in 関西資料 西谷 智広
4
1-1.ノードIDの検証・認証[案1]
NAT越え
案A UPnP利用
案B STUNサーバ利用
STUNサーバ
インターネッ
ト
ルータ
インターネッ
ト
UPnP機構
(IDG)
ノード
ルータ
ノード
P2P・DHT勉強会 in 関西資料 西谷 智広
5
1-1.ノードIDの検証・認証[案1]
 STUNサーバを利用してもNAT越えできない場合あり。(Sy
mmetric NATの場合等)
 上記の場合はB2BUA的な通信が必要。[案C]このときには
案1の利用は困難。
案C 他ノードを介する
ノード
ルータ
インターネッ
ト
ノード P2P・DHT勉強会 in 関西資料
西谷 智広
ルータ
ノード
6
1-2.ノードIDの検証・認証[案2]
 [案2]電子証明書内容のハッシュ値をノードID(PKI)
メリット
 ノードのネットワーク形態によらずノードIDの改ざんを検証でき
る。
 電子証明書を使うことにより、ノード間の認証、暗号化が(原
則サーバレスで)容易に可能。
デメリット
 ノードに電子証明書の配布する必要あり。証明書更改も順次
行う必要あり。
 上記に伴いCA等が必要。
 開発費用が高い。
P2P・DHT勉強会 in 関西資料 西谷 智広
7
1-2.ノードIDの検証・認証[案2]
 証明書の内容例
氏名
証明書発行シリアル番号
発行日
有効期間
発行機関
 オプションを利用すれば、上記以外のデータも証明
書に格納化。
 証明書内容のハッシュ値をノードIDとする。
 証明書有効を検証するためのハッシュ値(デジタル
署名用ハッシュ値)をそのままノードIDとして利用す
るアイデアもある。
P2P・DHT勉強会 in 関西資料 西谷 智広
8
1-2.ノードIDの検証・認証[案2]
案2に対する注意点
電子証明書のリポジトリ
案P:特定サーバを利用
• 通信集中、運用費高
案Q:DHTノードに分散(通信分散、運用費ほぼ0)
• 通信分散、運用費用低
• 証明書の紛失対策が必要→後述
• Node_ID=hash(X+Y)に格納。Xは証明書のデータ、Yはある
数値。
• Y=0にすると証明書対象ノードが証明書保有ノードになり、
Y≠0の方がセキュアと考えられる。(詳細検討が必要)
P2P・DHT勉強会 in 関西資料 西谷 智広
9
1-3.ノードIDの検証・認証(案3)




電子証明書内容のハッシュ値をノードID(PGP)
原則はPKIを利用した案2と同じ
メリット:サーバレス=コスト低
デメリット
 ノード数増加に伴いノード検証処理の増加
 ノードIDが一意にならない可能性あり
 信頼の輪が複数存在してしまう可能性も?
P2P・DHT勉強会 in 関西資料 西谷 智広
10
1-4.ノードIDの検証・認証(案4)
ノードが生成した素数の積のハッシュ値が
ノードID
アイデア:サーバレスで認証ができなか?
⇒パスワードを相手に渡さず認証できないか?
⇒ゼロ知識証明が使えそうだ!
P2P・DHT勉強会 in 関西資料 西谷 智広
11
1-4:ノードIDの検証・認証(案4)
・ノードA
大きな素数R、Sを準備、N=R・S
ノードID=Hash(N)⇒ノードIDとNを公開
ノードA
ゼロ知識証明
ノードB
ゼロ知識証明でノードAがNを素因数分解できることを提示できれば、
ノードBはノードAを認証したこととする。
P2P・DHT勉強会 in 関西資料 西谷 智広
12
1-4:ノードIDの検証・認証(案4)
問題点
中間侵入攻撃を許す
(ノードAに対して)
俺はノードBだよ。
ノードA
(ノードBに対して)
俺はノードAだよ。
ノードC
ノードB
ゼロ知識証明
ノードIDの衝突の可能性も。(レアケース?)
P2P・DHT勉強会 in 関西資料 西谷 智広
13
1-5:ノードIDの検証・認証(案5)
 ノードが生成した素数の積のハッシュ値がノードID
アイデア:
中間進入攻撃を防ぎたい⇒自己証明書の原理を利用
ノードA:大きな素数R、Sを準備、N=R・S
R、S、Nを利用してRSA暗号アルゴリズムより
公開鍵P_Key,秘密鍵S_Keyを作成。
ノードAが公開する情報
(ノードID=Hash(N)、N、P_Key)
P2P・DHT勉強会 in 関西資料 西谷 智広
14
1-5:ノードIDの検証・認証(案5)
認証
チャンレジレスポンス
(ノードAの認証)
ノードA
(Hash(N),N,Key_P)
RSA暗号化通信
チャンレジレスポンス
(ノードBの認証)
ノードB
(Hash(N’),N’,Key_P’)
□双方認証が可能。通信も暗号できる
P2P・DHT勉強会 in 関西資料 西谷 智広
15
1-5:ノードIDの検証・認証(案5)
デメリット
ノードIDの衝突が起きる可能性がある。
(どの程度の可能性?現実的にはレアケー
ス?)
P2P・DHT勉強会 in 関西資料 西谷 智広
16
2:文字列検索
最終目標:
・P2Pで部分一致文字列検索をする
・AND、OR検索ができること
P2P・DHT勉強会 in 関西資料 西谷 智広
17
2-1:文字列検索への道
DHT、SkipGraph
⇒ノードID、Keyにハッシュ値を利用。
文字列検索における問題点:
文字列が少し変わっただけでもハッシュ値が
全然違う値に。
P2P・DHT勉強会 in 関西資料 西谷 智広
18
2-1:文字列検索への道
そもそも論:
加法性があるハッシュ関数を作れば解決?
Hash(X+Y)=Hash(X)+Hash(Y)
(この方法は本プレゼンでは触れない。)
本プレゼンは加法性を利用することで
文字列検索を可能としている。
P2P・DHT勉強会 in 関西資料 西谷 智広
19
2-2:情報登録アルゴリズム
1:形態素解析
東京特許許可局⇒東京:特許:許可:局
東京
特許
許可
局
ハッシュ値
0001
0010
0100
1001
P2P・DHT勉強会 in 関西資料 西谷 智広
20
2-2:情報登録アルゴリズム
2:ハッシュ値のOR計算
東京
特許
許可
局
ハッシュ値
0001
0010
0100
0101
OR⇒ 0111
(これを抽出用ハッシュ値と呼ぶことにする)
P2P・DHT勉強会 in 関西資料 西谷 智広
21
2-2:情報登録アルゴリズム
3:ノードへの情報登録
形態素分解した単語のハッシュ値と抽出用ハッシュ値の直和と
なるノードIDのノードに情報(東京特許許可局)を登録
ハッシュ値
登録ノードID
東京
0001
00010111
特許
0010
00100111
許可
0100
01000111
局
0101
10010111
⇒
0111(抽出用ハッシュ値)
P2P・DHT勉強会 in 関西資料 西谷 智広
22
2-3:検索アルゴリズム
「東京」の検索
「東京」のハッシュ値=0001
東京に関する情報が登録されているノード
00010000≦ノードID≦00011111
ちなみに「東京特許許可局」⇒00010111
P2P・DHT勉強会 in 関西資料 西谷 智広
23
2-3:検索アルゴリズム
 「東京」AND「特許」の検索
「東京」のハッシュ値=0001
「特許」のハッシュ値=0010
東京と特許のOR=0011
「東京」AND「特許」に関する情報が登録されている
ノード
00010011≦ノードID≦00011111
または
00100011≦ノードID≦00101111
P2P・DHT勉強会 in 関西資料 西谷 智広
24
2-4:文字列検索DHT vs SkipGraph
ある範囲のKeyに検索クエリーを出す必要が
ある。
⇒DHTは苦手
⇒SkipGraphは得意!
文字列検索(本アルゴリズム)は
SkipGraphで実装する方が望ましいと
考えられる。
P2P・DHT勉強会 in 関西資料 西谷 智広
25
最後に
 P2Pのセキュリティ研究はとても魅力的な分野
 文字列部分検索からあいまい検索、全文検索へ
ご清聴ありがとうございました!
P2P・DHT勉強会 in 関西資料 西谷 智広
26