白かろうが黒かろうが、鼠を捕る猫はいい猫だ
某 H.264 のお仕事中のこと（つーか現在進行形だったりするのだけど）何か参考になる情報はないかと H.264 とか JVT とか AVC とかキーワードを変えながら google ことが日課だったりした。その際に見つけたページ [abcAVI Tag Editor]
このページを見ると、どうやら H261 〜 H269 までの FourCC は Intel が確保済みらしい。流石 Intel 体力にあふれている。H269 までの全 VCM/ICM CODEC を提供すると宣言するのはなかなか勇気が必要なことだと思うのだが……つーか H.265 から先なんてまだ影も形も無いはずなんだけど……すでに登録済みとは。
「どうやら Intel が VCM CODEC 提供してくれるみたいだから、エンコーダ作るのやめませんか〜」とか言ってみても通らないんだろうなぁ。くそー half pel 予測にも 6 tap filter が必要って……そりゃ遅くなって当然じゃないか。
最近購入した本の暗黒濃度があがっていてアレな感じ。いまどきのアセンブラプログラミング とか WindowsXP フィルタドライバプログラミング とかが代表例。そのうち RS-232C のクロスケーブルも入手しなければ。
えー、これらのブツが何に使われるかというと……ご想像の通りです。ただ、S-Box が判明しても、1COPY と COPY-FREE で別の暗号鍵を使ってる予感をひしひしと感じてしまうのが悲しいところなんだよなー。それが確定する前から心配しても仕方がないといえばそれまでなんだけど。
一度は諦めたのに、なぜこうして未練がましく続けてるのかをつらつらと考えるに……やっぱり 放送用エンコーダの出力ビットストリームを眺めてハァハァしたい ってぇのが大きいような気がする。
それとは別に「本当に優秀なハッカーなら、コピー制御を破るのは不可能ではないだろう」という発言に「無能なオメーラは指くわえてろ」という挑発を感じ取ってしまったからというのもある。
やっぱり馬鹿にされたら見返してやりたいよねー。もうそれに成功している人もいるんだし。
某 H.264 のお仕事での話。Baseline/Ex Profile の Level 3.0 以下には MaxSubMbRectSize とかいうたわけた制限があり、これに適合させる為にはエンコーダーでの Inter 8x4/4x8/4x4 予測で派手に面倒なことをしなければいけなくなる。（JM は当然のようにこの制限を無視している）
で、何でこんな仕様になったのかとても不思議だったのだけれども、どうやらこれは Texas Instruments が「この制限入れなきゃ CODEC チップ作ってあげないぞ〜」とごり押しして入れられたものらしい。というわけで、TI の石でデコードできるストリームを出力するためには MaxSubMbRectSize に対応してやらなきゃいけない。
まーその辺（Inter 予測）の面倒なアルゴリズムを考えるのは私の仕事じゃないから良いのだけど、実装も楽になりそうに無いのでウツだ。公式 FTP (2002/Oct Geneva 会合フォルダ) から JVT_E041 とかを眺めて見ると何故 MaxSubMbRectSize が導入されたか判って笑い出したくなること請け合い。
一昨日発覚した事実。H.264 デコーダ担当も私一人だけですか。まだエンコーダの P スライス対応すら済んでないというのに。このままでは CODEC 専任を経由して CODEC 仙人（俗世間のプログラムが書けない・客との折衝もできない・マネージメントができる訳でもない他から見ると何をやってるのか謎な人）へのクラスチェンジイベントが発生してしまう。
せめてデコーダは別の人に振られることだけを希望に日々の作業をこなしてきたというのに。嗚呼。嗚呼。
先週に引き続き圧縮フォーマットの調査。とりあえず CBC モードのユニットサイズや記録形式を探る為に、前回実行した 4096 バイト境界でのビットエラー挿入に加えて、2048, 1024, 512, 256 バイト境界でのビットエラー挿入を実行。
結果、CBC のユニットサイズは 512 バイトで、TS パケット間に 6 バイト非 TS データが挿入されている（188+6=194 バイト単位で HDD に記録されているらしい）ということが判明した。
先頭から 130M 前後の領域はちっとも書き換わらないので、ここにマスターキーが入っていて、8k ブロック毎にマスターキーと HDD のシリアル等からブロック鍵を作り直しているのかと妄想していたのだけど、512 バイトブロック毎に鍵を切り替えるには 130M 程度ではマスター情報を記録しきれない。
というわけで、来週の課題はどの範囲で同じ鍵が使われているかの調査。CBC ユニットを隣と入れ替えて同じデータが出力されるかとか、別のバイト境界のデータと CBC ユニットを入れ替えての調査とかの予定。うー S-Box さえ判ればそろそろ総当りを開始できる状態になってはいるのだけど……。
大宇宙からの大いなる電波をよんよんと受信して、確度は 50% 程度の S-Box 情報を取得。サンタさん、すこし時期はずれだけどクリスマスプレゼントありがとう。
とりあえずこの S-Box が正しいものとして総当りプログラム作成中。えーと、そんな人は居ないと思うのだけど。AVHDD は HDD 毎に異なる鍵が使われているので、私が運良く鍵をみつけるのに成功しても、それは他の Rec-POT には使えません。
もちろん AVHDD の鍵生成アルゴリズムとかまでクラックできれば、AVHDD 完全制覇と言えますが、とてもそこまでやれるとは思えないので。つーわけで、1COPY 回避を目指す人はそれぞれ頑張ってください。
Intel C/C++ Compiler が久々のメジャーバージョンアップを行ったらしい。とりあえず職場でダウンロードは済ませて、README のチェック中。どうやら Q194216 "IDE integration in Visual Studio .NET 2003 doesn't load the Japanese project" が修正されているらしいのはありがたい。
うーん、MPEG-2 VIDEO VFAPI Plug-In ver. 0.6.46 のリリースを急ぎすぎてしまったか。一日待てばコンパイラの変更も一緒に済ますことができたのに。
それなりの確度の S-Box が手に入ったので、総当りを開始した。うーむこのプログラム & CPU (P4 2.4C) では 4Mkey/sec が精一杯か。2^56 空間の全検索には 400 年かかってしまう。
せめて生きてる間に成果を手に入れたいので、もう少し何とかしなければいけないか。対策としては。
といったところか。できそうなところから並列に手を入れてくことにしよう。Eli Biham の "Differrential cryptanalysis of DES-like cryptosystems" とか他の論文ももう少し真面目に読んでいかなきゃなー。
Intel C/C++ Ver. 8.0 の主変更点は、Pentium M/P4(Prescotte) 最適化機能の追加あたりらしい。どっちも持ってないし最近では P3 最適化オプションしか使ってないので、急いで更新することはなかったかなという気分。
まーアップデート権限が有効な期間内だったので、更新してしまったけど。というわけで、0.6.46 では報告してもらったバグがさっぱり直ってなかったので、Intel C/C++ Ver. 8 を使用して 0.6.47 作成した。
gcc -O3 -fomit-frame-pointer -fstrength-reduce -funroll-loops -march=i686 により、7.4 Mkey/sec にまで速度は向上したもののそれでもやっぱり終わるまでには 304 年。
ラウンドごとに鍵と中間コードを足して S-Box を引っ張ってくる処理があるので、SIMD 化しても美味しくなさそうだし、キースケジュール部分も最適化方法が思い浮かばない。（F 関数用に S-Box を 32 bit に広げるのと、キースケジューラ用に S-Box を 4 bit シフトしておくのは実行済み）
ハード追加にしても個人では 10 台程度が限界だし、そこまでやっても 30 年かかってしまう。分散処理を本気で考えるべきだということで、サーバ側の仕様とか考慮中。せっかく一台自由になるサーバ持ってるんだし。
先週末から予定を変更して、例のアレのサーバ側アプリケーションを作成。土日を潰して何とか適当なものをでっち上げ、とりあえずテストまでは完了させることができた。次はクライアント側に通信機能を実装しなければ。
今から心配しても仕方がないことなんだけど、いったいどれほどの協力者が確保できることだろう。とりあえず 1000 人確保できれば、一年以内で全探索ができるようになるので多少は望みが出てくるのだけど。
何しろ現状では入手した S-Box が正しいかどうかさえ判ってないからなー。（現在実行中の総当りで確認予定だったりする）
分散攻撃開始 しました。現在攻撃中なのは手元のマシンだけですけど。サーバ側 & クライアント側共に思いっきり手抜きな上にクライアント側のソース公開なもので、改ざんデータ送りつけようと思えば簡単ですが、できればそーゆーことはしないで純粋に CPU の空き時間と電気代を提供してください。
えーと、現在公開中なのは Windows 用クライアントのみですが、希望者が居れば unix 用クライアントのソースも提供します。動作環境は常時接続必須で、グローバル IP への HTTP (port:80) アクセスが通る必要があります。手抜きの結果 PROXY には非対応になってますが、希望者が居れば対応クライアント作ります。
攻撃結果によって判明したことは全て公開する予定ですので、協力お願いします。
まだ確定ではないらしいが、どうやら H.264 デコーダの担当からは外れそうな気配。他社の開発も進んでいるのでエンコーダ・デコーダ合わせて担当１人では追いつけないからというということらしい。
エンコーダの担当者が増えるという話は無いらしいので仕事が楽になるわけではないけれども、あの訳の判らないオプションに全対応しなければいけないデコーダにかかわらなくて済むというだけで非常に気持ちが楽になる。つーか FMO やら Multiple Ref Frame がどうして Baseline Profile に入ってるのかが不思議だ。
昨日から開始した 分散総当り攻撃 は順調に協力者が出てくれているようで、一晩で 768 block も進んでいた。このスピードなら 20 年以内に全探索は終わってくれる。
正直なところを言うと、できれば１・２週間ぐらいでブロックの鍵推定ができるようになってくれれば、かなり解析しやすくなるのだけど、強制できることではないから仕方がない。
そのメニューがですね、ほかのところクリックしても消えないんですよ。
うわ、本当だ。帰ったら直します。クライアント数、現在 72 台ぐらいです。協力してくれている方々、本当にありがとうございます。
うーん、30 人×α台＝100クライアントぐらい確保できれば良いほうかなと思っていたのだけど、それなりに紹介されているようで、レポートを上げてくれたクライアントが 200 台に、接続してブロックの割り当てを要求しただけのクライアントまで含めれば 280 台を超えている。
かなり希望が出てきた。現在の速度を維持できれば 5 年以下で検索完了しそうだし、コードをアセンブラで書き直して 2 倍のスピードにできれば３年以内で全検索完了も夢ではない。
とりあえずサーバ側のでっち上げ ruby スクリプトではクライアント数があと３倍に増えてしまうとサーバーの CPU 使用率が危険な領域 (80% 以上) に突入してしまうからそっちも何とかしなければ。
以下、見かけた反応への応答です。
FreeBSD 版ならサーバ側テストに使ったクライアントのソースはあるのですが、ソケット周りでコンパイルエラーが出そうな気がするので、linux でもテストを済ませてから tar.gz 公開します。日曜まで待ってください。
分散 C2 総当り攻撃 が何を目的としたものか判りづらい方向けに、今までの背景へのリンクページを作成しました。順に読んでいけば何を目的にしたものか判るかと思います。
アセンブラで書けば間違いなく速くできるでしょう。ただ、それにかかる時間と速度向上をはかりにかけて、とりあえずはコンパイラの最適化に任せて、分散処理環境をでっち上げた方が完了までの時間を少なくできると考えて、そちらを優先することにしました。とりあえず UNIX 用ソース公開できたら次はアセンブラによる最適化に移る予定でいます。（最適化コードの提供は大歓迎です)
クライアント側の IP はチェックしていない（Apache でのログには残ってるけど）ので、NAT/NPT の後ろの複数マシンで動かしても問題はありません。あと、c2bf.exe は何時止めても問題ありません。空いてる時間に動かしてください。
UNIX 用クライアントのソースを公開しました。実は今日の AM 1:00 頃から 0.1.0 の公開はしていたのですが、中断・再開時の情報の引継ぎが正しく行われていなかったので、バグを修正した 0.1.1 を公開しています。
一応 FreeBSD 4.9-STABLE/VineLinux 2.8r3 でコンパイルおよび動作確認までは済ませたので、大抵の環境でそのまま make が通ると思います。コンパイルに障害が発生したけれども、内部の構造やクライアント・サーバー間のプロトコル等で不明な点があり、移植に障害が出たという場合はメールいただければできる限りの情報を提供します。
UNIX 版クライアントのテスト用および総当りへの戦力投入のために、キューブタイプのベアボーンキットで Celeron 2.8 GHz の PC を新たにでっち上げた。HDD は浮いていた 20G 物を流用したので、出費は 35,000 円程度。コードを書いていたときから c2bf のスピードはクロックにしか依存しないだろうと想像していたとは言え、やっぱり前回組んだ P4 2.4C GHz マシンよりもブロックレートが高いとなると少し落ち込んでしまう。
P4 2.4C GHz の場合は 1 ブロック (32bit 鍵ブロック) のテスト完了に 500 秒近くかかっていたのが Celeron 2.8 GHz の場合は 420 秒で済んでいる。後は 2ch DTV 板「MPEG-2 TS を...」スレッドによると Athlon XP の実クロック 2.3 GHz の場合だと 395 秒で済むらしいから……やっぱり P4 系はビットシフトやビットローテーションが AMD に比べて効率悪いらしい。distributed.net の DES クラックの時も、同じ傾向を示していたし。K6-2 300 MHz 以来になってしまうけれども、次は Athlon で組んでみようか。
さて、UNIX 用クライアントも公開したことだし、SIMD コードを考えはじめよう。後は教えてもらった time memory tradeoff attack の詳細調査もしなければ。
Win 用クライアントに MMX コードを入れました。MMX Pentium/Pentium II/K6-2 以上であれば動くはずです。そんな方は居ないと思いますが、486 や Normal Pentium では動かなくなってしまいましたので、その場合は 0.1.1 を使っていてください。
有給とって 4 連休にした 3 日目をほぼまるまる潰して書いたコードの割には速度向上が 3 割程度と悲しい結果になってしまった。キースケジューラ部はかなり高速化できたのだけど、肝心の Feistel ネットワーク部で SIMD 化の効果がほとんど出てないのが悲しいところ。
えーと次は、UNIX 用クライアントにテストルーチン追加して（add と shift と xor しか使ってないのにバグが出るコンパイラってのもかなりアレな感じだけど） solaris 向けのコンパイルメモを readme.ja に追加して。SIMD 版の Feistel ネットワークで rol を使う方を試してみて。nasm の文法と gcc のグローバルシンボルの扱い方しらべて……。
ちょいまえ (13:30) に起きた。あ〜折角の休みだたのに。えーと「MPEG2 TS..」スレをチェックして……マルチ CPU 向けか……安直に ini に逃げることにしよう。どうせ中でスレッド作ってるんだし、CPU の数をカウントしてスレッド増やそうとか考えてたけど、面倒だし、プログラムよりもユーザの方が CPU の数には詳しいだろう。
えーともう一段 SIMD 最適化できないか試してみて、そのタイミングで入れることにしよう。次は referrer チェックして……むー CPU が 100% 行くのがつらいといわれてしまうとなー。スレッド作成時に優先順位 IDLE にセットしてるので、他のアプリケーションが CPU 必要になったらすぐにそちらに制御をまわすはずですから、それで勘弁してください。
う、サーバ側平均 CPU 使用率が 30% 超えてしまっている。そうか、クライアント台数じゃなくて、報告頻度によって CPU 使用率は決まるからクライアント側の処理効率が上がれば当然サーバ側の CPU 負荷も高くなってしまう。思いっきり見落としてた。
現在、延べクライアント数は 568 台。鍵探索も順調で、開始 6 日目にして、2 行目の 1/4 を超えました。はじめた時にはこんなに順調に進んでサーバ側の負荷が問題になるような時がくるとは思ってもいませんでした。
これもみな、サイトや BBS で取り上げてくれた方々と、なによりも実際にクライアントを起動してくれている皆さんのおかげです。まだ 1/256 の探索が済んだだけと先は長いですが、今後ともよろしくおねがいします。本当にありがとうございます。
どうやら 0.1.2 で追加した MMX コードは P3 系での速度改善効果が絶大の模様。解析速度が倍以上に上がってくれているようなので嬉しいのだけど、本当に嬉しいのだけど……どうして P4 2.0GHz が P3 1.26GHz にキーレートで負けるのだろう。
解析マシンは Celeron 2.8G ではなく Celeron 1.4G を買ったほうが良かったのだろうか……なんとなく負けた気分。P4 系が激しく欠陥品に思えてくる。昨日試してみた rol (rotation left) 命令も SIMD シフト二つと OR の方が速いという結果になって散々だったし。
暗号化などのアクセスコントロール機能はまだ著作権法での保護の対象とするかどうか審議中（しかも著作権の根幹に関わるので慎重に議論すべきという扱い）のレベル [参考 URI] で、全然違法行為でもなんでもなかったりするのだが、分散 C2 総当り攻撃 はどんな罪に問われるのだろー。うわー怖いなー恐ろしいなー。ボク逮捕されちゃったりとかするのかなー。
開始 1 週間で 3 ライン目突入。2 ライン目は 3 日かかってないから、このペースならもう 2 年は切っているはず。サーバ側もやらないよりはマシ程度の最適化 (画像の更新は最低 2 分経過後でなければ行わないとか、analog 止めるとか) を実行。現在振り分け済みブロック数が 625 でサーバ側 CPU 負荷が 50% 程度 だから、もう 200 台ぐらい PC が増加しても大丈夫そう。
WIN 用クライアント更新しています。今回は追加の最適化はなく、ワーク情報の保存先をレジストリから ini へ変更した関連で埋め込んでしまったバグの修正をしています。
常時起動中の猛者にはあまり影響がないかと思うのですが、何らかの問題で PC 再起動が必要になったときとか、あるいはキャプチャマシンで協力してくれていて、キャプチャ時だけは止めておきたいという方は更新しておいてください。0.1.3 では起動後の最初の 1 ブロックの計算が無駄になってしまうので、よろしくお願いします。ダウンロードは 分散 C2 総当り攻撃 からです。
どうやら１０月に受けたテクニカルエンジニア（ネットワーク）には合格できていたらしい。発表は１月だとばかり思っていたのだけど、実家に戻ったら合格通知が届いていた。
受験料を無駄にせずに済んだのは嬉しいことだ。さて、次はデータベースでも受けることにしよう。
MMX 最適化版クライアントにバグを発見したため、分散 C2 総当り攻撃 は現在、サーバ側からのブロック割り当てを停止しています。[AM 0:25]
現在、Windows 用クライアントは "[E] failed on 2nd get_key()" か "[E] get_key() reached max retry count" を表示する状態で停止しているはずです。UNIX 用クライアントも鍵取得に失敗して終了しているはずです。
バグを発見したクライアントは Windows 用の ver. 0.1.3 および ver. 0.1.4 で、MMX 専用版として公開していたものです。このバージョンにはサーバから割り当てられた鍵ブロックと無関係な鍵ブロックのチェックを行うバグが存在しました。MMX 版公開から現在までに進んだ 0x008000 〜 0x03f000 までの鍵ブロックの解析結果は信頼できないために、全て破棄します。
バグ修正版の公開およびサーバからの鍵割り当て再開のスケジュールや、UNIX 版 / 非 MMX 版での修正の有無等は現在検討中です。[AM 1:00]
バグありの MMX 最適化版だけ鍵取得等から排除する手段がないか考えてみたのですが、簡単には実現できそうになかったので、UNIX 版、非 MMX 版含めて全てのクライアントを更新し、報告先アドレスを変更という対策をとることにしました。
現在各クライアントの最終テスト中で、本日 20:00 には修正版クライアントの公開 & 鍵割り当て再開という予定でいます。参加者の皆さんには手数をかけさせてしまうことになりますが、現在のクライアントは削除して、新しいクライアントをダウンロードしなおし、そちらを起動してください。
まだ修正版クライアントはテスト中ですので、ダウンロードはできません。修正版クライアントの公開予定は 20:00 頃です。[15:48]
修正版クライアントの公開および、サーバからの鍵ブロック割り当てを再開しました。[20:05]
やらねばならぬことは（手抜きだけど）済ませたので、心ゆくまで落ち込むことにする。間抜けすぎるバグにより５日間の計算結果が失われ、クライアント PC も増えてきてさあこれからという時期にブレーキをかけなきゃならなくなるとは……。
先週のうちに片付けることに失敗してしまった某 H.264 のお仕事の続きをしてみる。とりあえず CQ 設定で rdopt JM 比 1.1 倍強程度の符号量に到達させることはできた。当初は JM 比 2 倍とか 3 倍とかになってたからなー。後は QP=26 以外でも対処できるように ME 周りの内部構造を直してやれば、それなりの気分で新年が迎えられる。
少し考えればまだまだ難題が山積みのような気もしてくる（Multi Ref/Field/CABAC/Loop Filter) けど、健康の為にその辺はあまり考えないようにして。なるべく人生の明るい側面だけを見るようにしよう。
今年中に片付けておきたかった仕事も完了したので、nasm & gcc の調査開始。どーやら MASM よりも書くべきコードは少なくてすむ（といっても誤差のレベルだけど）らしいということと、gcc では cdecl 相当の呼び出し規約しかないらしいということは理解できた。スタックは関数の呼び出し元がクリアすることになっているらしい。
後は実際にコードを書いて試してみることにしよう。UNIX 版ではあんな醜態はさらさなくて済むようにしなきゃ。