[Web]Blogに対するはてブの新着ブックマークを簡単に確認する方法

自分のBlogに「はてブ」のブックマークがされているか気になる人も多いでしょう。
ここではBlogに対する最新ブックマーク状況が簡単にチェックされる方法を書いてみます。
方法は次の通り。

[1]はてブの注目エントリーのページに行く。
http://b.hatena.ne.jp/entrylist?sort=hot

[2]URLで絞りこみの欄に自分のBlogのURLを書く。

[3]すると自分のBlogに対するはてブの注目エントリーが表示されます。
そこで、「このサイトの新着ブックマーク」をクリックしましょう。
最新のブックマークが新着順に表示されます。
ちなみに私のblogの場合は下記のURLになります。
http://b.hatena.ne.jp/bookmarklist?url=http://toremoro.tea-nifty.com/

[4]上記の新着ブックマークを表示するページはRSSで簡単に更新をチェックすることができます。（「RSS」と書いてあるところをクリックしてみてください。）RSSリーダーを使うと、簡単に自分のBlogに対するはてブのブックマーク状況がわかりますよ！

[DHT]DHT勉強会ミニプレゼン講演者募集について

先日お知らせしたように９月に東京にて第2回DHT勉強会を開きます。
http://toremoro.tea-nifty.com/tomos_hotline/2006/04/p2pdht2dht_b1ab.html
それに合せて、ミニプレゼン講演者を募集します。

□ミニプレゼン概要

・内容：DHT関連であれば問いません
・プレゼン時間：プレゼン15分、質問5分（目安、内容・ボリュームにより時間調整可）
・募集人数：4人程度
・特典：DHT勉強会参加費無料、懇親会費減額あるいは無料

なお、DHTプレゼンはどなたでも参加可能です。大学生～社会人まで皆様参加して下さい！
学会や卒論・修論で書いた内容を簡単にまとめてもOKです。またジャストインアイデアなものや、提案等でもかまいません。

DHT勉強会を通して是非情報発信をしてみませんか？

なお、参加に興味のある方はtnishita@yahoo.co.jpまでご連絡をお願い致します。

[DHT]DHTとホップ数の関係[その１]～直感的な方法

DHTの論文を見るとホップ数についての記述があるが、その計算根拠について書いてない場合が多い。
ここでは簡単な方法を使ってホップ数のオーダーを考えてみよう。
なお、次回以降には微分方程式・数列等を使うことにより、より詳細な考察を行う予定である。

今回はCANとChordについて書いてみることにする。

□CAN
CANについての概要は以下のサイトをご覧になってほしい。
P2Pと分散ハッシュテーブル～その１

今、２次元空間のCANを考える。縦、横ともnの大きさがあるとすると、ノード数はN=n^2である。ただし、^2は二乗を表すこととする。

ホップ数については、（0,0)というノードから（論理的に）一番遠いノードに対するホップ数とほぼ同じオーダーであろう。一番遠いノードは（n,n)である。
注※正確には(n-1,n-1)。ホップ数のオーダーにはあまり関係ないこと、見た目が複雑なので(n,n)で書いていく。

(0,0)から(n,n)までは2nホップかかる。ここでCANではリンクが縦または横にしかないことに注意！斜めにホップすることはできない。

結局ホップ数は　2n=2√（N)となる。つまりO(N^｛1/2})である。

ちなみに同様な方法で計算すると、d次元の空間においてホップ数はO(N^{1/d})である。

□Chord
Chordの概要は以下のサイトをご覧になって欲しい。
P2Pと分散ハッシュテーブル～その2

今ノード数をNとして、n=log₂Nとする。
ノードAからはリンクをnだけ出していることに注意。

Chordは2^p離れたノードに対してリンクをする。（pは０以上の整数）
つまり、１回リンクを辿ると、次にホップできる空間を1/2に絞ることができる。
するとホップ数qは、リンクを辿ることでホップできる空間があるノードに限定してしまう状態、つまり次にホップできる空間が１に辿りつくホップ数が分かれば良い。

結局N*(1/2)^q = 1であり、これを解いてq= n = log₂ Nとなる。つまりq= O(log ₂N)

次回は数列や微分方程式を使ってよりエレガントにホップ数を計算できる方法を提案したいと考えている。　

[Winny]Winnyの解析とそのセキュリティ脅威分析セミナー概要

