ブロげ

無線LANのセキュリティに危機？「WEP」に続いて「WPA」までも一部解読

ちなみに上記の記事におけるTKIP=WPA1の終了が正しいかどうかについてはどうですかね。WPA-AESがまだあるので。WPA対応ということはAESチップを持っているし。

RC4使う系が軒並みダメということ？

これホントの話なのかなぁ。

まるもさんの日記の動きベクトルについてが非常に分かりやすい。

ffmpegとx264を調べたところ以下の動きベクトル算出法が見つかった。

• full motion estimation – full search(alias ‘esa’ – exhaustive search algorithm)
• EPZS motion estimation (alias ‘dia’ – diamond search)
• tesa motion estimation – transformed exhaustive search algorithm
• log motion estimation
• phods motion estimation – parallel hierarchical one-dimensional search algorithm
• hex motion estimation – hexagonal search
• umh motion estimation – uneven multi-hexagon search
• iter motion estimaion – iterative search

ffmpegで通常使われるのはEPZSというアルゴリズムだが、このアルゴリズムはdiamond search→MVFAST→PMVFAST→EPZSと改善に改善の論文を重ねて作られている。ffmpegではdiamond searchのエイリアスでEPZSが選択される。

full searchやumhについてはffmpegの中には入っておらず、x264のソースコード内にて発見した。

SIMD化されたCPUで上手く動作するのだろうか、気になった。アセンブリで書かれているのはiDCTとDSPの部分をMMX, SSE化しているものが多かった。ffmpeg、x264ともにマルチスレッドや64ビット化には対応しており、ベンチマークしている方々がいらっしゃる。x264のcell化は無理だったのか、と、ふと思う。

このコード群をJAVAやRubyにしたら面白いかなーと思いつつ、別に面白くないやと思う今日の午後。

ネタで取得した11n.jpおよび11s.jpの来期の契約が今月に迫っております。

不況のあおりを受け、経費削減が重要課題になりつつあります。

2008/11/31が期限ですが更新しない予定で検討してます（臨時収入がない限り）。

サーバも、これを期に一旦解約（〜2009/02/27）する方向で検討しています。

もし802.11n.jpや802.11s.jpなドメインでハァハァしたい無線LANな方がいらっしゃれば、お譲りできます。

MPEG-2の規格には、Iピクチャー、Pピクチャー、Bピクチャーが存在する。このＩ, P, BのピクチャーのグループをGOP(Group Of Picture)と呼ぶ。例えばDVDのGOP構造はIBBPBBPBBPBBPBBとなっている。

Iピクチャーはフレーム内圧縮しか行わないJPEG画像のようなもの。Pピクチャーは順方向（過去の画像に対して）の参照を行うことができる。Bピクチャーは両方向（過去と未来の画像に対して）参照を行うことができる。

実はこの時点で、「Pピクチャーは必ず順方向の参照を行う」「Bピクチャーは必ず両方向の参照を行う（だからBピクチャーを利用する符号化は重い）」と私は考えていた。が、講義を受ける辺り、そうではないらしい。

あくまでもI,P,Bピクチャーの時点では”参照を行うことが可能である”だけであり、実際に参照するかどうかを決めるのはmacroblockのようだ。Pピクチャー、Bピクチャーにてそれぞれ指定することのできるmacroblock_typeが異なり、このmacroblock_typeによって参照を行うかどうかが決定される。

よって、Iピクチャーは全てIntraのmacroblockだが、Pピクチャーで全てがIntraのmacroblockであっても良い。Bピクチャーの中身が全てIntraのmacroblockであっても良い。

実際にBピクチャーの前後にシーンチェンジが存在する場合、両方向の参照ではなく片方向への参照のみになるケースがあり、シーンチェンジの検出に利用できるという話であった（既に特許申請済みだという）。この点については確かにそうで、Bの前後でシーンチェンジがあった場合に両方向の差分を活用するよりは片方よりの予測の方がコストが少ない。

P,Bピクチャー内でどのタイプのmacroblockを選択するかについては、全部やってみる、らしいことを聞いた。BピクチャーではIntra,Forward Pre, Backword Pre,Bi Preと、4種の参照を検証しなければならないことになる。だから重いんだ、という説明で合点がいった。

不思議だったのは、PピクチャーにてIntraのmacroblockが微小だが存在していた点だ。順方向参照を行うよりもIntraで処理した方がコストが良くなることはあるのだろうか。それとも画質優先のためにIntraを選択したのだろうか。

このmacroblockに対する知見をネットワーク伝送に生かせないだろうか考えているが、いい案が浮かばない。残念だ。

昨年の夏にブロげ » MPEG-2 TSのスライスヘッダと称してMPEG-2 TSからスライスヘッダまで潜って帰って来た経験をした。

今は講義で最下層のブロック層から浮上するということを行っており、通好みでたまらない。ISO/IEC 13818を眺めながらまったりしている。

特にMPEG-2にはVLCという処理があり、メディアプレイヤであるVideoLan Clientと名前が類似しているので、気持ち悪かった記憶がある。そのVLCとはVariable length codingのことを指しており、DC成分やAC成分を効率的に符号化することを目的としている。