5/12(金）品川プリンスホテルで開催されたInside Winny～Winnyの解析とそのセキュリティ脅威分析セミナーに参加しましたので、その概要をお伝えします。修正点等ございましたらご連絡をお願い致します。

□講演者：鵜飼　裕司氏　eEye社　senior software engineer
（なお、資料には金居　良治氏　eEey社　software engineerの名もある。）

関連：検出ツールの開発者が語る，「Winnyを検出する方法」

※本講演は下記記事の拡張版のようなものです。
http://itpro.nikkeibp.co.jp/article/Watcher/20060411/235051/
□感想
eEye社は脆弱性判定ツールを開発する会社であり、Windows等の数々の脆弱性を発見した会社である。
Winnyのリサーチはわずか１ヶ月とのことだが、このような短期間の間に詳細内容を把握する技術力に驚いた。
なお、現在はWinnyネットワーク可視化、Shareの検出に力を入れており、今後研究の結果についても期待している。
また、Winnyを介したワームについての意見についてはとても興味深い。これについては私の意見を後述する。

□概要
-プロトコル
・ファイル転送用通信：ポート値はランダムな値を取る。26のコマンドで制御し、RC4で暗号化。
・BBS用通信：HTTPでポート値はランダムな値をとる。HTTP通信。

-パケット分析
・初期鍵パケット：最初の2バイトはダミー、次の4バイトが暗号キー(p_keyとしよう）を示す。
・通信ブロック：最初の4バイトはブロック長、次の1バイトがコマンド番号、残りはコマンド引数
・第2パケット以降の暗号方法：p_keyを加工した新しい鍵p_newkeyによりRC4暗号通信を行う。

-コマンド：
26のコマンドは次の通り
0x00:Winnyプロトコルヘッダー
0x01:回線速度通知
0x02:コネクション種別通知
0x03:自ノード情報通知
0x04:他ノード情報通知
0x05:BBSポート番号通知
0x0A:拡散クエリ送信要求
0x0B:キャッシュファイル送信要求
0x0C:拡散クエリ要求
0x0D:クエリ送信
0x0F:BBS拡散クエリ転送要求（検索条件付)
0x10:BBS拡散クエリ転送要求
0x11:BBSキー転送要求
0x15:キャッシュブロック送信
0x16:Port0ノードに対して転送リンク要請
0x17:Port0ノード情報通知
0x18:BBS投稿
0x19:BBS投稿中継依頼
0x1A:BBS書き込み中継結果通知
0x1B:BBS書き込み結果の通知
0x1F:切断要求
0x20:切断要求（転送限界）
0x21:切断要求（BadPort0警告）
0x22:切断要求（無視ノード警告）
0x23:切断要求（低速ノード警告）
0x24:切断要求（捏造警告）

-各コマンドの詳細：
講演では部分的に紹介されていた。主なものを抜粋。

0x03:自ノード情報の通知
・自ノードIPアドレス、ファイル転送ポート、DDNS名文字列長、クラスタリング文字列

0x04:他ノード情報の通知
・他ノードIPアドレス（IPv4アドレスがそのまま載っている）、ファイル転送ポート、BBSポート、回線速度、クラスタリング文字列等
・接続すると他ノードから0x04通信がバラバラ取得できる。これを元にWinnyのネットワークノード情報の列挙が可能。Winnyネットワークの可視化にも利用可能。

0x0D:クエリ送信
・クエリ経由ノード（IPv4アドレス）、経由ノード情報リスト個数、クエリID、検索キーワード、検索キーワード文字列長、キー情報リスト個数、キー情報等

-キー情報
・IPアドレス、ポート、ファイルサイズ、ハッシュ値（MD5)、ファイル名（多重暗号化）、ファイル名長等

・ファイル名の文字列の先頭一部を使ってファイル名をRC4で暗号化している。

-キャッシュファイルの復号
・ファイルをブロック単位で読み込んで復号。
・暗号はRC4で行われている。

-Winnyのセキュリティ脆弱性
・ファイル転送用ポートに対して細工されたパケットを送信。strcpy()命令でピープオーバーフローが発生。

(1)0052290A mov dword ptr [edx],eax:EDX,EAXが制御可能
(2)00406011 call dword ptr [edx+0ch]:EBXが制御可能

(1)は任意のアドレスに任意の32bit値をセットできる。
(2)は任意のアドレスに含まれる32bit値-0x0Chにジャンプできる

First Vectored Handlerポインタ上書きで任意アドレスにジャンプできることを確認。
アドレスはある程度の範囲内で安定（NOPで対処可能な範囲内）。BindShell実行可能。

（脆弱性の部分については講演資料から一部をそのまま抜粋しており、私は要約していません。）