例えばDC成分に対してはブロック間で予測符号化を行い、AC成分に対してはブロック内で係数0をまとめるような符号化を行う。さらにVariable length codingに持っていくにはスキャンや量子化に秘密がいっぱい。英語でもzigzag-scanと表記するなんて驚き。

と、これ以上MPEGの世界に突っ込むと実装に手を出しそうなので宿題のレポートを書いて終わりにしよう。

先週の金曜日にやったが、書き忘れていた。

TCPのコネクションについての話は前回で終わり、今回はインタラクティブ・データのやり取りについて。

インタラクティブな通信とは何か。例えば、ファイルの転送とssh(telnet)の操作で求められるネットワークの制御＝トランスポート層プロトコルの挙動は違う。ファイルの転送では大量のデータを効率よく伝送することが主目的で、双方向的な入力に対する応答性にはこだわらない。逆にsshのようなインタラクティブな通信ではファイルの転送も出来るに越したことはないが応答性の方が重要である。

まずインタラクティブ通信ではプッシュ（PUSH）フラグが意味を持つ。PUSHフラグを用いることで送信バッファが溢れるのを待たずにすぐに送信することができる。もともとファイル転送のようなバルク転送では、アプリケーションからある程度のデータがTCPにバッファされてから送信する方が、送信するTCPセグメント数を減らすことができるためTCPオーバーヘッドを減らすことができる。sshのようなインタラクティブ通信では効率性よりも応答性の方が要求されるため、PUSHフラグを用いてすぐに送信を行う。ただしPUSHフラグに対する挙動は実装依存であるため注意が必要である。

rloginリモートログインコマンドでは、キーボードから一文字入力するごとにアプリケーションからTCPに送信行為が行われる。前述のPUSHフラグによって、（Nagleアルゴリズムを用いない）すっぴんのTCPではキーボードの打鍵ごとに1つのTCPセグメントが生成され、送信される。例えば、10回のキーボードの打鍵によって、10のTCPセグメントが生成され、送信される。

さらにリモートログインでは打鍵したキーの内容をサーバからクライアントにechoする。”k”と入力したのであれば、”k”がサーバから応答される。よって以下のように1打鍵により2回のセグメントの往復が行われる。

1. クライアントからサーバに”k”を送信する。
2. サーバからクライアントにACKを送信する。
3. サーバからクライアントに”k”を送信する。
4. クライアントからサーバにACKを送信する。

これは著しく非効率である。この効率の問題を解決するために2つのアルゴリズムを紹介する。それがNagleアルゴリズムと遅延ACKである。

遅延ACK

まず、前述の4つのシーケンスを見るにあたり、2.3.のサーバからクライアントへの通信が2つ続いている点に着目する。実は3.のTCPセグメントではACKフラグがたっており、実質2.が送信されなくても問題はない。そこで、受信側TCPの処理として遅延ACKという手法をとることが提案される。

すっぴんのTCPはセグメントを受け取るにあたり、すぐにACKを返そうとする。このACKを返そうとする時間に遅延時間を持たせる。この時間はおおむね200msである（たしかRFCで決定されている）。この200ms待つ間に通信相手から他のセグメントを受け取ったり、アプリケーションから送るべきデータを受け取ったりする。もし新しいセグメントを受け取ったのであればACKを更新し、アプリケーションからデータを受け取ればそのデータも一緒に送ろうとする。そして200msのタイマーが切れたら送信を行う。このように受信応答に対してデータ送信を”便乗”させてしまう行為をpiggybackと呼ぶ。

今回の場合、サーバからのechoの送信要求にはPUSHフラグが立てられているため、以下のようなシーケンスになる。

1. クライアントからサーバに”k”を送信する。
2. サーバからのACK送信は遅延ACKにより200ms抑制しようとする。
3. サーバからクライアントに”k”を送信する。PUSHフラグにより、すぐに送信する。
4. クライアントからサーバにACKを送信する。

実際に送信しているのは1.3.4.であり、4回のシーケンスが3回に抑制されている。

以上のように遅延ACKとはTCP受信側の処理である。

nagleアルゴリズム

先ほど、rloginのようなアプリケーションは打鍵ごとにTCPに要求を出すため、「10回のキーボードの打鍵によって、10のTCPセグメントが送信される」と説明を行った。

このように送信要求ごとに小さいセグメント（例では1バイトの長さ）が生成されることによって、ネットワークの効率は悪くなる。特にLANのような高速なネットワークでは問題はないが、インターネットのようなWANのネットワークでは遅延が大きく、いくつもの小さいセグメントを回線上に載せてしまうこととなる。

このアルゴリズムで行いたいことは「インターネットのようにRTTの大きいネットワークで、いくつもの非効率な小さいパケットを送信したくない」ということである。そこで、nagleアルゴリズムでは「MSSではない小さなTCPセグメントを送出した場合、ACKを受信するまでは次の小さいセグメントを送信しない」というルールを決めた。

このルールでは、RTTの小さい高速なネットワークでは、非効率な小さいパケットは問題にならない。

例えば、RTTの大きいネットワーク上で、abcdef…と連続的に打鍵した場合は以下のようなシーケンスになる。