-脆弱性脅威分析
・きわめて簡単に発見できる脆弱性
・Winnyに感染するワームがあれば、数時間でほぼ大半のノードに感染するだろう。
（Winnyは隣接ノードを情報を持つため。）

□質疑応答(追記しました）

Q：脆弱性は現在あるパッチで解決するか？
A:複数パッチがリリースされている中で、とりあえず一つだけチェックしたが、そのパッチでは脆弱性が解決しないことを確認した。どのパッチだかは失念した。（修正しました）

Q:亜種についてはeEye製品で検知できるか？
A:現在はWinny2だけ検知できる。亜種、Shareなどについても検知できるように現在研究中である。

Q:欧米ではWinny+AntinnyのようなP2Pソフト関連の深刻な被害は報告されているか？
A:報告されていない。その理由は日米の文化面の違いではないか？
（補足：日米の文化面の違いについては詳細を語らなかった。おそらく日本のP2Pファイル交換ソフトが匿名性を重視しており、キャッシュ機能等を具備していることを指しているのではないだろうか？）

ちなみに私の質問は以下の通り：
Q：Winnyネットワーク可視化ツールは行政等に販売する予定はあるか？
A:現在可視化ツールの提供方法について検討中である。
Q:P2P Finderとの差別化戦略は？
A:リサーチ期間が短いので日本での状況について今後積極的に意見交換をして把握したいと考えている。

□補足（追記しました）
・Winnyのプロトコル詳細についてはpoenyのソースを見ればよいでしょう。
（IkeJIさまから当Blogへコメントがありました。http://b.ikejisoft.com/?05131147）
poenyとは？（FuktommyさんのBlogから）
http://blog.fuktommy.com/#e1141630998

□考察
Winnyのワーム攻撃の可能性について聞いて、Winnyネットワークに深刻な事態が現れる可能性を考えた。

Windowsサーバに関するワームにおいて、多大な被害を生じている事は多くの人の記憶にあるだろう。
今、Winnyに関してそのようなワームが生じた場合、実はWinnyネットワークを壊滅することが可能だ。

例えば、ワーム感染してから一定時間を経った後、キー送信等をさせない、リンクをダウンさせる、レジストリを書き換えWinnyを立ち上がらせないようにすることにより各ノードをWinnyネットワークから分離してしまうことである。

一旦壊滅されたWinnyネットワークはP2Pの性質から他のWinnyノードを知らない限り復旧は困難だ。またワームに対するパッチを当てるユーザは少ないから、結局今までのようなWinnyネットワークは形成できないかもしれない。

上記攻撃はP2Pネットワークを利用するソフトに対して起きるうる攻撃手法である。

補足：講演資料は非常に詳細な情報が載っている。興味のある方は知人等から資料をコピーしてもらうと良いでしょう。

[Winny]ダミーノードによるWinny情報漏洩対策効果の計算方法の提案

Antinnyによる情報漏洩の対策をWinnyネットワークを用いて行う方法は何種類かある。

大きく分けると
[1]ハッシュ値によるフィルタリング
→ボランティアユーザあるいはダミーノードによりハッシュ値のフィルタリングを行う。
[2]ブラックホールノードを上流ノードに配置し、ハッシュ値を拡散させない
→上流ノードにブラックホールノードと呼ばれるノードを設置し、キーの拡散をブロックする
参考：
Winny開発者にできること、できないこと3/3

の２つが考えられる。[2]は[1]を効果的に行う方法の一つと考えてよいだろう。

さて、実はこの２つの方法はかなりの協力ノード（これをダミーノードと呼ぶことにしよう）が存在しないと、ほとんど効果がないことを示したいと思う。おそらく、この手の効果測定は他の人は行ってないと思う。

キーの拡散は主に上流ノードで行われていることに注目する。
Winnyのノードは一般に２つの上流ノードと接続することに気をつける。

今、上流ノード間で４つずつリンクをしていると考えよう。リンクの方向性は今は気にしない。
上流ノードは簡単のために正方格子に並んでいて、隣接ノードとリンクしている。数学的にいうとZ^2の世界である。

さて今、ダミーノードを確率Pの割合で混入していく。このときPがいくら以上であれば、Winnyネットワークを分断できるだろうか？

実はこの手の計算は既に物性物理で盛んに行われている。その手法とは「パーコレーション」と呼ぶ。今回の方法は特にサイトパーコレーションと呼ぶ。

参考：パーコレーション：
http://www.mi.ics.saitama-u.ac.jp/~yas/research/network/percolation/

http://www.iba.k.u-tokyo.ac.jp/~yabuki/tip/swarm/percolation/percolation.html

では一体どのくらいダミーノードがあればWinnyネットワークは分断できるのか？答えはP=0.4以上、つまり４割以上がダミーノードである必要がある！これはとても大変な作業である。

もちろん今回の場合はリンク数、キー及び検索クエリの拡散の限界ホップ数等をあまり考慮していない。しかし、今回の計算でも明らかなようにダミーノードによるWinny情報漏えい対策は相当協力者やノード（あるいはリンク）数が必要であることがわかるだろう。

ちなみに前回のエントリーであるDHTはスモールワールドか？や今回のエントリーは増田直紀　他著「複雑ネットワークの科学」を参考にしている。数式を交えた簡潔な本なので、複雑系ネットワーク、P2Pネットワーク理論に興味のある方は是非とも読んでほしい。

[DHT]DHTはスモールワールドか？

スモールワールドが流行してた時に、DHTもスモールワールドであるかどうか議論が盛んであった。そこでDHTが本当にスモールワールドかどうか私なりの議論をしておきたい。

□クラスタリング係数
各種ネットワークを分類するときに、平均到達ホップ数とクラスタリング係数を算出することになる。
ここでクラスタリング係数とは、あるノードAに対してリンクを張ってあるノード群PがP内のノード間でどの程度リンクを張っているか示す数値である。クラスタリング係数Cは一般に０から１まで取り、C=1ならノード間は完全グラフ、つまりとても密にリンクされていることになる。

□スモールワールドとは？
スモールワールドとは平均ホップ数が小さいのにCが大きいグラフを指す。ワッツ＝ストロガッツモデルが有名である。平均ホップ数が小さいモデルとしてはスケールフリーネットワークが有名であるが、こちらはCが小さい。

□Chordにおけるクラスタリング係数の導出

さて、これからが本題である。DHTの手法として有名なChordについてクラスタリング係数を計算してみる。
当初、Chordにおけるクラスタリング係数について具体的な計算を行っている論文を探していたが見つからなかったので、今回の方法は私が独自で計算したものである。間違い等があれば指摘してほしい。

なお、数式を簡略化するため、AのB乗をA^Bと書くこととする。

Chordにおいてハッシュ空間を2^nとする。今、Node_ID=０から見ると、リンクはAノード群：Node_ID=2^0、2^1....2^(n-1)にあることになる。また、Node_ID=0にリンクしているノードも忘れてはいけない。これはBノード群：Node_ID=-2^0,-2^1....-2^(n-1)
である。ただし、簡略化のため　-P=2^n-Pを指すこととした。クラスタリング係数を出すには、
Node_ID=2^0,2^1.....2^(n-1)、-2^0,-2^1......-2^(n-2)間でリンクがいくつあるか計算することになる。ただし、左記で-2^(n-1)=2^(n-1)であることに注意してほしい。

＊Aノード群からAノード群へのリンク数
例えば、Node_ID=2^0は自身から距離2^0,2^1.......2^(n-1)までのリンクを張っている。それではAノード群からAノード群へのリンク総数はいくらだろうか？

ここで一つ補題を出す。
□補題１：
2^a-2^b=2^cが成り立つのはa,b,cが正の整数ならa=b+1、c=a-1に限る。
証明は簡単なので省略。

すると、補題を使って、Node_ID=2^0が他のAノード群とリンクをするノードはNode_ID=2^1に限られる。
同じように、Node_ID=2^aは2^(a+1)のみAノード群とリンクを張る。
つまり、Aノード群からAノード群へのリンク数はn-1である。なお、Node_ID=2^(n-1)から上記方法でリンクをするとNode_ID=0とリンクするので、この部分はリンク数からはずしている。

＊Bノード群からBノード群へのリンク数

先ほどと同じ手順で考えればよい。
□補題2
2^n-2^a-(2^n-2^b)=-2^a +2^b=2^c
はa,b,cが正の整数ならb=a+1,c=aに限る。　

よって、Bノード群からBノード群へのリンク数はn-1である。ここで上記方法だと、Node_ID=-2^1がNode_ID=0とリンクされるので、その部分をリンク数からはずしている。

*Bノード群からAノード群へのリンク数

これも同様な手順を考えばよい。

□補題３
2^a+2^b=2^c となるには、a,b,cが正の整数なら
a=b、c=a+1になる時に限る。

つまり、Node_ID=-2^aはNode_ID=2^aとリンクをすることなる。
リンク数は結局n-1

＊Aノード群からBノード群へのリンク数
リンクで一番距離が長いのは2^(n-1)のときである。Node__ID=2^(n-1)=-2^(n-1)におけるリンク計算はBノード群からBノード群へのリンク計算に既に入っているので、ここでは考慮しなくてよい。

すると、計算で関係するのはNode_ID=2^(n-2)のときである。これよりNode_IDが小さいAノード群はBノード群まで距離が足りないからである。Node_ID=2^(n-2)は距離2^(n-1)でNode_ID=-2^(n-2)とリンクを張る。ところが、このリンクは前述のBノードからAノードへのリンク計算に既に加味されている。

結局、ノード間のリンクは3(n-1)となる。クラスタリンク係数はNode_ID=0からのリンク数が2n-1であることを考えて、

C=3(n+1)/[(2n-1)(2n-2)/2]=3/(2n-1)となる。

□Chordはスモールワールドか？

Cを見てもらうとわかるが、nが十分大きいとCはかなり小さくなる。つまりChordをスモールワールドと考えるのは難しい。Chordにスモールワールド性を取り入れたSymphonyについては同様に計算ができるはずだが、（積分計算が必要）面倒なので途中で計算を止めてしまった。興味のある方はチャレンジしてほしい。

□Pastryはスモールワールドか？

今回は具体的な計算を出さないが、適当な仮定をするとPastryのCは簡単に求まる。こちらもハッシュ空間が大きいとCが小さいという結果になる。興味のある方はチャレンジして欲しい。

□DHTとスモールワールドの関係
DHTとスモールワールドはどちらも平均ホップ数が小さい。今回わかったことはDHTだからといって、スモールワールドであるとは言えないことである。DHTがネットワーク的にどのようなネットワークに分類できるのか、グラフ論的に調査すると、きっと興味深い結論がでるだろう。

[Winny]Antinny＋キーロガーによる情報漏えいの可能性について

Antinny等による情報漏えいが盛んな状況であるが、今後はより深刻な情報漏えいが起こる可能性がある。
それはAntinnyにキーロガーを仕込むことである。

□キーロガーとは？
キーロガーとはユーザがタイプした文字列等を記録するソフトである。ユーザがタイプした文字列は回線を通して、他人が監視することが出来る。キーロガーを使えばメール内容、閲覧したWebのURLはもとより、クレジットカードなどの暗証番号等を入手する事も可能だ。

インターネットカフェにキーロガーが仕込まれ、クレジットカードの暗証番号が漏洩したという事件はよく聞く話だ。
また最近ではbotにキーロガー機能があり、深刻な情報漏えいにつながるだろうと指摘されている。

参考記事：
「ボットネットを“飼って”みました」，Telecom-ISAC Japan
http://itpro.nikkeibp.co.jp/article/NEWS/20060426/236401/

□Antinny+キーロガー発生の可能性

botでキーロガーが出現すると言う事は、Antinnyにキーロガーが仕込まれるのも時間の問題である。
今までのAntinnyはPC内のファイルが暴露されるため、PC内に仕事等の情報が入ってなければ、深刻な被害にはならなかった。しかしながらキーロガーの場合にはキータイプ等の全ての情報が流出する可能性があるため、さらに深刻な被害が生じる可能性がある。いつのまにかにインターネット口座から引き落としされたり、クレジットカードによって勝手に他人が商品を購入できる事は朝飯前だ。ユーザのキータイプ情報はWinnyのキャッシュを使って、ほぼ永久にWinnyネットワークに残る事も可能であろう。

□Antinny+キーロガーの分類

では仮にAntinny+キーロガーが発生した場合、どのようなタイプに分類できるだろうか？私は大きく分けて2種類あると思う。

[1]キータイプ情報を特定ユーザのみ閲覧可能

これは今までのbot+キーロガーとほぼ同じである。攻撃者のみがキータイプ情報を閲覧できる。この手の情報漏えいをユーザが陽に把握するには時間がかかるため、攻撃者により長期間キータイプ情報を取得される可能性がある。

[2]キータイプ情報を不特定多数が閲覧可能

[1]より深刻な被害例である。大きく分けて3つに分類できる。

[2-1]キャッシュ利用型
キータイプ情報をWinnyネットワークに流出させる方法である。一旦流出すると、キータイプ情報の削除はほぼ不可能である。

[2-2]掲示板書き込み型
ユーザID＋パスワード情報のみを2ch等にURL付きで書き込む方法である。

[2-3]ユーザWebサーバ型
Antinnyに感染したPC自体がWebサーバになり、不特定多数のユーザが自由に全てのキータイプ情報を閲覧できる方法である。

Antinny+キーロガーが国家機関のPCに入った場合、かつてない程の深刻な被害が発生するだろう。