1. クライアントからサーバに”a”を送信する。
2. クライアントからサーバに”b”を送信しようとするが、”a”のACKを受信していないので送信を抑制する。
3. クライアントからサーバに”c”を送信しようとするが、”a”のACKを受信していないので送信を抑制する。
4. クライアントからサーバに”d”を送信しようとするが、”a”のACKを受信していないので送信を抑制する。
5. サーバからのACK送信は遅延ACKにより200ms抑制しようとする。
6. サーバからクライアントに”a”を送信する。PUSHフラグにより、すぐに送信する。
7. クライアントからサーバにACKを送信するが、送信バッファにあるデータ”bcd”と一緒に応答する。
8. クライアントからサーバに”e”を送信しようとするが、”bcd”のACKを受信していないので送信を抑制する。
9. クライアントからサーバに”f”を送信しようとするが、”bcd”のACKを受信していないので送信を抑制する。

このようなルールを適用することによって、RTTの大きいネットワークではまとめて、RTTの小さいネットワークでは小出しに送信することができるようになる。

nagleアルゴリズムは遅延ACKとは違い、送信側の処理である。

まとめ

遅延ACKとnagleアルゴリズムは無駄なセグメントの送信を抑制するための手段である。場合によっては、これらのアルゴリズムが障害になる場合もあり、そのときには解除することも必要である（それが昔にやってた研究だったり）。

TCPのコネクションの話が終わってすぐに遅延ACKとnagleアルゴリズムを取り出してくるあたり、この本は面白い。が、初めて読む方々は辛かろう。実際、そういう顔だったし…

ns-3について解説します。

簡潔に示すと以下の通り。

• ns-3ではOTcl排除でC++とPython。コンパイルが楽になった。（だからns-2の資産は使えないよ:p）
• 実環境との比較が楽に。Pcapファイル出力できるのでWiresharkで解析できる。実際のLinux Kernel実装のTCP輻輳制御メカニズムを利用できる。
• エミュレーション環境の進化。リアルタイムスケジューラ。Virtual Machine（VMware）を用いてのエミュレーション。

ちなみに、ns-3は夏あたりから”特別な”進化をしており、その理由は2008 Google Codeだと思われる。実際にそれ以前のns-3は使いたいとは思えなかった。

ns-3のネイティブのTCPモジュールだと送信側のTCPセグメントのACKに値が入っていないので、Wiresharkで詳細に解析できない。NSCによるLinux 2.6.26のTCP輻輳制御を用いた送信ではACKフィールドにも値が入っていることを確認した。

個人的には実環境向けにPcap解析プログラムを書いていたので、ns-3がPcapを吐いてくれるのであれば同じ解析プログラムを利用できるので、非常に便利。C++のシナリオファイルはC派の人間ならOTclよりもとっつきやすい。

結論としては、既存のns-2の資産を利用する予定があるのならns-2を、シンプルでかつ実環境との比較をやりたい派やPcapの解析プログラムなどの資産を持っている派、新しいものは再考だよね派は間違いなくns-3を使うべきだと思う。

Linuxカーネル実装を流用できるということは、ns-3でLinuxカーネル対応のTCPモジュールを書けば、すぐに実環境で実験できるという意味だから。

ぶろゲに比べると、このサイト、平日のアクセスが実に多い。アクセス解析から平日がなんとなく分かるくらい酷い。

かつ、日々を無線LANするサイトなのにMPEG-2とTCPの話題で来る人が圧倒的に多い。何処で間違えたんだろうか。多分、2008年以降にLinuxでTCPやる人だったら見たことある人は多いかも。

dlna 2.0 – Google 検索
とりあえず”DLNA 2.0″のトップは取れた。

mpeg-2 ts pts – Google 検索
pesヘッダー 詳細 – Google 検索
スライスヘッダ – Google 検索
mpeg2 ヘッダ – Google 検索
dccp linux – Google 検索
wrt300n – Google 検索
linux tcp タイムアウト – Google 検索
gop ts – Google 検索
emf eps – Google 検索
tcp timeout – Google 検索
aodvd – Google 検索

このブログ、誰にもリンクされないのに、掲載順位が高いってどういうことよ！？

# それともニッチ話題？

「WEPを一瞬で解読する方法」を研究者グループ発表　プログラムも公開予定 – ITmedia News

WEPを使っているおとこのひとって・・・

　今回報告した方法は、特殊なパケットを集める必要がなく、一般のIPパケットを傍受した上で、3つの関数を使って鍵を推測するなどの方法を使い、104 ビットのWEP鍵をごく短時間で導くという。「不正アクセスをすることもなく、相手に気付かれず、一瞬にして、WEPの鍵を導出できる」（森井教授）

104ビットということは128がダメなんですね、分かります。

とりあえず、任天堂DSのためにWEPを使っている方はアクセスポイントの電源を切りましょう。切りましょう。

WEPの暗号化チップしか無線LANが搭載していなくても、WPAのTKIPなら対処できるのに対処しようとしないのは何なの？

携帯可能な無線LANアクセスポイント「どこでもWi-Fi」発表

ほどよく売れると思います。